[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [moca] On the definition of bisimulation

Hello

sorry if some of my remarks overlap those of Hans.


Pietro Braione wrote:


I have a question about bisimulation.
In many places I found it defined as follows:
A relation R on the states of your favorite
transition system is a bisimulation iff:

1: it is a simulation;
2: its inverse is a simulation.

However there are authors who replace 2 with:

2': it is symmetric.

I have noticed that these authors do not worry
about the fact that the two definitions are not
equivalent. This makes me argue that perhaps it
is not so important assuming one definition or
the other. If effectively it is not, why? Maybe
because they yield the same bisimilarity
equivalence?

Thank you for your kind attention.

Pietro Braione

Yes, on a given transition system the resulting maximal bisimulation is the same in both cases.

However, as you point out, the two definitions are not equivalent. Personally, I prefer the first one -which is also the original definition - because it is more general : according to this definition an arbitrary bisimulation relation doesn't need to be symmetric (nor reflexive, nor transitive). Indeed, when you construct bisimulation relations to show that two processes are equivalent, you generally use minimal, non symmetric bisimulations. So the first definition is handier to use.

Moreover, and more importantly, the first definition allows you to compare different transition systems. It was indeed defined between different transition systems in the original paper of Park (Concurrency and automata on infinite sequences, LNCS 104, 1981.)

-Ilaria



--
***************************************************************

Ilaria Castellani, INRIA, 2004 Route des Lucioles,
BP 93, 06902 Sophia-Antipolis Cedex, FRANCE

Tel.: +33 (0)4 92 38 76 40 Fax: +33 (0)4 92 38 79 98 http://www-sop.inria.fr/mimosa/personnel/Ilaria.Castellani.html ***************************************************************



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list mailto:moca@xxxxxxxxxxxxxxx
http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html