An algebraic theory of Markov processes
Bacci, Giorgio and Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon; (2018) An algebraic theory of Markov processes. In: LICS '18 : Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, GBR, pp. 679-688. ISBN 9781450355834 (https://doi.org/10.1145/3209108.3209177)
Preview |
Text.
Filename: Bacci_etal_LICS_2018_An_algebraic_theory_of_Markov_processes.pdf
Accepted Author Manuscript Download (828kB)| Preview |
Abstract
Markov processes are a fundamental model of probabilistic transition systems and are the underlying semantics of probabilistic programs.We give an algebraic axiomatisation of Markov processes using the framework of quantitative equational logic introduced in [13]. We present the theory in a structured way using work of Hyland et al. [9] on combining monads. We take the interpolative barycentric algebras of [13] which captures the Kantorovich metric and combine it with a theory of contractive operators to give the required axiomatisation of Markov processes both for discrete and continuous state spaces. This work apart from its intrinsic interest shows how one can extend the general notion of combining effects to the quantitative setting.
-
-
Item type: Book Section ID code: 74746 Dates: DateEvent9 July 2018Published31 March 2018AcceptedSubjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 01 Dec 2020 14:03 Last modified: 05 Dec 2024 01:05 URI: https://strathprints.strath.ac.uk/id/eprint/74746