Publication details

Bisimulation invariant monadic-second order logic in the finite

Investor logo


Year of publication 2020
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Web journal web page
Keywords Bisimulation; Monadic second-order logic; Composition method
Description We consider bisimulation-invariant monadic second-order logic over various classes of finite transition systems. We present several combinatorial characterisations of when the expressive power of this fragment coincides with that of the modal u-calculus. Using these characterisations we prove for some simple classes of transition systems that this is indeed the case. In particular, we show that, over the class of all finite transition systems with Cantor-Bendixson rank at most k, bisimulation-invariant MSO coincides with L.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info