Order-Invariant MSO is Stronger than Counting MSO in the Finite

Tobias Ganzow, Sasha Rubin

We compare the expressiveness of two extensions of monadic second-order logic (MSO) over the class of finite structures. The first, counting monadic second-order logic (CMSO), exte…