Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
Popis výsledku anglicky
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
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2013
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ů
Údaje specifické pro druh výsledku
Název periodika
Logical Methods in Computer Science
ISSN
1860-5974
e-ISSN
—
Svazek periodika
9
Číslo periodika v rámci svazku
1:10
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
19
Strana od-do
1-19
Kód UT WoS článku
000317894100005
EID výsledku v databázi Scopus
—