FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
An algebraic theory of Markov processes

Authors: Radu Mardare, Prakash Panangaden, Gordon Plotkin and Giorgio Bacci

Paper Information

Title:An algebraic theory of Markov processes
Authors:Radu Mardare, Prakash Panangaden, Gordon Plotkin and Giorgio Bacci
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:Markov processes, computational monads, quantitative algebraic reasoning, equational logic
Abstract:

ABSTRACT. Markov processes are a fundamental models of probabilistic transition systems and are the underlying semantics of probabilistic programs. We give an algebraic axiomatization of Markov processes using the framework of quantitative equational reasoning introduced in LICS2016. We present the theory in a structured way using work of Hyland et al. on combining monads. We take the interpolative barycentric algebras of LICS16 which captures the Kantorovich metric and combine it with a theory of contractive operators to give the required axiomatization 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.

Pages:10
Talk:Jul 09 16:20 (Session 51E)
Paper: