KUČERA, Antonín a Richard MAYR. Why is Simulation Harder Than Bisimulation? L. Brim, P. Jancar, M. Kretinsky, A. Kucera (Eds.). In Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002). Berlin: Springer, 2002. s. 594-609. ISBN 3-540-44043-7.
Další formáty:   BibTeX LaTeX RIS
Zá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.).
Vydání Berlin, Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002), s. 594-609, 2002.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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
Štítky concurrency, infinite-state systems, verification, weak bisimilarity
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 22. 11. 2006 17:28.
Anotace
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 VaVNázev: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Standardní projekty
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
VytisknoutZobrazeno: 23. 10. 2019 07:08