Jean Goubault-Larrecq (Paris, France), Probability and Nondeterminism in Domain Theory, Part II


  • Feb. 23, 2012, 15:20 - 16:20


As the title indicates, this is a follow-up on Daniele Varacca's talk. We shall first talk about the very intuitive denotational model of probabilistic choice given by so-called continuous random variables, and will explain the relation to indexed valuations, as seen in Part I. We shall then explore a few solutions to the problem of giving semantics to mixed non-deterministic and probabilistic higher-order functional programs. While indexed valuations and continuous random variables solve the problem by changing the model of probabilistic choice, previsions and the Mislove-Ouaknine-Worrell and Tix-Kleimel-Plotkin models solve it by changing the model of non-deterministic choice to convex non-determinism. We shall conclude by returning to some of the goals stated at the beginning of Part I, and shall establish a few full abstraction results for variants of PCF with choice, exhibiting the differences in observable properties that each model exhibits.