The Powerdomain of Indexed Valuations
Daniele Varacca September 2002 |
Abstract:
This paper 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, as they are. 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
Available as PostScript, PDF. |