A Characterisation Theorem for Two−Way Bisimulation−Invariant Monadic Least Fixpoint Logic Over Finite Structures

Abstract

A seminal theorem by van Benthem characterises the bisimulation-invariant fragment of First Order Logic (FOL) in terms of Modal Logic. Similarly, Janin and Walukiewicz have shown that the bisimulation-invariant fragment of Monadic Second Order Logic (MSO) corresponds precisely to the (modal) mu-calculus. Notably, neither argument immediately carries over when only considering finite structures. In the case of FOL, Rosen provided an alternative proof, which also works over finite structures. However, such characterisations for any logic more expressive than FOL over finite structures have remained long-standing open problems. In this paper, we prove such a characterisation for parameter-free Monadic Least Fixpoint Logic, a well-known logic in between FOL and MSO. In particular, we show that, over finite structures, every two-way bisimulation-invariant formula in this logic is equivalent to a formula in the two-way mu-calculus and vice versa.