Abstract
Simulation equivalence and bisimulation equivalence are some of most common notions of semantic equivalence used in the framework of process algebras. Many recent results in this area indicate that, for almost any meaningful class of concurrent systems, checking simulation equivalence has a higher complexity than checking bisimulation equivalence. Why is this the case ? In this talk we give an overview over several results that show the connections between simulation and bisimulation. First, there is a general abstract one-to-one reduction from simulation problems to bisimulation problems. However, on most classes of systems this reduction is not effective (e.g., for classes of systems where simulation equivalence is undecidable but bisimulation equivalence is decidable). Secondly, there are two different general methods for constructing reductions from bisimulation problems to simulation problems (i.e., in the other direction). These reductions are effective and require only polynomial time. Roughly speaking, the first method works for all classes of systems that can test for non-enabledness of atomic actions (e.g., test for zero in systems with counters), while the second method works for all classes of systems that are closed under parallel composition and synchronization. Nearly all meaningful classes of systems are in one of those two categories.

ASTEC seminar
April 1, 2003

Place: Information technology, Uppsala University
Room: 1113
Time: 15.15-16.00 (+ discussions)

Room 1113 is in building 1, floor 1, room 13 (in the southern part of the building).

Help on how to find ASTEC Seminars.

There will be an extended period for discussions after the seminar.

Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 16.00.