Fall 2016

Simulation and Bisimulations for Probabilistic Systems, and their Logical Contents

Monday, November 7th, 2016 2:30 pm3:00 pm

Add to Calendar

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.