Bisimulation Invariant Monadic-Second Order Logic in the Finite

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00101061" target="_blank" >RIV/00216224:14330/18:00101061 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117" target="_blank" >10.4230/LIPIcs.ICALP.2018.117</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-01035S" target="_blank" >GA17-01035S: Algebraická teorie jazyků pro nekonečné stromy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic

ISBN

9783959770767

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

13

Strana od-do

1-13

Název nakladatele

Schloss Dagstuhl

Místo vydání

Dagstuhl

Místo konání akce

Dagstuhl

Datum konání akce

1. 1. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—