Dependence logic with a majority quantifier
  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. 
Arnaud Durand, Johannes Ebbing, Juha Kontinen and Heribert Vollmer
cs.LO math.LO