Termination in convex sets of distributions
From MaRDI portal
Publication:4558786
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)
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
- 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?)
- 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
- 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 \(\mu \)-calculus
Cited in
(7)- Operads in the category of convexors: II.
- Relations into algebras of probabilistic distributions
- scientific article; zbMATH DE number 7566077 (Why is no real title available?)
- Distribution bisimilarity via the power of convex algebras
- Congruences of convex algebras.
- scientific article; zbMATH DE number 6917183 (Why is no real title available?)
- Graded semantics and graded logics for Eilenberg-Moore coalgebras
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)
