Logical, Metric, and Algorithmic Characterisations of Probabilistic Bisimulation
Yuxin Deng and Wenjie Du
Many behavioural equivalences or preorders for probabilistic
processes involve a lifting operation that turns a relation on
states into a relation on distributions of states. We show that
several existing proposals for lifting relations can be reconciled
to be different presentations of essentially the same lifting
operation. More interestingly, this lifting operation nicely
corresponds to the Kantorovich metric, a fundamental concept used in
mathematics to lift a metric on states to a metric on distributions
of states, besides the fact the lifting operation is related to the
maximum flow problem in optimisation theory.
The lifting operation yields a neat notion of probabilistic
bisimulation, for which we provide logical, metric, and algorithmic
characterisations. Specifically, we extend the Hennessy-Milner logic
and the modal mu-calculus with a new modality, resulting in an
adequate and an expressive logic for probabilistic bisimilarity,
respectively. The correspondence of the lifting operation and the
Kantorovich metric leads to a natural characterisation of
bisimulations as pseudometrics which are post-fixed points of a
monotone function. We also present an ``on the fly" algorithm to
check if two states in a finitary system are related by
probabilistic bisimilarity, exploiting the close relationship
between the lifting operation and the maximum flow problem.