| KUČERA, Antonín and 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, p. 594-609. ISBN 3-540-44043-7. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{405201,
author = {Kučera, Antonín and Mayr, Richard},
address = {Berlin},
booktitle = {Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)},
keywords = {verification; concurrency; weak bisimilarity; infinite-state systems},
language = {eng},
location = {Berlin},
isbn = {3-540-44043-7},
pages = {594-609},
publisher = {Springer},
title = {Why is Simulation Harder Than Bisimulation?},
year = {2002}
}
TY - JOUR
ID - 405201
AU - Kučera, Antonín - Mayr, Richard
PY - 2002
TI - Why is Simulation Harder Than Bisimulation?
PB - Springer
CY - Berlin
SN - 3540440437
KW - verification
KW - concurrency
KW - weak bisimilarity
KW - infinite-state systems
N2 - 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.
ER -
KUČERA, Antonín and Richard MAYR. Why is Simulation Harder Than Bisimulation? L. Brim, P. Jancar, M. Kretinsky, A. Kucera (Eds.). In \textit{Proceedings of 13th International Conference on Concurrency Theory (CONCUR 2002)}. Berlin: Springer, 2002, p.~594-609. ISBN~3-540-44043-7.
|
