Re: [moca] On the definition of bisimulation

[Hans Huttel <hans@xxxxxxxxx>]

Pietro Braione <braione@xxxxxxxxxxxxxx> wrote:

> This my first post on this mailing list, so I think
> I should introduce myself briefly. I am a phd student
> at Politecnico di Milano, in Italy. My research topic
> is, roughly speaking, models for network- and
> context-aware systems.
>
> 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?

Let us call a bisimulation as defined by the first definition an
I-bisimulation, and a bisimulation as defined by the second definition an
II-bisimulation.

Clearly, any II-bisimulation is also an I-bisimulation.

The symmetric closure of a binary relation R is the set RS = { (a,b) | aRb or bRa }.

A moment's thought should convince you that the symmetric closure of any
I-bisimulation is an II-bisimulation.

Since Tarski's fixed point theorem tells us that the maximal bisimulation
(whatever the definition)  is the union of all bisimulations, the two
definitions give us the same maximal bisimulation.


Hans

--
Hans Hüttel                        | email: hans@xxxxxxxxx
BRICS, Dept. of Computer Science   | WWW: http://www.cs.auc.dk/~hans/
Aalborg University                 | tel.: (+45) 96 35 88 88
Fredrik Bajersvej 7E               | fax: (+45) 98 15 98 89
9220 Aalborg Ø, DENMARK            | Fight spam!  http://www.cauce.org



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