Why is Simulation Harder Than Bisimulation? Antonin Kucera and Richard Mayr
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
onetoone polynomialtime reductions from bisimulation equivalence
tosimulation 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 `nonenabledness' of actions, while our
second method works for all classes of systems that are closed under
synchronization.

concur02@fi.muni.cz 