An algebraic theory of markov processes

Giorgio Bacci, Radu Mardare, Prakash Panangaden, Gordon Plotkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
Pages679-688
Number of pages10
ISBN (Electronic)9781450355834, 9781450355834
DOIs
Publication statusPublished - 9 Jul 2018
Event33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, United Kingdom
Duration: 9 Jul 201812 Jul 2018

Conference

Conference33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
CountryUnited Kingdom
CityOxford
Period9/07/1812/07/18

Keywords

  • combining monads
  • equational logic
  • Markov processes
  • quantitative reasoning

Fingerprint Dive into the research topics of 'An algebraic theory of markov processes'. Together they form a unique fingerprint.

  • Cite this

    Bacci, G., Mardare, R., Panangaden, P., & Plotkin, G. (2018). An algebraic theory of markov processes. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 (pp. 679-688) https://doi.org/10.1145/3209108.3209177