Bisimulation equivalence of first-order grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F14%3A86092897" target="_blank" >RIV/61989100:27240/14:86092897 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-662-43951-7_20" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-662-43951-7_20</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-43951-7_20" target="_blank" >10.1007/978-3-662-43951-7_20</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bisimulation equivalence of first-order grammars

Popis výsledku v původním jazyce

A decidability proof for bisimulation equivalence of first- order grammars (i.e., finite sets of labelled rules for rewriting roots of first-order terms) is presented. The result, generalizing the decidability of the DPDA (deterministic pushdown automata) equivalence, is equivalent to the result achieved by Senizergues (1998, 2005) in the framework of equational graphs, or of PDA with restricted epsilon-steps, but the framework of classical first-order terms seems to be particularly useful for providinga concise proof that should be understandable for a wider audience.

Název v anglickém jazyce

Bisimulation equivalence of first-order grammars

Popis výsledku anglicky

A decidability proof for bisimulation equivalence of first- order grammars (i.e., finite sets of labelled rules for rewriting roots of first-order terms) is presented. The result, generalizing the decidability of the DPDA (deterministic pushdown automata) equivalence, is equivalent to the result achieved by Senizergues (1998, 2005) in the framework of equational graphs, or of PDA with restricted epsilon-steps, but the framework of classical first-order terms seems to be particularly useful for providinga concise proof that should be understandable for a wider audience.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F11%2F0340" target="_blank" >GAP202/11/0340: Modelování a verifikace paralelních systémů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

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

Lecture Notes in Computer Science. Volume 8573

ISBN

978-3-662-43950-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

232-243

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Copenhagen

Datum konání akce

8. 7. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

—