A Spectrum of Approximate Probabilistic Bisimulations

RWTH Publications (RWTH Aachen)

Abstract

This paper studies various notions of approximate probabilistic bisimulation on labeled Markov chains (LMCs). We introduce approximate versions of weak and branching bisimulation, as well as a notion of $\varepsilon$-perturbed bisimulation that relates LMCs that can be made (exactly) probabilistically bisimilar by small perturbations of their transition probabilities. We explore how the notions interrelate and establish their connections to other well-known notions like $\varepsilon$-bisimulation.

Authors 5

1. Timm Spork

   Technische Universität Dresden

   Affiliation as printed

   Technische Universität Dresden, Dresden, Germany

2. Christel Baier

   Technische Universität Dresden

   Affiliation as printed

   Technische Universität Dresden, Dresden, Germany

3. Joost-Pieter Katoen Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

4. Jakob Piribauer

   Technische Universität Dresden · Leipzig University

   Affiliation as printed

   Technische Universität Dresden, Dresden, Germany

   Universität Leipzig, Leipzig, Germany

5. Tim Quatmann Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany