Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-07T23:13:27.231Z Has data issue: false hasContentIssue false
  • English
  • Français

Weak bisimulations for the Giry monad†

Published online by Cambridge University Press:  27 October 2010

ERNST-ERICH DOBERKAT
ERNST-ERICH DOBERKAT*
Affiliation:
Chair for Software Technology, Technische Universität Dortmund Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the existence of bisimulations for Kleisli morphisms associated with the Giry monad of subprobabilities over Polish spaces. We first investigate these morphisms and show that the problem can be reduced to the existence of bisimulations for objects in the base category of stochastic relations using simulation equivalent congruences. This leads us to a criterion for two objects to be bisimilar.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 5: Theory and Applications of Models of Computation (TAMC 2008–2009) , October 2010 , pp. 781 - 798
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S., Blute, R. and Panangaden, P. (1999) Nuclear and trace ideal in tensored *-categories. J. Pure Appl. Alg. 143 (1-3)3–47.CrossRefGoogle Scholar
Doberkat, E.-E. (2006) Stochastic relations: congruences, bisimulations and the Hennessy–Milner theorem. SIAM J. Computing 35 (3)590–626.CrossRefGoogle Scholar
Doberkat, E.-E. (2007a) Kleisli morphisms and randomized congruences for the Giry monad. J. Pure Appl. Alg. 211 638–664.CrossRefGoogle Scholar
Doberkat, E.-E. (2007b) Stochastic Relations. Foundations for Markov Transition Systems, Chapman and Hall/CRC Press.CrossRefGoogle Scholar
Doberkat, E.-E. (2009) Stochastic Coalgebraic Logic, Springer-Verlag.CrossRefGoogle Scholar
Doberkat, E.-E. and Schubert, Ch. (2009) Coalgebraic logic for stochastic right coalgebras. Ann. Pure Appl. Logic 159 268–284.CrossRefGoogle Scholar
Giry, M. (1981) A categorical approach to probability theory. In: Categorical Aspects of Topology and Analysis. Springer-Verlag Lecture Notes in Computer Science 915 68–85.Google Scholar
Kechris, A. S. (1994) Classical Descriptive Set Theory, Graduate Texts in Mathematics, Springer-Verlag.Google Scholar
Mac Lane, S. (1997) Categories for the Working Mathematician, Graduate Texts in Mathematics, Springer-Verlag.Google Scholar
Moggi, E. (1991) Notions of computation and monads. Information and Computation 93 55–92.CrossRefGoogle Scholar
Parthasarathy, K. R. (1967) Probability Measures on Metric Spaces, Academic Press.CrossRefGoogle Scholar
Schröder, L. and Pattinson, D. (2007) Modular algorithms for heterogeneous modal logics. In: ICALP. Springer-Verlag Lecture Notes in Computer Science 4596 459–471.CrossRefGoogle Scholar
Srivastava, S. M. (1998) A Course on Borel Sets, Graduate Texts in Mathematics, Springer-Verlag.CrossRefGoogle Scholar