Axioms for Probability and Nondeterminism
Michael W. Mislove, Joël Ouaknine, James Worrell · Electronic Notes in Theoretical Computer Science · 2004
This paper studies a simple calculus for finite-state processes featuring both nondeterministic and probabilistic choice. We present a domain model and an operational semantics for our calculus. The denotational model uses the probabilistic powerdomain of Jones and Plotkin, combined with a geometrically convex variant of the Plotkin powerdomain. The operational model defines transition rules under which a process makes transitions to probability distributions over states. We prove a full abstraction result that shows two processes have the same denotation if and only if they are probabilistically bisimilar. We also show that the expected laws for probability and nondeterminism are sound and complete with respect to the denotational model.