SOS rule formats for convex and abstract probabilistic bisimulations

Pedro R. D'Argenio
(FaMAF, Universidad Nacional de Córdoba - CONICET)
Matias David Lee
(FaMAF, Universidad Nacional de Córdoba - CONICET)
Daniel Gebler
(Department of Computer Science, VU University Amsterdam)

Probabilistic transition system specifications (PTSSs) in the ntμfθ/ntμxθ format provide structural operational semantics for Segala-type systems that exhibit both probabilistic and nondeterministic behavior and guarantee that bisimilarity is a congruence for all operator defined in such format. Starting from the ntμfθ/ntμxθ format, we obtain restricted formats that guarantee that three coarser bisimulation equivalences are congruences. We focus on (i) Segala's variant of bisimulation that considers combined transitions, which we call here "convex bisimulation"; (ii) the bisimulation equivalence resulting from considering Park & Milner's bisimulation on the usual stripped probabilistic transition system (translated into a labelled transition system), which we call here "probability obliterated bisimulation"; and (iii) a "probability abstracted bisimulation", which, like bisimulation, preserves the structure of the distributions but instead, it ignores the probability values. In addition, we compare these bisimulation equivalences and provide a logic characterization for each of them.

In Silvia Crafa and Daniel E. Gebler: Proceedings of the Combined 22th International Workshop on Expressiveness in Concurrency and 12th Workshop on Structural Operational Semantics (EXPRESS/SOS 2015), Madrid, Spain, 31st August 2015, Electronic Proceedings in Theoretical Computer Science 190, pp. 31–45.
Published: 26th August 2015.

ArXived at: https://dx.doi.org/10.4204/EPTCS.190.3 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org