Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F02%3A00004665" target="_blank" >RIV/00216224:14330/02:00004665 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time
Popis výsledku v původním jazyce
We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, theseare the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.
Název v anglickém jazyce
Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time
Popis výsledku anglicky
We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, theseare the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
JC - Počítačový hardware a software
OECD FORD obor
—

Projekt
<a href="/cs/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Nekonečně stavové souběžné systémy - modely a verifikace</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2002
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)