Volume 6: January - December 1996

Issue 5: October 1996


Counting variables in a dynamic setting

  • Counting variables in a dynamic setting
  • M. Hollenberg and 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 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.

    Keywords: Finite variable fragments, dynamic logics, predicate logic, stacks, semantics of variables.

    Pages: 725 - 744

    Part of the OUP Journal of Logic and Computation WWW service

    General Information

    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