Categories of machines, automata (18B20) Eilenberg-Moore and Kleisli constructions for monads (18C20) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
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 of a vector space satisfying additional technical condition, we consider the algebra of convex subsets of . 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.
Recommendations
Cites work
- A cogenerator for preseparated superconvex spaces
- A hierarchy of probabilistic system types
- A spectrum of behavioral relations over LTSs on probability distributions
- Bisimulation for probabilistic transition systems: A coalgebraic approach
- Characterising Testing Preorders for Finite Probabilistic Processes
- Convex Analysis
- Convexity theories. 0: Foundations
- Convexity theories. IV: Klein-Hilbert parts in convex modules
- Convexity, duality and effects
- Eilenberg--Moore algebras for stochastic relations
- Erratum and addendum: ``Eilenberg-Moore algebras for stochastic relations
- Extreme convex sets in \({\mathbb{R}}^ 2\)
- Formal verification of timed properties of randomized distributed algorithms
- Generalized Convexity
- Generalizing the powerset construction, coalgebraically
- scientific article; zbMATH DE number 3744015 (Why is no real title available?)
- scientific article; zbMATH DE number 1022519 (Why is no real title available?)
- scientific article; zbMATH DE number 3434546 (Why is no real title available?)
- scientific article; zbMATH DE number 6917183 (Why is no real title available?)
- scientific article; zbMATH DE number 794262 (Why is no real title available?)
- scientific article; zbMATH DE number 7204940 (Why is no real title available?)
- scientific article; zbMATH DE number 3428045 (Why is no real title available?)
- scientific article; zbMATH DE number 236540 (Why is no real title available?)
- Konvexe Räume
- Logical Characterizations of Bisimulations for Discrete Probabilistic Systems
- On the quasivariety on convex subsets of affine spaces
- On the semantics of Markov automata
- Probabilistic Bisimulation: Naturally on Distributions
- Probabilistic systems coalgebraically: a survey
- States of convex sets
- Testing Finitary Probabilistic Processes
- Trace semantics via determinization
- Upper-expectation bisimilarity and Łukasiewicz -calculus
Cited in
(8)- Operads in the category of convexors: II.
- Congruences of convex algebras.
- Relations into algebras of probabilistic distributions
- scientific article; zbMATH DE number 6917183 (Why is no real title available?)
- The theory of traces for systems with nondeterminism, probability, and termination
- Distribution bisimilarity via the power of convex algebras
- Graded semantics and graded logics for Eilenberg-Moore coalgebras
- Compact quantitative theories 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)
