and M. Hollenberg K. Vermeulen Department of Philosophy, Utrecht University, Heidelberglaan 8, 3584 CS Utrecht, The Netherlands
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 nvariables. These equivalents can be obtained effectively: reducing the number of variables corresponds to using nstacks for the simulation of programs that run on n+ mstacks. Finite variable fragments, dynamic logics, predicate logic, stacks, semantics of variables.
Part of the OUP Journal of Logic and Computation WWW service
Click here to register with OUP.
This page is maintained by OUP admin
Last updated 19 Nov 96
Part of the OUP Journals World Wide Web service.
Copyright Oxford University Press, 1996