Working Seminar on Formal Models, Discrete Structures, and Algorithms

Computational homotopy theory

Jan Krčál (Saarland University)

When: February 11, 3:30pm

Where: room G2.91b/G215


In contrast to the usual understanding of probabilistic systems as stochastic processes, these systems have recently been also regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as systems with uncountable state and action spaces. We argue on several examples of applications that our definition refines understanding of behavioural equivalences of probabilistic systems. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of infinite systems such as non-Markovian continuous-time stochastic processes.