License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2017.22
URN: urn:nbn:de:0030-drops-80434
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8043/
Go to the corresponding LIPIcs Volume Portal

Sokolova, Ana ; Woracek, Harald

Termination in Convex Sets of Distributions

pdf-format:
LIPIcs-CALCO-2017-22.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{sokolova_et_al:LIPIcs:2017:8043,
  author =	{Ana Sokolova and Harald Woracek},
  title =	{{Termination in Convex Sets of Distributions}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Filippo Bonchi and Barbara K{\"o}nig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8043},
  URN =		{urn:nbn:de:0030-drops-80434},
  doi =		{10.4230/LIPIcs.CALCO.2017.22},
  annote =	{Keywords: convex algebra, one-point extensions, convex powerset monad}
}

Keywords: convex algebra, one-point extensions, convex powerset monad
Collection: 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)
Issue Date: 2017
Date of publication: 17.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI