Relativized logspace and generalized quantifiers over finite ordered structures

Journal of Symbolic Logic 62 (2):545-574 (1997)

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]
Keywords generalized quantifiers   Henkin quantifiers   finite model theory   finite structues   expressive power   complexity   oracles   relativization   logarithmic space   logspace   bounded queries
Categories (categorize this paper)
DOI 10.2307/2275546
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 43,049
Through your library

References found in this work BETA

Finite Partially‐Ordered Quantifiers.Herbert B. Enderton - 1970 - Mathematical Logic Quarterly 16 (8):393-397.
Henkin Quantifiers and Complete Problems.Andreas Blass & Yuri Gurevich - 1986 - Annals of Pure and Applied Logic 32 (1):1--16.

View all 6 references / Add more references

Citations of this work BETA

Generalized Quantifiers.Dag Westerståhl - 2008 - Stanford Encyclopedia of Philosophy.
Partially Ordered Connectives and Monadic Monotone Strict Np.Lauri Hella, Merlijn Sevenster & Tero Tulenheimo - 2008 - Journal of Logic, Language and Information 17 (3):323-344.

Add more citations

Similar books and articles

Modal Ontology and Generalized Quantifiers.Peter Fritz - 2013 - Journal of Philosophical Logic 42 (4):643-678.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.
Definability of Polyadic Lifts of Generalized Quantifiers.Lauri Hella, Jouko Väänänen & Dag Westerståhl - 1997 - Journal of Logic, Language and Information 6 (3):305-335.
On Second-Order Generalized Quantifiers and Finite Structures.Anders Andersson - 2002 - Annals of Pure and Applied Logic 115 (1--3):1--32.
Ways of Branching Quantifers.Gila Sher - 1990 - Linguistics and Philosophy 13 (4):393 - 422.
The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.


Added to PP index

Total views
14 ( #573,888 of 2,260,641 )

Recent downloads (6 months)
1 ( #896,656 of 2,260,641 )

How can I increase my downloads?


My notes

Sign in to use this feature