Composition of stochastic transition systems based on spans and couplings

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Abstract

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.

Details

Original languageEnglish
Title of host publication43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
EditorsIoannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages102:1-102:15
ISBN (print)978-3-95977-013-2
Publication statusPublished - 2016
Peer-reviewedYes

Publication series

Series43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) ; Vol. 55
Volume55
ISSN1868-8969

Conference

Title43rd International Colloquium on Automata, Languages, and Programming
Abbreviated titleICALP 2016
Duration12 - 15 July 2016
Degree of recognitionInternational event
CityRom
CountryItaly

External IDs

ORCID /0000-0002-5321-9343/work/142236725
ORCID /0000-0003-1724-2586/work/165453593
Scopus 85012879558

Keywords

Keywords

  • Stochastic Transition System, Composition, Stochastic Hybrid Motion Automata, Stochastically Independent, Coupling, Span, Bisimulation, Congruence, Polish Space