×

Deciding bisimilarities on distributions. (English) Zbl 1398.68364

Joshi, Kaustubh (ed.) et al., Quantitative evaluation of systems. 10th international conference, QEST 2013, Buenos Aires, Argentina, August 27–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40195-4/pbk). Lecture Notes in Computer Science 8054, 72-88 (2013).
Summary: Probabilistic automata (PA) are a prominent compositional concurrency model. As a way to justify property-preserving abstractions, in the last years, bisimulation relations over probability distributions have been proposed both in the strong and the weak setting. Different to the usual bisimulation relations, which are defined over states, an algorithmic treatment of these relations is inherently hard, as their carrier set is uncountable, even for finite PAs. The coarsest of these relation, weak distribution bisimulation, stands out from the others in that no equivalent state-based characterisation is known so far. This paper presents an equivalent state-based reformulation for weak distribution bisimulation, rendering it amenable for algorithmic treatment. Then, decision procedures for the probability distribution-based bisimulation relations are presented.
For the entire collection see [Zbl 1284.68017].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDFBibTeX XMLCite
Full Text: DOI