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%2F20%3A00114229" target="_blank" >RIV/00216224:14330/20:00114229 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0304397520301389?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0304397520301389?via%3Dihub</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2020.03.001" target="_blank" >10.1016/j.tcs.2020.03.001</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 u-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.

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

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

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í

2020

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 periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

823

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

26-43

Kód UT WoS článku

000530067900002

EID výsledku v databázi Scopus

2-s2.0-85081273402