Jan Pachl ; Pedro Sánchez Terraf - Semipullbacks of labelled Markov processes

lmcs:5886 - Logical Methods in Computer Science, April 14, 2021, Volume 17, Issue 2 - https://doi.org/10.23638/LMCS-17(2:3)2021
Semipullbacks of labelled Markov processesArticle

Authors: Jan Pachl ; Pedro Sánchez Terraf

    A labelled Markov process (LMP) consists of a measurable space $S$ together with an indexed family of Markov kernels from $S$ to itself. This structure has been used to model probabilistic computations in Computer Science, and one of the main problems in the area is to define and decide whether two LMP $S$ and $S'$ "behave the same". There are two natural categorical definitions of sameness of behavior: $S$ and $S'$ are bisimilar if there exist an LMP $ T$ and measure preserving maps forming a diagram of the shape $ S\leftarrow T \rightarrow{S'}$; and they are behaviorally equivalent if there exist some $ U$ and maps forming a dual diagram $ S\rightarrow U \leftarrow{S'}$. These two notions differ for general measurable spaces but Doberkat (extending a result by Edalat) proved that they coincide for analytic Borel spaces, showing that from every diagram $S\rightarrow U \leftarrow{S'}$ one can obtain a bisimilarity diagram as above. Moreover, the resulting square of measure preserving maps is commutative (a semipullback). In this paper, we extend the previous result to measurable spaces $S$ isomorphic to a universally measurable subset of a Polish space with the trace of the Borel $\sigma$-algebra, using a version of Strassen's theorem on common extensions of finitely additive measures.


    Volume: Volume 17, Issue 2
    Published on: April 14, 2021
    Accepted on: February 16, 2021
    Submitted on: November 1, 2019
    Keywords: Mathematics - Probability,Computer Science - Logic in Computer Science,28A35, 28A60, 68Q85,F.4.1,F.1.2

    Consultation statistics

    This page has been seen 951 times.
    This article's PDF has been downloaded 126 times.