Compositional methods for probabilistic systems Conference Paper


Author(s): de Alfaro, Luca; Henzinger, Thomas A; Jhala, Ranjit
Title: Compositional methods for probabilistic systems
Title Series: LNCS
Affiliation
Abstract: We present a compositional trace-based model for probabilistic systems. The behavior of a system with probabilistic choice is a stochastic process, namely, a probability distribution on traces, or “bundle.” Consequently, the semantics of a system with both nondeterministic and probabilistic choice is a set of bundles. The bundles of a composite system can be obtained by combining the bundles of the components in a simple mathematical way. Refinement between systems is bundle containment. We achieve assume-guarantee compositionality for bundle semantics by introducing two scoping mechanisms. The first mechanism, which is standard in compositional modeling, distinguishes inputs from outputs and hidden state. The second mechanism, which arises in probabilistic systems, partitions the state into probabilistically independent regions.
Conference Title: CONCUR: Concurrency Theory
Volume: 2154
Conference Dates: August 20-25, 2001
Conference Location: Aalborg, Denmark
ISBN: 978-3-95977-017-0
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Location: Berlin, Heidelberg
Date Published: 2001-08-13
Start Page: 351
End Page: 365
Sponsor: This research was supported in part by the SRC contract 99-TJ-683.003, the AFOSR MURI grant F49620-00-1-0327, the MARCO GSRC grant 98-DT-660, the NSF Theory grant CCR-9988172, and the DARPA SEC grant F33615-C-98-3614.
DOI: 10.1007/3-540-44685-0_24
Open access: no