On vectorizations of unary generalized quantifiers

Archive for Mathematical Logic 51 (3-4):241-255 (2012)
  Copy   BIBTEX

Abstract

Vectorization of a class of structures is a natural notion in finite model theory. Roughly speaking, vectorizations allow tuples to be treated similarly to elements of structures. The importance of vectorizations is highlighted by the fact that if the complexity class PTIME corresponds to a logic with reasonable syntax, then it corresponds to a logic generated via vectorizations by a single generalized quantifier (Dawar in J Log Comput 5(2):213–226, 1995). It is somewhat surprising, then, that there have been few systematic studies of the expressive power of vectorizations of various quantifiers. In the present paper, we consider the simplest case: the cardinality quantifiers C S . We show that, in general, the expressive power of the vectorized quantifier logic ${{\rm FO}(\{{\mathsf C}_S^{(n)}\, | \, n \in \mathbb{Z}_+\})}$ is much greater than the expressive power of the non-vectorized logic FO(C S )

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,391

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Beyond the Frege boundary.Edward L. Keenan - 1992 - Linguistics and Philosophy 15 (2):199-221.
Hierarchies of monadic generalized quantifiers.Kerkko Luosto - 2000 - Journal of Symbolic Logic 65 (3):1241-1263.
The Hierarchy Theorem for Second Order Generalized Quantifiers.Juha Kontinen - 2006 - Journal of Symbolic Logic 71 (1):188 - 202.
Dynamic Generalized Quantifiers.Martin van den Berg - 1996 - In J. van der Does & Van J. Eijck (eds.), Quantifiers, Logic, and Language. Stanford University. pp. 63--94.
Generalized Quantifiers, and Beyond.Hanoch Ben-Yami - 2009 - Logique Et Analyse (208):309-326.
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.
Quantification.Anna Szabolcsi - 2010 - Cambridge University Press.
Unary quantifiers on finite models.Jouko Väänänen - 1997 - Journal of Logic, Language and Information 6 (3):275-304.

Analytics

Added to PP
2013-10-27

Downloads
83 (#149,026)

6 months
1 (#451,971)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Definability hierarchies of general quantifiers.Lauri Hella - 1989 - Annals of Pure and Applied Logic 43 (3):235.
Hierarchies of monadic generalized quantifiers.Kerkko Luosto - 2000 - Journal of Symbolic Logic 65 (3):1241-1263.
δ-Logics and generalized quantifiers.J. A. Makowsky - 1976 - Annals of Mathematical Logic 10 (2):155.

View all 13 references / Add more references