Why is Simulation Harder Than Bisimulation?
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F02%3A00006376" target="_blank" >RIV/00216224:14330/02:00006376 - 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
Why is Simulation Harder Than Bisimulation?
Popis výsledku v původním jazyce
Why is deciding simulation preorder (and simulation equivalence) computationally harder than deciding bisimulation equivalence on almost all known classes of processes? We try to answer this question by describing two general methods that can be used toconstruct direct one-to-one polynomial-time reductions from bisimulation equivalence to simulation preorder (and simulation equivalence). These methods can be applied to many classes of finitely generated transition systems, provided that they satisfy certain abstractly formulated conditions. Roughly speaking, our first method works for all classes of systems that can test for `non-enabledness' of actions, while our second method works for all classes of systems that are closed under synchronization.
Název v anglickém jazyce
Why is Simulation Harder Than Bisimulation?
Popis výsledku anglicky
Why is deciding simulation preorder (and simulation equivalence) computationally harder than deciding bisimulation equivalence on almost all known classes of processes? We try to answer this question by describing two general methods that can be used toconstruct direct one-to-one polynomial-time reductions from bisimulation equivalence to simulation preorder (and simulation equivalence). These methods can be applied to many classes of finitely generated transition systems, provided that they satisfy certain abstractly formulated conditions. Roughly speaking, our first method works for all classes of systems that can test for `non-enabledness' of actions, while our second method works for all classes of systems that are closed under synchronization.
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%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)
Ostatní
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)
ISBN
3-540-44043-7
ISSN
—
e-ISSN
—
Počet stran výsledku
16
Strana od-do
594
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
August 20-23, 2002, Brno, Czech Republic
Datum konání akce
1. 1. 2002
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—