Composition of Stochastic Transition Systems Based on Spans and Couplings

Daniel GburekDaniel Gburek, Christel BaierChristel Baier, Sascha KlüppelholzSascha Klüppelholz

DOI Link

Daniel Gburek, Christel Baier, Sascha Klüppelholz
Composition of Stochastic Transition Systems Based on Spans and Couplings
Proc. of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), 102:1--102:15, 2016. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
Conventional approaches for parallel composition of stochastic systems relate probability measures of the individual components in terms of product measures. Such approaches rely on the assumption that components interact stochastically independent, which might be too rigid for modeling real world systems. In this paper, we introduce a parallel-composition operator for stochastic transition systems that is based on couplings of probability measures and does not impose any stochastic assumptions. When composing systems within our framework, the intended dependencies between components can be determined by providing so-called spans and span couplings. We present a congruence result for our operator with respect to a standard notion of bisimilarity and develop a general theory for spans, exploiting deep results from descriptive set theory. As an application of our general approach, we propose a model for stochastic hybrid systems called stochastic hybrid motion automata.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{GBK2016,
  author    = {Daniel Gburek and Christel Baier and Sascha Kl{\"{u}}ppelholz},
  title     = {Composition of Stochastic Transition Systems Based on Spans and
               Couplings},
  booktitle = {Proc. of the 43rd International Colloquium on Automata, Languages
               and Programming (ICALP)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {55},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2016},
  pages     = {102:1--102:15},
  doi       = {10.4230/LIPICS.ICALP.2016.102}
}