Abstract
Labelled Markov processes are continuous-state fully probabilistic labelled transition systems. They can be seen as co-algebras of a suitable monad on the category of measurable space. The theory as developed so far included a treatment of bisimulation, logical characterization of bisimulation, weak bisimulation, metrics, universal domains for LMPs and approximations. Much of the theory involved delicate properties of analytic spaces.
Recently a new kind of averaging procedure was used to construct approximations. Remarkably, this version of the theory uses a dual view of LMPs and greatly simplifies the theory eliminating the need to consider aanlytic spaces. In this talk I will survey some of the ideas that led to this work.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Sontag, E.: Mathematical Control Theory. Texts in Applied Mathematics, vol. 6. Springer, Heidelberg (1990)
Blute, R., Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for labelled Markov processes. In: Proceedings of the Twelfth IEEE Symposium On Logic In Computer Science, Warsaw, Poland (1997)
Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for labeled Markov processes. Information and Computation 179(2), 163–193 (2002)
Segala, R., Lynch, N.: Probabilistic simulations for probabilistic processes. In: Jonsson, B., Parrow, J. (eds.) CONCUR 1994. LNCS, vol. 836, pp. 481–496. Springer, Heidelberg (1994)
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, Chichester (1994)
Larsen, K.G., Skou, A.: Bisimulation through probablistic testing. Information and Computation 94, 1–28 (1991)
de Vink, E., Rutten, J.J.M.M.: Bisimulation for probabilistic transition systems: A coalgebraic approach. In: Proceedings of the 24th International Colloquium On Automata Languages And Programming (1997)
Kozen, D.: A probabilistic PDL. Journal of Computer and Systems Sciences 30(2), 162–178 (1985)
Danos, V., Desharnais, J., Panangaden, P.: Conditional expectation and the approximation of labelled markov processes. In: Amadio, R.M., Lugiez, D. (eds.) CONCUR 2003. LNCS, vol. 2761, pp. 477–491. Springer, Heidelberg (2003)
Feller, W.: An Introduction to Probability Theory and its Applications II, 2nd edn. John Wiley and Sons, Chichester (1971)
Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: The metric analogue of weak bisimulation for labelled Markov processes. In: Proceedings of the Seventeenth Annual IEEE Symposium On Logic In Computer Science, pp. 413–422 (2002)
Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand (1960)
Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Approximating labeled Markov processes. Information and Computation 184(1), 160–200 (2003)
Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: A metric for labelled Markov processes. Theoretical Computer Science 318(3), 323–354 (2004)
Hopf, E.: The general temporally discrete Markoff process. J. Rational Math. Mech. Anal. 3, 13–45 (1954)
Danos, V., Desharnais, J., Laviolette, F., Panangaden, P.: Bisimulation and cocongruence for probabilistic systems. Information and Computation 204(4), 503–523 (2006)
Bartels, F., Sokolova, A., de Vink, E.: A hierarchy of probabilistic system types. Theoretical Computer Science 327, 3–22 (2004)
Billingsley, P.: Probability and Measure. Wiley Interscience, Hoboken (1995)
Choksi, J.: Inverse limits on measure spaces. Proc. London Math. Soc. 8(3), 321–342 (1958)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chaput, P., Danos, V., Panangaden, P., Plotkin, G. (2009). Approximating Labelled Markov Processes Again!. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds) Algebra and Coalgebra in Computer Science. CALCO 2009. Lecture Notes in Computer Science, vol 5728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03741-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-03741-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03740-5
Online ISBN: 978-3-642-03741-2
eBook Packages: Computer ScienceComputer Science (R0)