Abstract
We study the extension of dependence logic \ by a majority quantifier \ over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, \\) captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of \\).
Keywords Dependence logic  Dependence atom  Team semantics  Logic  Dependence  Complexity theory  Expressivity  Second order logic  Counting hierarchy  Majority
Categories (categorize this paper)
ISBN(s)
DOI 10.1007/s10849-015-9218-3
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,436
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

Dependence and Independence.Erich Grädel & Jouko Väänänen - 2013 - Studia Logica 101 (2):399-410.
On Definability in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2009 - Journal of Logic, Language and Information 18 (3):317-332.

View all 16 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Generalized Quantifiers in Dependence Logic.Fredrik Engström - 2012 - Journal of Logic, Language and Information 21 (3):299-324.
On Definability in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2009 - Journal of Logic, Language and Information 18 (3):317-332.
A Double Team Semantics for Generalized Quantifiers.Antti Kuusisto - 2015 - Journal of Logic, Language and Information 24 (2):149-191.
Epistemic Operators in Dependence Logic.Pietro Galliani - 2013 - Studia Logica 101 (2):367-397.
Dependence Logic: A Survey of Some Recent Work.Juha Kontinen - 2013 - Philosophy Compass 8 (10):950-963.
A Remark on Negation in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2011 - Notre Dame Journal of Formal Logic 52 (1):55-65.
Axiomatizing First-Order Consequences in Dependence Logic.Juha Kontinen & Jouko Väänänen - 2013 - Annals of Pure and Applied Logic 164 (11):1101-1117.
The Dynamification of Modal Dependence Logic.Pietro Galliani - 2013 - Journal of Logic, Language and Information 22 (3):269-295.

Analytics

Added to PP index
2015-06-25

Total views
13 ( #772,591 of 2,519,857 )

Recent downloads (6 months)
1 ( #406,012 of 2,519,857 )

How can I increase my downloads?

Downloads

My notes