Unary quantifiers on finite models

Abstract
In this paper (except in Section 5) all quantifiers are assumedto be so called simple unaryquantifiers, and all models are assumedto be finite. We give a necessary and sufficientcondition for a quantifier to be definablein terms of monotone quantifiers. For amonotone quantifier we give a necessaryand sufficient condition for beingdefinable in terms of a given set of bounded monotonequantifiers. Finally, we give a necessaryand sufficient condition for a monotonequantifier to be definable in terms of agiven monotone quantifier.Our analysis shows that the quantifierat least one half and its relatives behavedifferently than other monotone quantifiers.
Keywords definability   generalized   quantifiers
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1008209019899
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 27,141
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Game-Based Notions of Locality Over Finite Models.Marcelo Arenas, Pablo Barceló & Leonid Libkin - 2008 - Annals of Pure and Applied Logic 152 (1):3-30.

Add more citations

Similar books and articles
Beyond the Frege Boundary.Edward L. Keenan - 1992 - Linguistics and Philosophy 15 (2):199 - 221.
Scope Dominance with Monotone Quantifiers Over Finite Domains.Gilad Ben-Avi & Yoad Winter - 2004 - Journal of Logic, Language and Information 13 (4):385-402.
A Dichotomy in Classifying Quantifiers for Finite Models.Saharon Shelah & Mor Doron - 2005 - Journal of Symbolic Logic 70 (4):1297 - 1324.
Scope Dominance with Upward Monotone Quantifiers.Alon Altman, Ya'Acov Peterzil & Yoad Winter - 2005 - Journal of Logic, Language and Information 14 (4):445-455.
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.

Monthly downloads

Added to index

2009-01-28

Total downloads

39 ( #131,488 of 2,163,616 )

Recent downloads (6 months)

1 ( #348,040 of 2,163,616 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums