×

Kleisli morphisms and randomized congruences for the Giry monad. (English) Zbl 1122.18004

The present paper is about the Kleisli morphisms in the Giry monad (proposed and investigated by M. Giry [Lect. Notes Math. 915, 68–85 (1981; Zbl 0486.60034)] as one component for the categorical foundation of probability theory) and their associated morphisms and congruences. The relationship between kernels of these morphisms and congruences is explained, and a unique factorization of a morphism through this kernel is shown to exist. This study is based on a subdivision into countably generated equivalence relations on the space of all subprobabilities; operations on these relations are investigated quite closely.

MSC:

18C20 Eilenberg-Moore and Kleisli constructions for monads
03B45 Modal logic (including the logic of norms)
08A70 Applications of universal algebra in computer science
18A32 Factorization systems, substructures, quotient structures, congruences, amalgams
18B10 Categories of spans/cospans, relations, or partial maps

Citations:

Zbl 0486.60034
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramsky, S.; Blute, R.; Panangaden, P., Nuclear and trace ideal in tensored \({}^\ast \)-categories, J. Pure Appl. Algebra, 143, 1-3, 3-47 (1999) · Zbl 0946.18004
[2] Arveson, W., (An Invitation to \(C^\ast \)-Algebra. An Invitation to \(C^\ast \)-Algebra, Graduate Texts in Mathematics (1976), Springer-Verlag: Springer-Verlag New York) · Zbl 0344.46123
[3] Baier, C.; Haverkort, B.; Hermanns, H.; Katoen, J.-P., Model-checking algorithms for continuous time Markov chains, IEEE Trans. Softw. Eng., 29, 6, 524-541 (2003)
[4] Desharnais, J.; Edalat, A.; Panangaden, P., Bisimulation of labelled Markov-processes, Inform. and Comput., 179, 2, 163-193 (2002) · Zbl 1096.68103
[5] Desharnais, J.; Panangaden, P., Continuous stochastic logic characterizes bisimulation of continuous-time Markov processes, J. Log. Algebr. Program., 56, 1-2, 99-115 (2003) · Zbl 1053.68065
[6] Doberkat, E.-E., Eilenberg-Moore algebras for stochastic relations, Inform. and Comput., 204, 1756-1781 (2006) · Zbl 1116.18002
[7] Doberkat, E.-E., Stochastic relations: Congruences, bisimulations and the Hennessy-Milner theorem, SIAM J. Comput., 35, 3, 626 (2006) · Zbl 1095.68063
[8] Doberkat, E.-E., Stochastic Relations. Foundations for Markov Transition Systems (2007), Chapman & Hall/CRC Press: Chapman & Hall/CRC Press Boca Raton, New York · Zbl 1137.60002
[9] Giry, M., A categorical approach to probability theory, (Categorical Aspects of Topology and Analysis. Categorical Aspects of Topology and Analysis, Lect. Notes Math., vol. 915 (1981), Springer-Verlag: Springer-Verlag Berlin), 68-85
[10] Grätzer, G., (Universal Algebra. Universal Algebra, The University Series in Higher Mathematics (1968), Van Nostrand: Van Nostrand Princeton, N.J.)
[11] Hennessy, M.; Milner, R., On observing nondeterminism and concurrency, (Proc. ICALP’80. Proc. ICALP’80, Lect. Notes Comp. Sci., vol. 85 (1980), Springer-Verlag: Springer-Verlag Berlin), 395-409 · Zbl 0441.68018
[12] Hinderer, K., Foundations of non-stationary dynamic programming with discrete time parameter, (Lect. Notes Op. Re. Math. Syst., vol. 33 (1970), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0202.18401
[13] C. Jones, Probabilistic non-determinism, Ph.D. Thesis, Univ. Edinburgh, 1989; C. Jones, Probabilistic non-determinism, Ph.D. Thesis, Univ. Edinburgh, 1989
[14] Jones, C.; Plotkin, G., A probabilistic powerdomain of evaluations, (Proc. LICS’89 (1989), IEEE Computer Society Press), 186-195 · Zbl 0716.06003
[15] Kechris, A. S., (Classical Descriptive Set Theory. Classical Descriptive Set Theory, Graduate Texts in Mathematics (1994), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York) · Zbl 0819.04002
[16] G. Lajios, Zur kategoriellen Beschreibung von Schichtenarchitekturen, Ph.D. Thesis, Chair for Software Technology, University of Dortmund, March 2006; G. Lajios, Zur kategoriellen Beschreibung von Schichtenarchitekturen, Ph.D. Thesis, Chair for Software Technology, University of Dortmund, March 2006
[17] Lang, S., Algebra (1965), Addison-Wesley: Addison-Wesley Reading, Mass. · Zbl 0193.34701
[18] Larsen, K. G.; Skou, A., Bisimulation through probabilistic testing, Inform. and Comput., 94, 1-28 (1991) · Zbl 0756.68035
[19] MacLane, S., (Categories for the Working Mathematician. Categories for the Working Mathematician, Graduate Texts in Mathematics (1997), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0705.18001
[20] Moggi, E., Notions of computation and monads, Inform. and Comput., 93, 55-92 (1991) · Zbl 0723.68073
[21] Osius, G., Categorical set theory: A characterisation of the category of sets, J. Pure Appl. Algebra, 4, 79-119 (1974) · Zbl 0282.02027
[22] P. Panangaden, Stochastic techniques in concurrency, Technical Report, BRICS, Dept. of Comp. Sci., Univ. of Aarhus, 1997; P. Panangaden, Stochastic techniques in concurrency, Technical Report, BRICS, Dept. of Comp. Sci., Univ. of Aarhus, 1997
[23] Panangaden, P., Probabilistic relations, (Baier, C.; Huth, M.; Kwiatkowska, M.; Ryan, M., Proc. PROBMIV (1998)), 59-74
[24] Parthasarathy, K. R., Probability Measures on Metric Spaces (1967), Academic Press: Academic Press New York · Zbl 0153.19101
[25] Pumplün, D., Positively convex modules and ordered normed linear spaces, J. Convex Anal., 10, 1, 109-127 (2003) · Zbl 1056.52002
[26] Rutten, J. J.M. M., Universal coalgebra: A theory of systems (Modern algebra and its applications), Theoret. Comput. Sci., 249, 1, 3-80 (2000), (special issue) · Zbl 0951.68038
[27] Srivastava, S. M., (A Course on Borel Sets. A Course on Borel Sets, Graduate Texts in Mathematics (1998), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0903.28001
[28] Taylor, P., (Practical Foundations of Mathematics. Practical Foundations of Mathematics, Cambridge Studies in Advanced Mathematics, vol. 59 (1999), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0939.18001
[29] van Breugel, F.; Mislove, M.; Ouaknine, J.; Worrell, J., Domain theory, testing and simulation for labelled Markov processes, Theoret. Comput. Sci., 333, 171-197 (2005) · Zbl 1070.68108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.