On Combining Probability and Nondeterminism 1

The problem of combining nondeterminism and probability within a denotational model has been the subject of much research. Early work used schedulers to model probabilistic choice, interleaving their execution with that of nondeterministic choice, a theme that continues in some operational models today. More recent work has focused on providing a principled account of the interactions of these operators, with the aim of devising models that support both operators so that neither is related with the other. In this paper we recount the results along this line, and point out some places where further research is warranted.