## Duality for labelled Markov processes

*Michael W. Mislove*,
*Joël
Ouaknine*,
*Dusko Pavlovic*,
and *James Worrell*
Labelled Markov processes (**LMP**s) 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
**LMP**s which is fully abstract with respect to probabilistic
bisimilarity. We also consider **LMP**s with entry points and exit
points in the setting of iteration theories. We define an iteration
theory of **LMP**s by specifying its categorical dual: a certain
category of C^{*}-algebra. We find that the basic operations
for composing **LMP**s have simple definitions in the dual
category.

*Proceedings of FOSSACS 04*, LNCS 2987, 2004. 15 pages.

PostScript /
PDF
© 2004
Springer-Verlag.

Imprint / Data Protection