The Theory of Traces for Systems with Nondeterminism, Probability, and
TerminationArticle
Authors: Filippo Bonchi ; Ana Sokolova ; Valeria Vignudelli
NULL##NULL##NULL
Filippo Bonchi;Ana Sokolova;Valeria Vignudelli
This paper studies trace-based equivalences for systems combining
nondeterministic and probabilistic choices. We show how trace semantics for
such processes can be recovered by instantiating a coalgebraic construction
known as the generalised powerset construction. We characterise and compare the
resulting semantics to known definitions of trace equivalences appearing in the
literature. Most of our results are based on the exciting interplay between
monads and their presentations via algebraic theories.