David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Marcelo Arenas, Pablo Barceló & Leonid Libkin (2008). Game-Based Notions of Locality Over Finite Models. Annals of Pure and Applied Logic 152 (1):3-30.
Anuj Dawar, David Richerby & Benjamin Rossman (2008). Choiceless Polynomial Time, Counting and the Cai–Fürer–Immerman Graphs. Annals of Pure and Applied Logic 152 (1):31-50.
Phokion G. Kolaitis & Jouko A. Väänänen (1995). Generalized Quantifiers and Pebble Games on Finite Structures. Annals of Pure and Applied Logic 74 (1):23-75.
Similar books and articles
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. 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
Juha Kontinen (2006). The Hierarchy Theorem for Second Order Generalized Quantifiers. Journal of Symbolic Logic 71 (1):188 - 202.
Georg Gottlob (1997). Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures. Journal of Symbolic Logic 62 (2):545-574.
Johan van Benthem & Dag Westerståhl (1995). Directions in Generalized Quantifier Theory. Studia Logica 55 (3):389-419.
Lauri Hella, Kerkko Luosto & Jouko Väänänen (1996). The Hierarchy Theorem for Generalized Quantifiers. Journal of Symbolic Logic 61 (3):802-817.
Jakub Szymanik (2009). Quantifiers in TIME and SPACE. Computational Complexity of Generalized Quantifiers in Natural Language. Dissertation, University of Amsterdam
Lauri Hella, Jouko Väänänen & Dag Westerståhl (1997). Definability of Polyadic Lifts of Generalized Quantifiers. Journal of Logic, Language and Information 6 (3):305-335.
Martin Otto (1996). The Expressive Power of Fixed-Point Logic with Counting. Journal of Symbolic Logic 61 (1):147-176.
Jakub Szymanik (2010). Almost All Complex Quantifiers Are Simple. In C. Ebert, G. Jäger, M. Kracht & J. Michaelis (eds.), Mathematics of Language 10/11, Lecture Notes in Computer Science 6149. Springer
Jouko Väänänen & Dag Westerståhl (2002). On the Expressive Power of Monotone Natural Language Quantifiers Over Finite Models. Journal of Philosophical Logic 31 (4):327-358.
Wiebe Van Der Hoek & Maarten De Rijke (1993). Generalized Quantifiers and Modal Logic. Journal of Logic, Language and Information 2 (1):19-58.
Livio Robaldo (2010). Independent Set Readings and Generalized Quantifiers. Journal of Philosophical Logic 39 (1):23-58.
Peter Fritz (2013). Modal Ontology and Generalized Quantifiers. Journal of Philosophical Logic 42 (4):643-678.
Marcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Lauri Hella & Kerkko Luosto (1992). The Beth-Closure of L(Qα) is Not Finitely Generated. Journal of Symbolic Logic 57 (2):442 - 448.
Added to index2012-03-18
Total downloads2 ( #511,927 of 1,699,804 )
Recent downloads (6 months)1 ( #362,609 of 1,699,804 )
How can I increase my downloads?