Why is Simulation Harder Than Bisimulation?

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KUČERA Antonín MAYR Richard

Year of publication 2002
Type Article in Proceedings
Conference Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Keywords verification; concurrency; weak bisimilarity; infinite-state systems
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 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.