@article{Durand:2015vn,
    Abstract = {We study the extension of dependence logic {\$}{\$}{$\backslash$}mathcal {\{}D{\}}{\$}{\$}by a majority quantifier {\$}{\$}{$\backslash$}mathsf{\{}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, {\$}{\$}{$\backslash$}mathcal {\{}D{\}}({$\backslash$}mathsf{\{}M{\}}){\$}{\$}captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of {\$}{\$}{$\backslash$}mathcal {\{}D{\}}({$\backslash$}mathsf{\{}M{\}}){\$}{\$}.},
    Author = {Durand, Arnaud and Ebbing, Johannes and Kontinen, Juha and Vollmer, Heribert},
    Date = {2015/09/01},
    File = {Dependence Logic with a Majority Quantifier - Durand2015\_Article\_DependenceLogicWithAMajorityQu.pdf},
    ISBN = {1572-9583},
    Journal = {Journal of Logic, Language and Information},
    Number = {3},
    Pages = {289--305},
    Title = {Dependence Logic with a Majority Quantifier},
    URL = {https://doi.org/10.1007/s10849-015-9218-3},
    Volume = {24},
    Year = {2015},
    bdsk-url-1 = {https://doi.org/10.1007/s10849-015-9218-3},
    date-added = {2022-07-01 12:35:44 +0200},
    date-modified = {2022-07-01 12:35:44 +0200},
    id = {Durand2015},
    doi = {10.1007/s10849-015-9218-3}
}

@article{Durand:2015vn, Abstract = {We study the extension of dependence logic {\$}{\$}{$\backslash$}mathcal {{}D{}}{\$}{\$}by a majority quantifier {\$}{\$}{$\backslash$}mathsf{{}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, {\$}{\$}{$\backslash$}mathcal {{}D{}}({$\backslash$}mathsf{{}M{}}){\$}{\$}captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of {\$}{\$}{$\backslash$}mathcal {{}D{}}({$\backslash$}mathsf{{}M{}}){\$}{\$}.}, Author = {Durand, Arnaud and Ebbing, Johannes and Kontinen, Juha and Vollmer, Heribert}, Date = {2015/09/01}, File = {Dependence Logic with a Majority Quantifier - Durand2015_Article_DependenceLogicWithAMajorityQu.pdf}, ISBN = {1572-9583}, Journal = {Journal of Logic, Language and Information}, Number = {3}, Pages = {289--305}, Title = {Dependence Logic with a Majority Quantifier}, URL = {https://doi.org/10.1007/s10849-015-9218-3}, Volume = {24}, Year = {2015}, bdsk-url-1 = {https://doi.org/10.1007/s10849-015-9218-3}, date-added = {2022-07-01 12:35:44 +0200}, date-modified = {2022-07-01 12:35:44 +0200}, id = {Durand2015}, doi = {10.1007/s10849-015-9218-3} }