Bisimilarity of One-Counter Processes Is PSPACE-Complete

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F10%3A86075810" target="_blank" >RIV/61989100:27240/10:86075810 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Bisimilarity of One-Counter Processes Is PSPACE-Complete
Popis výsledku v původním jazyce
A one-counter automaton is a pushdown automaton over a singleton stack alphabet. We prove that the bisimilarity of processes generated by nondeterministic one-counter automata (with no e-steps) is in PSPACE. This improves the previously known decidability result (Jancar 2000) and matches the known PSPACE lower bound (Srba 2009). We add the PTIME completeness result for deciding regularity (i.e. finiteness up to bisimilarity) of one-counter processes.
Název v anglickém jazyce
Bisimilarity of One-Counter Processes Is PSPACE-Complete
Popis výsledku anglicky
A one-counter automaton is a pushdown automaton over a singleton stack alphabet. We prove that the bisimilarity of processes generated by nondeterministic one-counter automata (with no e-steps) is in PSPACE. This improves the previously known decidability result (Jancar 2000) and matches the known PSPACE lower bound (Srba 2009). We add the PTIME completeness result for deciding regularity (i.e. finiteness up to bisimilarity) of one-counter processes.

Projekt
<a href="/cs/project/1M0567" target="_blank" >1M0567: Centrum aplikované kybernetiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2010
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ů

Podobné výsledky(10)