An Algebraic Theory of Markov Processes

Giorgio Bacci, Radu Iulian Mardare, Prakash Panangaden, Gordon Plotkin

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citation (Scopus)
12 Downloads (Pure)

Resumé

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 (Mardare et al LICS'16). We present the theory in a structured way using work of (Hyland et al. TCS'06) on combining monads. We take the interpolative barycentric algebras of (Mardare et al LICS'16) 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.
OriginalsprogEngelsk
TitelProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
Antal sider10
ForlagAssociation for Computing Machinery
Publikationsdato9 jul. 2018
Sider679-688
ISBN (Elektronisk)978-1-4503-5583-4
DOI
StatusUdgivet - 9 jul. 2018
Begivenhed33rd Annual ACM/IEEE Symposium on Logic in Computer Science - University of Oxford, Oxford, Storbritannien
Varighed: 9 jul. 201812 jul. 2018
http://lics.siglog.org/lics18/

Konference

Konference33rd Annual ACM/IEEE Symposium on Logic in Computer Science
LokationUniversity of Oxford
LandStorbritannien
ByOxford
Periode09/07/201812/07/2018
Internetadresse
NavnAnnual Symposium on Logic in Computer Science
ISSN1043-6871

Fingerprint

Algebraic Theory
Markov Process
Axiomatization
Equational Logic
Centrobaric
Monads
Transition Systems
State Space
Metric
Algebra
Operator
Model

Citer dette

Bacci, G., Mardare, R. I., Panangaden, P., & Plotkin, G. (2018). An Algebraic Theory of Markov Processes. I Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 (s. 679-688). Association for Computing Machinery. Annual Symposium on Logic in Computer Science https://doi.org/10.1145/3209108.3209177
Bacci, Giorgio ; Mardare, Radu Iulian ; Panangaden, Prakash ; Plotkin, Gordon. / An Algebraic Theory of Markov Processes. Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Association for Computing Machinery, 2018. s. 679-688 (Annual Symposium on Logic in Computer Science).
@inproceedings{31664965faa249b686428e9ce7ff052e,
title = "An Algebraic Theory of Markov Processes",
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 (Mardare et al LICS'16). We present the theory in a structured way using work of (Hyland et al. TCS'06) on combining monads. We take the interpolative barycentric algebras of (Mardare et al LICS'16) 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.",
keywords = "Markov Processes, Combining Monads, Equational Logic, Quantitative Reasoning",
author = "Giorgio Bacci and Mardare, {Radu Iulian} and Prakash Panangaden and Gordon Plotkin",
year = "2018",
month = "7",
day = "9",
doi = "10.1145/3209108.3209177",
language = "English",
series = "Annual Symposium on Logic in Computer Science",
publisher = "Association for Computing Machinery",
pages = "679--688",
booktitle = "Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018",
address = "United States",

}

Bacci, G, Mardare, RI, Panangaden, P & Plotkin, G 2018, An Algebraic Theory of Markov Processes. i Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Association for Computing Machinery, Annual Symposium on Logic in Computer Science, s. 679-688, 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, Oxford, Storbritannien, 09/07/2018. https://doi.org/10.1145/3209108.3209177

An Algebraic Theory of Markov Processes. / Bacci, Giorgio; Mardare, Radu Iulian; Panangaden, Prakash; Plotkin, Gordon.

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Association for Computing Machinery, 2018. s. 679-688 (Annual Symposium on Logic in Computer Science).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - An Algebraic Theory of Markov Processes

AU - Bacci, Giorgio

AU - Mardare, Radu Iulian

AU - Panangaden, Prakash

AU - Plotkin, Gordon

PY - 2018/7/9

Y1 - 2018/7/9

N2 - 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 (Mardare et al LICS'16). We present the theory in a structured way using work of (Hyland et al. TCS'06) on combining monads. We take the interpolative barycentric algebras of (Mardare et al LICS'16) 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.

AB - 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 (Mardare et al LICS'16). We present the theory in a structured way using work of (Hyland et al. TCS'06) on combining monads. We take the interpolative barycentric algebras of (Mardare et al LICS'16) 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.

KW - Markov Processes

KW - Combining Monads

KW - Equational Logic

KW - Quantitative Reasoning

UR - http://www.scopus.com/inward/record.url?scp=85051119872&partnerID=8YFLogxK

U2 - 10.1145/3209108.3209177

DO - 10.1145/3209108.3209177

M3 - Article in proceeding

T3 - Annual Symposium on Logic in Computer Science

SP - 679

EP - 688

BT - Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018

PB - Association for Computing Machinery

ER -

Bacci G, Mardare RI, Panangaden P, Plotkin G. An Algebraic Theory of Markov Processes. I Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Association for Computing Machinery. 2018. s. 679-688. (Annual Symposium on Logic in Computer Science). https://doi.org/10.1145/3209108.3209177