TY - JOUR
TI - Domain theory, testing and simulation for labelled Markov processes
AU - van Breugel, Franck
AU - Mislove, Michael
AU - Ouaknine, Joël
AU - Worrell, James
T2 - Theoretical Computer Science
T3 - Foundations of Software Science and Computation Structures
AB - This paper presents a fundamental study of similarity and bisimilarity for labelled Markov processes (LMPs). The main results characterize similarity as a testing preorder and bisimilarity as a testing equivalence. In general, LMPs are not required to satisfy a finite-branching condition—indeed the state space may be a continuum, with the transitions given by arbitrary probability measures. Nevertheless we show that to characterize bisimilarity it suffices to use finitely-branching labelled trees as tests. Our results involve an interaction between domain theory and measure theory. One of the main technical contributions is to show that a final object in a suitable category of LMPs can be constructed by solving a domain equation D≅V(D)Act, where V is the probabilistic powerdomain. Given an LMP whose state space is an analytic space, bisimilarity arises as the kernel of the unique map to the final LMP. We also show that the metric for approximate bisimilarity introduced by Desharnais, Gupta, Jagadeesan and Panangaden generates the Lawson topology on the domain D.
DA - 2005/03/01/
PY - 2005
DO - 10/ft9vc5
DP - ScienceDirect
VL - 333
IS - 1
SP - 171
EP - 197
J2 - Theoretical Computer Science
LA - en
SN - 0304-3975
UR - http://www.sciencedirect.com/science/article/pii/S030439750400711X
Y2 - 2019/11/26/19:59:13
KW - Coalgebras
KW - Denotational semantics
KW - Probabilistic transition systems
KW - Transition systems
ER -
TY - JOUR
TI - Bisimulation for Labelled Markov Processes
AU - Desharnais, Josée
AU - Edalat, Abbas
AU - Panangaden, Prakash
T2 - Information and Computation
AB - In this paper we introduce a new class of labelled transition systems—labelled Markov processes— and define bisimulation for them. Labelled Markov processes are probabilistic labelled transition systems where the state space is not necessarily discrete. We assume that the state space is a certain type of common metric space called an analytic space. We show that our definition of probabilistic bisimulation generalizes the Larsen–Skou definition given for discrete systems. The formalism and mathematics is substantially different from the usual treatment of probabilistic process algebra. The main technical contribution of the paper is a logical characterization of probabilistic bisimulation. This study revealed some unexpected results, even for discrete probabilistic systems. •Bisimulation can be characterized by a very weak modal logic. The most striking feature is that one has no negation or any kind of negative proposition.•We do not need any finite branching assumption, yet there is no need of infinitary conjunction. We also show how to construct the maximal autobisimulation on a system. In the finite state case, this is just a state minimization construction. The proofs that we give are of an entirely different character than the typical proofs of these results. They use quite subtle facts about analytic spaces and appear, at first sight, to be entirely nonconstructive. Yet one can give an algorithm for deciding bisimilarity of finite state systems which constructs a formula that witnesses the failure of bisimulation.
DA - 2002/12/15/
PY - 2002
DO - 10/fmp9vd
DP - ScienceDirect
VL - 179
IS - 2
SP - 163
EP - 193
J2 - Information and Computation
LA - en
SN - 0890-5401
UR - http://www.sciencedirect.com/science/article/pii/S0890540101929621
Y2 - 2019/11/26/21:27:24
KW - Coalgebras
KW - Denotational semantics
KW - Probabilistic transition systems
KW - Symbolic logic
KW - Transition systems
ER -
TY - CONF
TI - Bisimulation for probabilistic transition systems: A coalgebraic approach
AU - de Vink, E. P.
AU - Rutten, J. J. M. M.
A2 - Degano, Pierpaolo
A2 - Gorrieri, Roberto
A2 - Marchetti-Spaccamela, Alberto
T3 - Lecture Notes in Computer Science
AB - The notion of bisimulation as proposed by Larsen and Skou for discrete probabilistic transition systems is shown to coincide with a coalgebraic definition in the sense of Aczel and Mendier in terms of a set functor. This coalgebraic formulation makes it possible to generalize the concepts to a continuous setting involving Borel probability measures. Under reasonable conditions, generalized probabilistic bisimilarity can be characterized categorically. Application of the final coalgebra paradigm then yields an internally fully abstract semantical domain with respect to probabilistic bisimulation.
C1 - Berlin, Heidelberg
C3 - Automata, Languages and Programming
DA - 1997///
PY - 1997
DO - 10/fcqzmk
DP - Springer Link
SP - 460
EP - 470
LA - en
PB - Springer
SN - 978-3-540-69194-5
ST - Bisimulation for probabilistic transition systems
KW - Categorical probability theory
KW - Coalgebras
KW - Denotational semantics
KW - Probabilistic transition systems
KW - Transition systems
ER -