
From Simulation to Bisimulation and Back
Richard Mayr
AlbertLudwigsUniversity Freiburg, Germany
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 onetoone 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 nonenabledness 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.
Place: Information technology, Uppsala University
Room: 1113
Time: 15.1516.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.
Everyone is welcome !
Updated 25Mar2003 10:31 by Roland Grönroos
email: info at astec.uu.se
Location: http://www.astec.uu.se/Seminars/03/0401.shtml
