Labelled Markov processes (LMPs) are automata whose transitions are given by probability distributions. In this paper we present a 'universal' LMP as the spectrum of a commutative C*-algebra consisting of formal linear combinations of labelled trees. We characterize the state space of the universal LMP as the set of homomorphims from an ordered commutative monoid of labelled trees into the multiplicative unit interval. This yields a simple semantics for LMPs which is fully abstract with respect to probabilistic bisimilarity. We also consider LMPs with entry points and exit points in the setting of iteration theories. We define an iteration theory of LMPs by specifying its categorical dual: a certain category of C*-algebra. We find that the basic operations for composing LMPs have simple definitions in the dual category.
Proceedings of FOSSACS 04, LNCS 2987, 2004. 15 pages.
PostScript /
PDF
© 2004
Springer-Verlag.