Counting variables in a dynamic setting
Marco Hollenberg · Journal of Logic and Computation · 1996
We discuss the issue of finite variable fragments from a dynamic perspective. In the traditional, static approach to first-order logic this is a well-investigated area of research which is relevant for reasons of memory management. Instead of taking PRED, first-order logic with equality, as our base language, we look at DPLE, a variant of predicate logic developed in the area of dynamic semantics for natural language. DPLE has the same expressive power as PRED, but gives a procedural treatment of the quantifiers: it represents existential quantification as a push operation on a stack. The end of the scope of a quantifier can then be mimicked by a pop operation. We present a characterization of all the finite variable fragments of DPLE. It is shown that, in the presence of =, all formulas of DPLE containing at most n-ary predicates have an equivalent that uses at most n variables. These equivalents can be obtained effectively: reducing the number of variables corresponds to using n stacks for the simulation of programs that run on n + m stacks.