Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

912 questions

1k answers


441 users

0 votes

Hi, I have doubt regarding Bisimulation. If we are asked to find Greatest Simulation first then followed by Greatest Bisimulation, can we use Greatest simulation's result and use that result to find Greatest Bisimulation (assign B1 to Greatest Simulation Result instead of starting from B0 ). Because if its bisimulated,  then K1<=K2 and K2<=K1.  Can we use the below Greatest Simulation Result to find Greatest Bisimulation or Should we start from B0? Could you please help me on this ?

in # Study-Organisation (Master) by (1.1k points)

1 Answer

+1 vote
Best answer
It depends: If there is no simulation relation, then there is also no bisimulation relation since the bisimulation relation would also be a simulation relation. Hence, if there is no simulation relation, you don't have to compute the greatest bisimulation relation since it follows immediately that there is no bisimulation relation.

If there is no bisimulation relation, there may still be a simulation relation, and even K1 may simulate K2 and K2 may simulate K1 in that case (see slide 42 for such an example).

If there is a bisimulation relation, it is also a simulation relation, but not necessarily the greatest one. So, you would still have to compute the greatest one that must then exist.

The particular intermediate steps cannot really be reused, except for the initial relation where state pairs with the same labels are constructed. That one is the same in these cases. Also the simulation diagrams are the same for all computations, but they are used in different ways.
by (142k points)
selected by
Thank you, Professor. I got it.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Aug 15, 2022 in # Study-Organisation (Master) by Yedhukrishna (1.1k points)
Imprint | Privacy Policy