Probability, Nondeterminism and Concurrency: Two Denotational Models for
Probabilistic Computation
Daniele Varacca November 2003 |

## Abstract:
Nondeterminism is modelled in domain theory by the notion of a
powerdomain, while probability is modelled by that of the probabilistic
powerdomain. Some problems arise when we want to combine them in order to
model computation in which both nondeterminism and probability are present.
In particular there is no categorical
distributive law between them. We
introduce the powerdomain of indexed valuations which modifies the
usual probabilistic powerdomain to take more detailed account of where
probabilistic choices are made. We show the existence of a distributive law
between the powerdomain of indexed valuations and the nondeterministic
powerdomain. By means of an equational theory we give an alternative
characterisation of indexed valuations and the distributive law. We study the
relation between valuations and indexed valuations. Finally we use indexed
valuations to give a semantics to a programming language. This semantics
reveals the computational intuition lying behind the mathematics.
In
the second part of the thesis we provide an operational reading of continuous
valuations on certain domains (the distributive concrete domains of Kahn and
Plotkin) through the model of
Available as |

Last modified: 2004-08-23 by webmaster.