Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F19%3A73595314" target="_blank" >RIV/61989592:15310/19:73595314 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1109/LICS.2019.8785848" target="_blank" >http://dx.doi.org/10.1109/LICS.2019.8785848</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/LICS.2019.8785848" target="_blank" >10.1109/LICS.2019.8785848</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

Popis výsledku v původním jazyce

Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity upper bound for this famous problem, in the equivalent setting of first-order grammars. This ACKERMANN upper bound is optimal, and we also show that strong bisimilarity is primitive-recursive when the number of states of the automata is fixed.

Název v anglickém jazyce

Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

Popis výsledku anglicky

Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity upper bound for this famous problem, in the equivalent setting of first-order grammars. This ACKERMANN upper bound is optimal, and we also show that strong bisimilarity is primitive-recursive when the number of states of the automata is fixed.

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/GA18-11193S" target="_blank" >GA18-11193S: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy</a><br>

Návaznosti

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

Rok uplatnění

2019

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

Proceedings - Symposium on Logic in Computer Science Volume 2019

ISBN

978-1-72813-608-0

ISSN

1043-6871

e-ISSN

—

Počet stran výsledku

12

Strana od-do

1-12

Název nakladatele

IEEE Computer Society Press

Místo vydání

New York

Místo konání akce

Vancouver

Datum konání akce

24. 6. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

000502349000057