A Dichotomy in Classifying Quantifiers for Finite Models
Journal of Symbolic Logic 70 (4):1297 - 1324 (2005)
| Abstract | We consider a family U of finite universes. The second order existential quantifier QR. means for each U ϵ U quantifying over a set of n(R)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every QR. either QR is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(QR) (first order logic plus the quantifier QR) is undecidable | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesSaharon Shelah (2000). On Quantification with a Finite Universe. Journal of Symbolic Logic 65 (3):1055-1075.
Jörg Flum, Matthias Schiehlen & Jouko Väänänen (1999). Quantifiers and Congruence Closure. Studia Logica 62 (3):315-340.
Jouko Väänänen (1997). Unary Quantifiers on Finite Models. Journal of Logic, Language and Information 6 (3):275-304.
Juha Kontinen (2006). The Hierarchy Theorem for Second Order Generalized Quantifiers. Journal of Symbolic Logic 71 (1):188 - 202.
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.
Lauri Hella (1996). Logical Hierarchies in PTIME. Information and Computation 129 (1):1--19.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Oleg Pikhurko & Oleg Verbitsky (2005). Descriptive Complexity of Finite Structures: Saving the Quantifier Rank. Journal of Symbolic Logic 70 (2):419 - 450.
Georg Gottlob (1997). Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures. Journal of Symbolic Logic 62 (2):545-574.
Stephen Donaho (2002). Standard Quantification Theory in the Analysis of English. Journal of Philosophical Logic 31 (6):499-526.
Yuri Gurevich & Saharon Shelah (1996). On Finite Rigid Structures. Journal of Symbolic Logic 61 (2):549-562.
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.
Anders Andersson (2002). On Second-Order Generalized Quantifiers and Finite Structures. Annals of Pure and Applied Logic 115 (1--3):1--32.
Marcin Mostowski (1998). Computational Semantics for Monadic Quantifiers. Journal of Applied Non--Classical Logics 8:107--121.
Lauri Hella, Kerkko Luosto & Jouko Väänänen (1996). The Hierarchy Theorem for Generalized Quantifiers. Journal of Symbolic Logic 61 (3):802-817.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-24Total downloads1 ( #274,830 of 549,090 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
