Hostname: page-component-6bf8c574d5-qdpjg Total loading time: 0 Render date: 2025-02-21T01:22:54.616Z Has data issue: false hasContentIssue false
  • English
  • Français

Distributing probability over non-determinism

Published online by Cambridge University Press:  21 February 2006

DANIELE VARACCA  and
GLYNN WINSKEL
DANIELE VARACCA
Affiliation:
Department of Computing, Imperial College London, London, U.K.
GLYNN WINSKEL
Affiliation:
Computer Laboratory, Cambridge University, Cambridge, U.K.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the combination of probability and non-determinism from a categorical point of view. In category theory, non-determinism and probability are represented by suitable monads. However, these two monads do not combine well as they are. To overcome this problem, we introduce the notion of indexed valuations. This notion is used to define a new monad that can be combined with the usual non-deterministic monad via a categorical distributive law. We give an equational characterisation of our construction. 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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 16 , Issue 1 , February 2006 , pp. 87 - 113
Copyright
2006 Cambridge University Press