Finite variable logics in descriptive complexity theory

Bulletin of Symbolic Logic 4 (4):345-398 (1998)
  Copy   BIBTEX


Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth.



    Upload a copy of this work     Papers currently archived: 84,292

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

24 (#513,457)

6 months
1 (#510,180)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Finite and Infinite Model Theory-A Historical Perspective.John Baldwin - 2000 - Logic Journal of the IGPL 8 (5):605-628.

Add more citations

References found in this work

[Introduction].Wilfrid Hodges - 1988 - Journal of Symbolic Logic 53 (1):1.
[Introduction].Wilfrid Hodges - 1986 - Journal of Symbolic Logic 51 (4):865.
On languages with two variables.Michael Mortimer - 1975 - Mathematical Logic Quarterly 21 (1):135-140.

View all 16 references / Add more references