2002
Why is Simulation Harder Than Bisimulation?
KUČERA, Antonín a Richard MAYRZákladní údaje
Originální název
Why is Simulation Harder Than Bisimulation?
Autoři
KUČERA, Antonín (203 Česká republika, garant) a Richard MAYR (276 Německo)
L. Brim, P. Jancar, M. Kretinsky, A. Kucera (Eds.).
L. Brim, P. Jancar, M. Kretinsky, A. Kucera (Eds.).
Vydání
Berlin, Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002), s. 594-609, 2002
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
20206 Computer hardware and architecture
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Kód RIV
RIV/00216224:14330/02:00006376
Organizační jednotka
Fakulta informatiky
ISBN
3-540-44043-7
Klíčová slova anglicky
verification; concurrency; weak bisimilarity; infinite-state systems
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 22. 11. 2006 17:28, prof. RNDr. Antonín Kučera, Ph.D.
Anotace
V originále
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 to construct 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ávaznosti
| GA201/00/0400, projekt VaV |
| ||
| MSM 143300001, záměr |
|