Coalgebraic Trace Semantics for Probabilistic Transition Systems ...

Reference

Henning Kerstan and Barbara König. Coalgebraic trace semantics for probabilistic transition systems based on measure theory. In Maciej Koutny and Irek Ulidowski, editors, CONCUR 2012 – Concurrency Theory, volume 7454 of Lecture Notes in Computer Science, pages 410–424. Springer Berlin Heidelberg, sep 2012.

Abstract

Coalgebras in a Kleisli category yield a generic definition of trace semantics for various types of labelled transition systems. In this paper we apply this generic theory to generative probabilistic transition systems, short PTS, with arbitrary (possibly uncountable) state spaces. We consider the sub-probability monad and the probability monad (Giry monad) on the category of measurable spaces and measurable functions. Our main contribution is that the existence of a final coalgebra in the Kleisli category of these monads is closely connected to the measure-theoretic extension theorem for sigma-finite pre-measures. In fact, we obtain a practical definition of the trace measure for both finite and infinite traces of PTS that subsumes a well-known result for discrete probabilistic transition systems.

Suggested BibTeX entry:

@inproceedings{KK12a,
    author = {Henning Kerstan and Barbara K{\"o}nig},
    booktitle = {CONCUR 2012 -- Concurrency Theory},
    editor = {Koutny, Maciej and Ulidowski, Irek},
    month = {sep},
    pages = {410--424},
    publisher = {Springer Berlin Heidelberg},
    series = {Lecture Notes in Computer Science},
    title = {Coalgebraic Trace Semantics for Probabilistic Transition Systems Based on Measure Theory},
    volume = {7454},
    year = {2012}
}

This work is not available online here.