Daniele Varacca

Computer Laboratory, University of Cambridge.

Time: Tuesday, October 15, 13.00.
Place: Room E2-214, Fredrik Bajersvej 7.

Semantics of probabilty and nondeterminism

This talk is about combining nondeterminism and probabilities. We study this phenomenon from a domain theoretic point of view. In domain theory, nondeterminism is modeled using the notion of powerdomain, while probability is modeled using the powerdomain of valuations. Those two functors do not combine well. We define the notion of powerdomain of indexed valuations, which can be combined nicely with the usual nondeterministic powerdomain. We show an equational characterization of our construction. Finally we discuss the computational meaning of indexed valuations, and we show how they can be used, by giving a denotational semantics of a simple imperative language.

This work was presented at LICS 2002. An extended version appears as BRICS report RS-02-38 (PDF).