Bisimulation Invariant Monadic-Second Order Logic in the Finite
Authors
BLUMENSATH, Achim (276 Germany, guarantor, belonging to the institution) and Felix WOLF (276 Germany)
Edition
Dagstuhl, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, p. 1-13, 13 pp. 2018
Publisher
Schloss Dagstuhl
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
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 mu-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_mu.
Links
GA17-01035S, research and development project
Name: Algebraická teorie jazyků pro nekonečné stromy