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 (2011)
| Abstract | We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier $\most^1$ is not definable in second-order logic. | |||||||||
| Keywords | generalized quantifiers second-order generalized quantifiers collective quantification definability computational complexity | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesJuha Kontinen (2006). The Hierarchy Theorem for Second Order Generalized Quantifiers. Journal of Symbolic Logic 71 (1):188 - 202.
Johan van Benthem & Dag Westerståhl (1995). Directions in Generalized Quantifier Theory. Studia Logica 55 (3):389-419.
Lauri Hella (1996). Logical Hierarchies in PTIME. Information and Computation 129 (1):1--19.
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.
Wiebe Van Der Hoek & Maarten De Rijke (1993). Generalized Quantifiers and Modal Logic. Journal of Logic, Language and Information 2 (1).
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.
Lauri Hella, Kerkko Luosto & Jouko Väänänen (1996). The Hierarchy Theorem for Generalized Quantifiers. Journal of Symbolic Logic 61 (3):802-817.
Georg Gottlob (1997). Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures. Journal of Symbolic Logic 62 (2):545-574.
Jakub Szymanik & Marcin Zajenkowski (2009). Improving Methodology of Quantifier Comprehension Experiments. Neuropsychologia 47 (12):2682--2683.
Peter Fritz (forthcoming). Modal Ontology and Generalized Quantifiers. Journal of Philosophical Logic.
K. Luosto (1999). Ramsey Theory is Needed for Solving Definability Problems of Generalized Quantifiers. 1754:121--134.
M. Mostowski (1995). Quantifiers Definable by Second Order Means. In M. Krynicki, M. Mostowski & L. Szczerba (eds.), Quantifiers: Logics, Models and Computation. Kluwer Academic Publishers.
Heribert Vollmer (1999). A Generalized Quantifier Concept in Computational Complexity Theory. In Generalized Quantifiers and Computation (Aix-En-Provence, 1997). Springer.
Per Lindström (1966). First Order Predicate Logic with Generalized Quantifiers. Theoria 32:186--195.
Analytics
Monthly downloads |
Added to index2011-05-31Total downloads10 ( #106,238 of 549,068 )Recent downloads (6 months)1 ( #63,185 of 549,068 )How can I increase my downloads? |
My notes
Discussion
