Bisimulation Invariant Monadic-Second Order Logic in the Finite
Autoři
BLUMENSATH, Achim (276 Německo, garant, domácí) a Felix WOLF (276 Německo)
Vydání
Dagstuhl, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, od s. 1-13, 13 s. 2018
Nakladatel
Schloss Dagstuhl
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
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.
Návaznosti
GA17-01035S, projekt VaV
Název: Algebraická teorie jazyků pro nekonečné stromy
Investor: Grantová agentura ČR, Algebraic Language Theory for Infinite Trees