A hierarchy of probabilistic system types

Joint work with Erik de Vink (TU/e).

Many approaches in standard concurrency theory are commonly based on labelled transition systems or some minor variant thereof. When probabilities are introduced however, many different system types emerge: some authors for instance consider fully probabilistic systems, while others use systems which incorporate both, nondeterministic and probabilistic choice. In the latter case, various restrictions are furthermore imposed about when or in which order nondeterministic and probabilistic steps are allowed and which of them are associated with input or output labels.

We survey the different probabilistic models in use and arrange them in an expressiveness hierarchy. To this end a coalgebraic presentation turns out to be appropriate not only to describe the various systems with their associated notion of bisimilarity, but also to define translations of one type into another. Moreover, we present a simple sufficient criterion for such a translation to preserve expressiveness.  

hosted by