Weak MSO: Automata and Expressiveness Modulo Bisimilarity

Facundo Carreiro, Alessandro Facchini, Yde Venema +1

We prove that the bisimulation-invariant fragment of weak monadic second-order logic (WMSO) is equivalent to the fragment of the modal $\mu$-calculus where the application of the lea…