On vectorizations of unary generalized quantifiers

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

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 )
Keywords Generalized quantifier  Vectorization  Topological dynamics
Categories (categorize this paper)
DOI 10.1007/s00153-011-0262-7
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,545
External links

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

Add more references

Citations of this work BETA

No citations found.

Add more citations

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 index
2013-10-27

Total views
40 ( #186,365 of 2,325,475 )

Recent downloads (6 months)
7 ( #215,232 of 2,325,475 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature