## An intrinsic characterization of approximate
probabilistic bisimilarity

*Franck van Breugel*,
*Michael W. Mislove*,
*Joël
Ouaknine*, and
*James Worrell*
In previous work we have investigated a notion of approximate
bisimilarity for labelled Markov processes. We argued that such a
notion is more realistic and more feasible to compute than (exact)
bisimilarity. The main technical tool used in the underlying theory
was the Hutchinson metric on probability measures. This paper gives a
more fundamental characterization of approximate bisimilarity in terms
of the notion of (exact) similarity. In particular, we show that the
topology of approximate bisimilarity is the Lawson topology with
respect to the simulation preorder. To complement this abstract
characterization we give a statistical account of similarity, and by
extension, of approximate bisimilarity, in terms of the process
testing formalism of Larsen and Skou.

*Proceedings of FOSSACS 03*, LNCS 2620, 2003. 15 pages.

PostScript /
PDF
© 2003
Springer-Verlag.

Imprint / Data Protection