Bisimulation Invariant Monadic-Second Order Logic in the Finite

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Original language 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 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA17-01035S" target="_blank" >GA17-01035S: Algebraic Language Theory for Infinite Trees</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Article name in the collection

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

ISBN

9783959770767

ISSN

1868-8969

e-ISSN

—

Number of pages

13

Pages from-to

1-13

Publisher name

Schloss Dagstuhl

Place of publication

Dagstuhl

Event location

Dagstuhl

Event date

Jan 1, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—