Extensions of MSO and the monadic counting hierarchy
In this paper we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most(1). We consider first certain sublogics of FO(Most(1)) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO(R(n))(n is an element of z+), where R(n) is the nth vectorization of R, corresponds to the Delta(0)-fragment of arithmetic. Then we show that FO(Most(1)) >= MSO(R(n))(n is an element of z+) and that, on unary vocabularies, FO(Most(1)) collapses to uniform-TC(0). Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most(1)) over the empty vocabulary. On the other hand, over strings, FO(Most(1)) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most(1)) can express problems complete via first-order reductions for each level of the counting hierarchy. (C) 2010 Elsevier Inc. All rights reserved.
counting hierarchy majority quantifier monadic second-order logic second-order generalized quantifier