Hostname: page-component-f554764f5-68cz6 Total loading time: 0 Render date: 2025-04-14T12:23:30.945Z Has data issue: false hasContentIssue false
  • English
  • Français

A classification of bisimilarities for general Markov decision processes

Published online by Cambridge University Press:  07 April 2025

Martín Santiago Moroni  and
Pedro Sánchez Terraf Open the ORCID record for Pedro Sánchez Terraf [Opens in a new window]
Martín Santiago Moroni*
Affiliation:
Facultad de Matemática, Astronomía, Física y Computación, Universidad Nacional de Córdoba, Córdoba Argentina
Pedro Sánchez Terraf
Affiliation:
Centro de Investigación y Estudios de Matemática (CIEM-FaMAF), Conicet, Córdoba, Argentina
*
Corresponding author: Martín Santiago Moroni; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We provide a fine classification of bisimilarities between states of possibly different labelled Markov processes (LMP). We show that a bisimilarity relation proposed by Panangaden that uses direct sums coincides with “event bisimilarity” from his joint work with Danos, Desharnais, and Laviolette. We also extend Giorgio Bacci’s notions of bisimilarity between two different processes to the case of nondeterministic LMP and generalize the game characterization of state bisimilarity by Clerc et al. for the latter.

Keywords

labelled Markov processprobabilistic bisimilaritybisimulation
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 35 , 2025 , e3
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press

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.)

Article purchase

Temporarily unavailable

Footnotes

*

Supported by Secyt-UNC project 33620230100751CB and Conicet PIP project 11220210100508CO.

References

Aczel, P. and Mendler, N. (1989) A final coalgebra theorem. In: Pitt, D. H., Rydeheard, D. E., Dybjer, P., Pitts, A. M. and Poigné, A. (ed.), Category Theory and Computer Science. Berlin, Heidelberg Springer Berlin Heidelberg 357–365.CrossRefGoogle Scholar
Bacci, G. (2013). Generalized Labelled Markov Processes, coalgebraically. Ph.D. thesis. Università degli Studi di Udine.Google Scholar
Bacci, G., Bacci, G., Larsen, K. G. and Mardare, R. (2014) Bisimulation on Markov processes over arbitrary measurable spaces. In: Horizons of the mind. A tribute to Prakash Panangaden. Essays dedicated to Prakash Panangaden on the occasion of his 60th birthday Horizons of the mind. A tribute to Prakash Panangaden. Essays dedicated to Prakash Panangaden on the occasion of his 60th birthday. Berlin, Springer, 76–95.CrossRefGoogle Scholar
Blute, R., Desharnais, J., Edalat, A. and Panangaden, P. (1997). Bisimulation for labelled Markov processes. In: Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, 149–158.CrossRefGoogle Scholar
Budde, C. E., D’Argenio, P. R., Terraf, P. Sánchez and Wolovick, N. (2014) A theory for the semantics of stochastic and non-deterministic continuous systems. In: Remke, A. and Stoelinga, M. (ed.) Stochastic Model Checking. Rigorous Dependability Analysis Using Model Checking Techniques for Stochastic Systems, Lecture Notes in Computer Science 8453, Berlin Heidelberg, Springer, 67–86.Google Scholar
Clerc, F., Fijalkow, N., Klin, B. and Panangaden, P. (2019). Expressiveness of probabilistic modal logics: a gradual approach. Information and Computation. 267 145–163.Google Scholar
D’Argenio, P. R., Sánchez Terraf, P. and Wolovick, N. (2012). Bisimulations for non-deterministic labelled Markov processes. Mathematical Structures in Computer Science. 22 43–68.CrossRefGoogle Scholar
D’Argenio, P. R., Wolovick, N., Sánchez Terraf, P. and Celayes, P. (2009). Nondeterministic labelled Markov processes: Bisimulations and logical characterization. QEST, 20-11.Google Scholar
Danos, V., Desharnais, J., Laviolette, F. and Panangaden, P. (2006). Bisimulation and cocongruence for probabilistic systems. Information and Computation. 204 503–523.CrossRefGoogle Scholar
de Vink, E. P. and Rutten, J. J. M. M. (1997). Bisimulation for probabilistic transition systems: a coalgebraic approach. In: Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7-11, 1997. Proceedings. Berlin: Springer-Verlag. 460–470.Google Scholar
Desharnais, J. (1999). Labelled Markov processes. Ph.D. thesis. McGill University.Google Scholar
Desharnais, J., Edalat, A. and Panangaden, P. (1998). A logical characterization of bisimulation for labelled Markov processes. Proceedings. Thirteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.98CB36226). 179 (2) 163–193.Google Scholar
Desharnais, J., Edalat, A. and Panangaden, P. (2002). Bisimulation for labelled Markov processes. Information and Computation. 179 163–193.CrossRefGoogle Scholar
Doberkat, E. E. (2005a). Semi-pullbacks for stochastic relations over analytic spaces. Mathematical Structures in Computer Science. 15 (4) 647–670.Google Scholar
Doberkat, E. E. (2005b). Stochastic relations: congruences, bisimulations and the Hennessy–Milner theorem. SIAM Journal on Computing. 35 (3) 590–626.CrossRefGoogle Scholar
Doberkat, E. E. and Sánchez Terraf, P. (2017). Stochastic nondeterminism and effectivity functions. Journal of Logic and Computation. 27 (1) 357–394.CrossRefGoogle Scholar
Dubuc, E. J. and Español, L. (2006). Topological functors as familiarly-fibrations, arXiv Mathematics e-prints math/0611701: 1-16.Google Scholar
Edalat, A. (1999). Semi-pullbacks and bisimulation in categories of Markov processes. Mathematical Structures in Computer Science. 9 523–543.CrossRefGoogle Scholar
Gburek, D. (2016). Comments on Proposition 13 in [BBLM14]. Available at https://homes.cs.aau.dk/~grbacci/Papers/comments%20-%20Gburek.pdf.Google Scholar
Giry, M. (1981). A categorical approach to probability theory. In: Categorical Aspects of Topology and Analysis, LNM 915 . Springer, 68–85.Google Scholar
Kechris, A. S. (1994) Classical descriptive set theory. In: Graduate Texts in Mathematics, 156, Springer-Verlag.Google Scholar
Łoś, J. and Marczewski, E. (1949). Extension of measure. Fundamenta Mathematicae. 36 267–276.CrossRefGoogle Scholar
Moroni, M. S. (2022). Bisimulation on Markov decision processes over continuous spaces”. Ph.D. thesis. Universidad Nacional de Córdoba.Google Scholar
Moroni, M. S. and Sánchez Terraf, P. (2023). The Zhou ordinal of labelled Markov processes over separable spaces. The Review of Symbolic Logic. 16 (4) 1011–1032.CrossRefGoogle Scholar
Pachl, J. and Sánchez Terraf, P. (2021). Semipullbacks of labelled Markov processes. Logical Methods in Computer Science. 17 3:1–3:12.Google Scholar
Panangaden, P. (2009). Labelled Markov Processes, Imperial College Press. Available at https://www.worldscientific.com/doi/abs/10.1142/p595.CrossRefGoogle Scholar
Rutten, J. J. M. M. (2000). Universal coalgebra: a theory of systems. Theoretical Computer Science. 249 (1) 3–80.Google Scholar
Sokolova, A. (2005). Coalgebraic analysis of probabilistic systems. Ph.D. thesis. Mathematics and Computer Science.Google Scholar
Sánchez Terraf, P. (2011). Unprovability of the logical characterization of bisimulation. Information and Computation. 209 (7) 1048–1056.CrossRefGoogle Scholar
Viglizzo, I. D. (2005). Coalgebras on measurable spaces. Ph.D. thesis. Indiana University.Google Scholar
Wolovick, N. (2012). Continuous probability and nondeterminism in labelled transition systems. Ph.D. thesis. Universidad Nacional de Córdoba.Google Scholar