Labelled Markov Processes as Generalised Stochastic Relations

Labelled Markov processes (LMPs) are labelled transition systems in which each transition has an associated probability. In this paper we present a universal LMP as the spectrum of a commutative C*-algebra consisting of formal linear combinations of labelled trees. This yields a simple trace-tree semantics for LMPs that is fully abstract with respect to probabilistic bisimilarity. We also consider LMPs with distinguished entry and exit points as stateful stochastic relations. This allows us to define a category GSRel of generalized stochastic relations, which has measurable spaces as objects and LMPs as morphisms. Our main result in this context is to provide a predicate-transformer duality for GSRel that generalises Kozen's duality for the category SRel of stochastic relations. © 2007 Elsevier B.V. All rights reserved