Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F13%3A86088903" target="_blank" >RIV/61989100:27240/13:86088903 - isvavai.cz</a>
Result on the web
<a href="http://www.lmcs-online.org/ojs/viewarticle.php?id=1216" target="_blank" >http://www.lmcs-online.org/ojs/viewarticle.php?id=1216</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.2168/LMCS-9(1:10)2013" target="_blank" >10.2168/LMCS-9(1:10)2013</a>
Alternative languages
Result language
angličtina
Original language name
Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
Original language description
Burkart, Caucal, Steffen (1995) showed a procedure deciding bisimulation equivalence of processes in Basic Process Algebra (BPA), i.e. of sequential processes generated by context-free grammars. They improved the previous decidability result of Christensen, Hüttel, Stirling (1992), since their procedure has obviously an elementary time complexity and the authors claim that a close analysis would reveal a double exponential upper bound. Here a self-contained direct proof of the membership in 2-ExpTime isgiven. This is done via a Prover-Refuter game which shows that there is an alternating Turing machine deciding the problem in exponential space. The proof uses similar ingredients (size-measures, decompositions, bases) as the previous proofs, but one new simplifying factor is an explicit addition of infinite regular strings to the state space. An auxiliary claim also shows an explicit exponential upper bound on the equivalence level of nonbisimilar normed BPA processes. The importance o
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
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
Name of the periodical
Logical Methods in Computer Science
ISSN
1860-5974
e-ISSN
—
Volume of the periodical
9
Issue of the periodical within the volume
1:10
Country of publishing house
DE - GERMANY
Number of pages
19
Pages from-to
1-19
UT code for WoS article
000317894100005
EID of the result in the Scopus database
—