Why is Simulation Harder Than Bisimulation?

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Why is Simulation Harder Than Bisimulation?
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Infinite state concurrent systems - models and verification</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2002
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)
ISBN
3-540-44043-7
ISSN
—
e-ISSN
—
Number of pages
16
Pages from-to
594
Publisher name
Springer
Place of publication
Berlin
Event location
August 20-23, 2002, Brno, Czech Republic
Event date
Jan 1, 2002
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)