Bisimulation Equivalence of a BPP and a Finite State System can be Decided in Polynomial Time

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F04%3A00010337" target="_blank" >RIV/61989100:27240/04:00010337 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Bisimulation Equivalence of a BPP and a Finite State System can be Decided in Polynomial Time
Popis výsledku v původním jazyce
In this paper we consider the problem of deciding bisimulation equivalence of a BPP and a finite-state system. We show that the problem can be solved in polynomial time and we present an algorithm deciding the problem in time O(n^4). The algorithm also constructs for each state of the finite-state system a `symbolic' semilinear representation of the set of all states of the BPP system which are bisimilar with this state.
Název v anglickém jazyce
Bisimulation Equivalence of a BPP and a Finite State System can be Decided in Polynomial Time
Popis výsledku anglicky
In this paper we consider the problem of deciding bisimulation equivalence of a BPP and a finite-state system. We show that the problem can be solved in polynomial time and we present an algorithm deciding the problem in time O(n^4). The algorithm also constructs for each state of the finite-state system a `symbolic' semilinear representation of the set of all states of the BPP system which are bisimilar with this state.

Projekt
<a href="/cs/project/GA201%2F03%2F1161" target="_blank" >GA201/03/1161: Verifikace nekonečně stavových systémů</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

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ů

Název statě ve sborníku
Proceedings of Infinity 2004 (A Satellite Workshop of CONCUR 2004)
ISBN
—
ISSN
—
e-ISSN
—
Počet stran výsledku
9
Strana od-do
73-81
Název nakladatele
Springer-Verlag
Místo vydání
Londýn
Místo konání akce
Londýn
Datum konání akce
28. 9. 2004
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)