Abstract
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.
Supported by the Natural Sciences and Engineering Research Council of Canada.
Supported by the US National Science Foundation and the US Office of Naval Research (ONR).
Supported by ONR contract N00014-95-1-0520, Defense Advanced Research Project Agency and the Army Research Office under contract DAAD19-01-1-0485.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adámek, J. and V. Koubek: On the greatest fixed point of a set functor. Theoretical Computer Science, 150 (1995) 57–75.
Alvarez-Manilla, M., A. Edalat, and N. Saheb-Djahromi. An extension result for continuous valuations. Journal of the London Mathematical Society, 61 (2000)629–640.
Averson, W.: An Invitation to C*-Algebras, Springer-Verlag, 1976.
van Breugel, F. and J. Worrell: Towards quantitative verification of probabilistic transition system, Lecture Notes in Computer Science, 2076 (2001), Springer-Verlag, 421–432.
van Breugel, F. and J. Worrell: An algorithm for quantitative verification of probabilistic transition systems, Lecture Notes in Computer Science, 2154 (2001), Springer-Verlag, 336–350.
van Breugel, F., S. Shalit and J. Worrell: Testing labelled Markov processes, Lecture Notes in Computer Science, 2380 (2002), Springer-Verlag, 537–548.
van Breugel, F., M. Mislove, J. Ouaknine and J. Worrell: An intrinsic characterization of approximate probabilistic bisimilarity, Report CS-2003-01, York University, 2003.
Desharnais, J., A. Edalat and P. Panangaden: A logical characterization of bisimulation for labelled Markov processes, In Proc. 13th IEEE Symposium on Logic in Computer Science (1998), IEEE Press, 478–487.
Desharnais, J., V. Gupta, R. Jagadeesan and P. Panangaden: Metrics for labeled Markov systems, Lecture Notes in Computer Science, 1664 (1999), Springer-Verlag, 258–273.
Desharnais, J., V. Gupta, R. Jagadeesan and P. Panangaden: Approximating labeled Markov processes. In Proc. 15th Symposium on Logic in Computer Science, (2000), IEEE Press, 95–106.
Edalat, A.: When Scott is weak at the top, Mathematical Structures in Computer Science, 7 (1997), 401–417.
Giry, M.: A categorical approach to probability theory, Lecture Notes in Mathematics, 915 (1981), Springer-Verlag, 68–85.
Heckmann, R.: Spaces of valuations, Annals of the New York Academy of Sciences, 806 (1996), New York Academy of Sciences, 174–200.
Jones, C.: Probabilistic nondeterminism, PhD Thesis, Univ. of Edinburgh, 1990.
Jung, A. and R. Tix: The troublesome probabilistic powerdomain. Electronic Notes in Theoretical Computer Science, 13 (1998), Elsevier.
Larsen, K.G. and A. Skou: Bisimulation through probabilistic testing: Information and Computation, 94 (1991), Academic Press, 1–28.
Milner, R.: Communication and Concurrency, Prentice Hall, 1989.
Park, D.: Concurrency and automata on infinite sequences. Lecture Notes in Computer Science, 104 (1981), Springer-Verlag, 167–183.
Parthasarathy, K.R.: Probability Measures on Metric Spaces, Academic Press, 1967.
Di Pierro, A., C. Hankin, and H. Wiklicky, Approximate non-interference, In Proc. 15th IEEE Computer Security Foundations Workshop (2002), IEEE Press, 3–17.
Smyth, M.B. and G.D. Plotkin: The category theoretic solution of recursive domain equations, SIAM Journal of Computing, 11 (1982), 761–783.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Breugel, F., Mislove, M., Ouaknine, J., Worrell, J. (2003). An Intrinsic Characterization of Approximate Probabilistic Bisimilarity. In: Gordon, A.D. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2003. Lecture Notes in Computer Science, vol 2620. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36576-1_13
Download citation
DOI: https://doi.org/10.1007/3-540-36576-1_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00897-2
Online ISBN: 978-3-540-36576-1
eBook Packages: Springer Book Archive