Finite variable logics in descriptive complexity theory

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

Abstract

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.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 101,916

External links

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

Through your library

Similar books and articles

Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
Some aspects of model theory and finite structures.Eric Rosen - 2002 - Bulletin of Symbolic Logic 8 (3):380-403.
Logic in Finite Structures: Definability, Complexity, and Randomness.Scott Weinstein - 2002 - In Dale Jacquette (ed.), A Companion to Philosophical Logic. Malden, MA, USA: Wiley-Blackwell. pp. 332–348.
Computational model theory: an overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
How to define a linear order on finite models.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1997 - Annals of Pure and Applied Logic 87 (3):241-267.
Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
Finite Model Theory and Finite Variable Logics.Eric Barry Rosen - 1995 - Dissertation, University of Pennsylvania

Analytics

Added to PP
2009-01-28

Downloads
67 (#321,151)

6 months
9 (#493,407)

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.
On languages with two variables.Michael Mortimer - 1975 - Mathematical Logic Quarterly 21 (1):135-140.
Definability hierarchies of general quantifiers.Lauri Hella - 1989 - Annals of Pure and Applied Logic 43 (3):235.

View all 15 references / Add more references