Labelled Markov Processes as Generalised Stochastic Relations

详细信息    查看全文

• 作者：Michael Mislove ; Dusko Pavlovic ; James Worrell
• 关键词：Labelled Markov process ; (Generalized) Stochastic relation ; Probabilistic bisimulation ; Stone duality ; C*-algebra ; Comonad
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2007
• 出版时间：1 April 2007
• 年：2007
• 卷：172
• 期：Complete
• 页码：459-478
• 全文大小：429 K

文摘

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.