TY - JOUR

T1 - Dependence logic with a majority quantifier

AU - Durand, Arnaud

AU - Ebbing, Johannes

AU - Kontinen, Juha

AU - Vollmer, Heribert

N1 - Funding Information: The third author was supported by Grants 264917 and 275241 of the Academy of Finland. The second and fourth author were supported by a Grant from DAAD within the PPP programme. The fourth author was also supported by DFG Grant VO 630/6-2.

PY - 2015/9

Y1 - 2015/9

N2 - 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. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of D(M).

AB - 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. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of D(M).

U2 - 10.48550/arXiv.1109.4750

DO - 10.48550/arXiv.1109.4750

M3 - Article

VL - 24

SP - 289

EP - 305

JO - Journal of Logic, Language and Information

JF - Journal of Logic, Language and Information

SN - 0925-8531

ER -