摘要：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.
关键词：dependence logic; counting hierarchy; majority quantifier; second order logic; descriptive complexity; finite model theory
