Information And Computation 129 (1):1--19 (1996)
We consider the problem of finding a characterization for polynomial time computable queries on finite structures in terms of logical definability. It is well known that fixpoint logic provides such a characterization in the presence of a built-in linear order, but without linear order even very simple polynomial time queries involving counting are not expressible in fixpoint logic. Our approach to the problem is based on generalized quantifiers. A generalized quantifier isn-ary if it binds any number of formulas, but at mostnvariables in each formula. We prove that, for each natural numbern, there is a query on finite structures which is expressible in fixpoint logic, but not in the extension of first-order logic by any set ofn-ary quantifiers. It follows that the expressive power of fixpoint logic cannot be captured by adding finitely many quantifiers to first-order logic. Furthermore, we prove that, for each natural numbern, there is a polynomial time computable query which is not definable in any extension of fixpoint logic byn-ary quantifiers. In particular, this rules out the possibility of characterizing PTIME in terms of definability in fixpoint logic extended by a finite set of generalized quantifiers
|Keywords||complexity computational descriptive generalized quantifiers|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
Choiceless Polynomial Time, Counting and the Cai–Fürer–Immerman Graphs.Anuj Dawar, David Richerby & Benjamin Rossman - 2008 - Annals of Pure and Applied Logic 152 (1):31-50.
Generalized Quantifiers and Pebble Games on Finite Structures.Phokion G. Kolaitis & Jouko A. Väänänen - 1995 - Annals of Pure and Applied Logic 74 (1):23-75.
A Local Normal Form Theorem for Infinitary Logic with Unary Quantifiers.H. Jerome Keisler & Wafik Boulos Lotfallah - 2005 - Mathematical Logic Quarterly 51 (2):137-144.
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.
Similar books and articles
Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.
Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures.Georg Gottlob - 1997 - Journal of Symbolic Logic 62 (2):545-574.
The Hierarchy Theorem for Generalized Quantifiers.Lauri Hella, Kerkko Luosto & Jouko Väänänen - 1996 - Journal of Symbolic Logic 61 (3):802-817.
Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2009 - Dissertation, University of Amsterdam
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.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Almost All Complex Quantifiers Are Simple.Jakub Szymanik - 2010 - In C. Ebert, G. Jäger, M. Kracht & J. Michaelis (eds.), Mathematics of Language 10/11, Lecture Notes in Computer Science 6149. Springer.
On the Expressive Power of Monotone Natural Language Quantifiers Over Finite Models.Jouko Väänänen & Dag Westerståhl - 2002 - Journal of Philosophical Logic 31 (4):327-358.
Generalized Quantifiers and Modal Logic.Wiebe Van Der Hoek & Maarten De Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
Modal Ontology and Generalized Quantifiers.Peter Fritz - 2013 - Journal of Philosophical Logic 42 (4):643-678.
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
The Beth-Closure of L(Qα) is Not Finitely Generated.Lauri Hella & Kerkko Luosto - 1992 - Journal of Symbolic Logic 57 (2):442 - 448.
Added to index2012-03-18
Total downloads4 ( #636,610 of 2,158,146 )
Recent downloads (6 months)1 ( #356,322 of 2,158,146 )
How can I increase my downloads?