Ana Sokolova ; Harald Woracek - Termination in Convex Sets of Distributions

lmcs:4036 - Logical Methods in Computer Science, November 20, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:17)2018
Termination in Convex Sets of DistributionsArticle

Authors: Ana Sokolova ; Harald Woracek

    Convex algebras, also called (semi)convex sets, are at the heart of modelling probabilistic systems including probabilistic automata. Abstractly, they are the Eilenberg-Moore algebras of the finitely supported distribution monad. Concretely, they have been studied for decades within algebra and convex geometry. In this paper we study the problem of extending a convex algebra by a single point. Such extensions enable the modelling of termination in probabilistic systems. We provide a full description of all possible extensions for a particular class of convex algebras: For a fixed convex subset $D$ of a vector space satisfying additional technical condition, we consider the algebra of convex subsets of $D$. This class contains the convex algebras of convex subsets of distributions, modelling (nondeterministic) probabilistic automata. We also provide a full description of all possible extensions for the class of free convex algebras, modelling fully probabilistic systems. Finally, we show that there is a unique functorial extension, the so-called black-hole extension.


    Volume: Volume 14, Issue 4
    Published on: November 20, 2018
    Accepted on: October 18, 2018
    Submitted on: October 31, 2017
    Keywords: Computer Science - Logic in Computer Science

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1737 times.
    This article's PDF has been downloaded 339 times.