Daniele Varacca (Paris, France), Probability and Nondeterminism in Domain Theory, Part I


  • Feb. 23, 2012, 14:00 - 15:00


I will first introduce the notion of continuous valuations, used by Jones and Plotkin to represent probabilities in domain theory. I will in particular discuss the Splitting Lemma which gives an intuition about the way valuations are ordered. I will then explain why the valuations are "troublesome" (as defined by Jung and Tix): no cartesian closed category of continuous domains is known to be preserved by the valuations functor, and therefore they cannot be used in the semantics of functional programming languages, like a probabilistic extension of PCF.

Valuations are troublesome also because they do not combine well with the nondeterminisitic models of domain theory. I will show why and I will introduce another probabilistic model that is designed to solve this problem: the indexed valuations. I will show how the Splitting Lemma translates within indexed valuations. Indexed valuations also pave the way towards random variables will be presented by Jean Goubault-Larrecq in Part II.

Fear not. Only very lightweight notions of category theory and of universal algebra will be used in this talk.