Termination in convex sets of distributions

DOI10.23638/LMCS-14(4:17)2018zbMATH Open1400.68146arXiv1710.10402OpenAlexW2767081344MaRDI QIDQ4558786FDOQ4558786

Authors: Ana Sokolova, Harald Woracek 

Publication date: 30 November 2018

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.

Full work available at URL: https://arxiv.org/abs/1710.10402

Recommendations

• scientific article; zbMATH DE number 6917183
• Congruences of convex algebras.
• scientific article; zbMATH DE number 7204940
• Distribution bisimilarity via the power of convex algebras
• Relations into algebras of probabilistic distributions

zbMATH Keywords

one-point extensionsconvex algebraconvex powerset monad

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Eilenberg-Moore and Kleisli constructions for monads (18C20) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Categories of machines, automata (18B20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex Analysis
• On the semantics of Markov automata
• Bisimulation for probabilistic transition systems: A coalgebraic approach
• Title not available (Why is that?)
• Probabilistic systems coalgebraically: a survey
• Trace semantics via determinization
• Convexity, duality and effects
• Title not available (Why is that?)
• Title not available (Why is that?)
• States of convex sets
• Eilenberg--Moore algebras for stochastic relations
• Testing Finitary Probabilistic Processes
• Characterising Testing Preorders for Finite Probabilistic Processes
• A hierarchy of probabilistic system types
• Erratum and addendum: ``Eilenberg-Moore algebras for stochastic relations
• On the quasivariety on convex subsets of affine spaces
• Logical Characterizations of Bisimulations for Discrete Probabilistic Systems
• Probabilistic Bisimulation: Naturally on Distributions
• Generalizing the powerset construction, coalgebraically
• Formal verification of timed properties of randomized distributed algorithms
• Konvexe Räume
• Title not available (Why is that?)
• Generalized Convexity
• Extreme convex sets in \({\mathbb{R}}^ 2\)
• Title not available (Why is that?)
• Convexity theories. 0: Foundations
• A cogenerator for preseparated superconvex spaces
• Convexity theories. IV: Klein-Hilbert parts in convex modules
• Title not available (Why is that?)
• Upper-expectation bisimilarity and Łukasiewicz \(\mu \)-calculus
• A spectrum of behavioral relations over LTSs on probability distributions

Cited In (7)

• Operads in the category of convexors: II.
• Relations into algebras of probabilistic distributions
• Title not available (Why is that?)
• Congruences of convex algebras.
• Title not available (Why is that?)
• Graded semantics and graded logics for Eilenberg-Moore coalgebras
• Distribution bisimilarity via the power of convex algebras

This page was built for publication: Termination in convex sets of distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558786)