Technical Reports
The report FIMU-RS-2014-03
Probabilistic Bisimulation: Naturally on Distributions
by
Holger Hermanns,
Jan Krčál,
Jan Křetínský,
April 2014, 36 pages.
FIMU-RS-2014-03.
Available as Postscript,
PDF.
Abstract:
In contrast to the usual understanding of probabilistic systems as
stochastic processes, recently these systems have also been 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 to systems with
uncountable state and action spaces. Several examples demonstrate
that our definition refines the understanding of behavioural
equivalences of probabilistic systems. In particular, it solves a
longstanding open problem concerning the representation of
memoryless continuous time by memoryfull continuous time. Finally,
we give algorithms for computing this bisimulation not only for
finite but also for classes of uncountably infinite systems.
