Bisimilarity of One-Counter Processes Is PSPACE-Complete
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Bisimilarity of One-Counter Processes Is PSPACE-Complete
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0567" target="_blank" >1M0567: Centre for Applied Cybernetics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
CONCUR 2010 - Concurrency Theory
ISBN
978-3-642-15374-7
ISSN
0302-9743
e-ISSN
—
Number of pages
15
Pages from-to
—
Publisher name
Springer-Verlag Berlin Heidelberg
Place of publication
Berlin Heidelberg
Event location
Paris, France
Event date
Aug 31, 2010
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000285373500013