Dependence Logic with a Majority Quantifier

作者：Durand Arnaud; Ebbing Johannes^*; Kontinen Juha; Vollmer Heribert

来源：Journal of Logic, Language and Information, 2015, 24(3): 289-305.

DOI：10.1007/s10849-015-9218-3

• Dependence logic
• Dependence atom
• Team semantics
• Logic
• Dependence
• Complexity theory
• Expressivity
• Second order logic
• Counting hierarchy
• Majority

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 D(M).

• 出版日期2015-9