Dependence logic with a majority quantifier

2011/09/22 by Arnaud Durand, Durand, Arnaud, Johannes Ebbing +5
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #cs.LO #math.LO

paper · pdf · doi:10.48550/arxiv.1109.4750

arxiv created 2013/03/08 · arxiv updated 2013/03/11

Abstract

We study the extension of dependence logic D by a majority quantifier M 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, D(M) captures the complexity class counting hierarchy.

Related

• Dependence Logic with Generalized Quantifiers: Axiomatizations
• Hierarchies in Dependence Logic
• Characterizing Quantifier Extensions of Dependence Logic
• Team Semantics and Recursive Enumerability
• Boolean Dependence Logic and Partially-Ordered Connectives