×

Probabilistic automata: System types, parallel composition and comparison. (English) Zbl 1203.68089

Baier, Christel (ed.) et al., Validation of stochastic systems. A guide to current research. Berlin: Springer (ISBN 3-540-22265-0/pbk). Lecture Notes in Computer Science 2925, 1-43 (2004).
Summary: We survey various notions of probabilistic automata and probabilistic bisimulation, accumulating in an expressiveness hierarchy of probabilistic system types. The aim of this paper is twofold: On the one hand it provides an overview of existing types of probabilistic systems and, on the other hand, it explains the relationship between these models. We overview probabilistic systems with discrete probabilities only. The expressiveness order used to built the hierarchy is defined via the existence of mappings between the corresponding system types that preserve and reflect bisimilarity. Additionally, we discuss parallel composition for the presented types of systems, augmenting the map of probabilistic automata with closedness under this compositional operator.
For the entire collection see [Zbl 1047.68001].

MSC:

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