Probabilistic bisimulation: Naturally on distributions Conference Paper


Author(s): Hermanns, Holger; Krčál, Jan; Křetínský, Jan
Title: Probabilistic bisimulation: Naturally on distributions
Title Series: LNCS
Affiliation IST Austria
Abstract: In contrast to the usual understanding of probabilistic systems as stochastic processes, recently these systems have also been regarded as transformers of probabilities. In this paper, we give a natural definition of strong bisimulation for probabilistic systems corresponding to this view that treats probability distributions as first-class citizens. Our definition applies in the same way to discrete systems as well as to systems with uncountable state and action spaces. Several examples demonstrate that our definition refines the understanding of behavioural equivalences of probabilistic systems. In particular, it solves a longstanding open problem concerning the representation of memoryless continuous time by memoryfull continuous time. Finally, we give algorithms for computing this bisimulation not only for finite but also for classes of uncountably infinite systems.
Conference Title: CONCUR: Concurrency Theory
Volume: 8704
Conference Dates: September 2-5, 2014
Conference Location: Rome, Italy
ISBN: 978-3-95977-017-0
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2014-09-01
Start Page: 249
End Page: 265
URL:
DOI: 10.1007/978-3-662-44584-6_18
Notes: This work is supported by the EU 7th Framework Programme under grant agreements 295261 (MEALS) and 318490 (SENSATION), European Research Council (ERC) under grant agreement 267989 (QUAREM), Austrian Science Fund (FWF) project S11402-N23 (RiSE), Czech Science Foundation under grant agreement P202/12/G061, the DFG Transregional Collaborative Research Centre SFB/TR 14 AVACS, and by the CAS/SAFEA International Partnership Program for Creative Research Teams
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work