Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

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

Result on the web

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

Result language

angličtina

Original language name

Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

Original language description

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.

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/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>

Continuities

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

Publication year

2019

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

Proceedings - Symposium on Logic in Computer Science Volume 2019

ISBN

978-1-72813-608-0

ISSN

1043-6871

e-ISSN

—

Number of pages

12

Pages from-to

1-12

Publisher name

IEEE Computer Society Press

Place of publication

New York

Event location

Vancouver

Event date

Jun 24, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000502349000057