2026-07-19T16:32:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8043 2024-03-06T10:39:39Z ddc:004 open_access

Termination in Convex Sets of Distributions Sokolova, Ana Woracek, Harald convex algebra one-point extensions convex powerset monad 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ana Sokolova and Harald Woracek 2017 Is Part Of LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2017.22 urn:nbn:de:0030-drops-80434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.22 eng https://creativecommons.org/licenses/by/3.0/legalcode