D 2018

Bisimulation Invariant Monadic-Second Order Logic in the Finite

BLUMENSATH, Achim a Felix WOLF

Základní údaje

Originální název

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Autoři

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

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00101061

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-076-7

ISSN

DOI

EID Scopus

2-s2.0-85049803926

Klíčová slova anglicky

bisimulation; monadic second-order logic; composition method

Štítky

Změněno: 30. 4. 2019 09:59, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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