In this talk, I will discuss the different definitions that have been proposed in the literature to express that two states of a probabilistic system are similar (or bisimilar). Different intuitions and purposes led to conceptually various definitions.

I will show that most of the definitions have a logical counterpart, meaning that for each of them there exists a logical formalism which distinguishes two states if, and only if, they are not similar (or bisimilar).

When considering computational properties, the landscape turns out to be rather surprising: some definitions lead to efficient algorithms, while some others to undecidability.

http://www.cs.ox.ac.uk/people/nathanael.fijalkow/Talk/Simons_Bisimulation/