Some Problems Related to Bisimilarity on BPP
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F04%3A00010321" target="_blank" >RIV/61989100:27240/04:00010321 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Some Problems Related to Bisimilarity on BPP
Popis výsledku v původním jazyce
Jančar has in 2003 shown that bisimilarity on Basic Parallel Processes (BPP) can be decided in polynomial space. Bisimilarity is studied on various subclasses of BPP as well. We present summary of known complexity bounds of some such bisimilarity problems. Moreover is here shown that deciding regularity of a BPP is PSPACE-complete. So far this problem was only known to be PSPACE-hard.
Název v anglickém jazyce
Some Problems Related to Bisimilarity on BPP
Popis výsledku anglicky
Jančar has in 2003 shown that bisimilarity on Basic Parallel Processes (BPP) can be decided in polynomial space. Bisimilarity is studied on various subclasses of BPP as well. We present summary of known complexity bounds of some such bisimilarity problems. Moreover is here shown that deciding regularity of a BPP is PSPACE-complete. So far this problem was only known to be PSPACE-hard.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
JC - Počítačový hardware a software
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F03%2F1161" target="_blank" >GA201/03/1161: Verifikace nekonečně stavových systémů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2004
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 statě ve sborníku
Proceedings of Movep'04
ISBN
—
ISSN
—
e-ISSN
—
Počet stran výsledku
7
Strana od-do
96-102
Název nakladatele
Université Libre de Bruxelles
Místo vydání
Brussels
Místo konání akce
Brussels
Datum konání akce
1. 1. 2004
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—