Domain Theory

---

MSc in Computer Science, Schedule C MMath and Computer Science MComputer Science MSc in Mathematics and the Foundations of Computer Science

20 lectures, plus extra reading HT Professor Samson Abramsky Assessed by take-home mini-project

---

Overview

Domain theory is a mathematical theory of information and computation. It is based on the idea of states of (in general) partial information, ordered by how much information they contain. On this basis, a beautiful mathematical theory has been developed, with deep applications to many topics in Computer Science, in particular to the semantics of programming languages. In this course, we shall develop both the mathematical theory, and the applications. Particular themes will: the ideas of continuity and approximation supported by domain theory, which has important connections with topology, and gives a basis for computation with infinite objects; the development of a rich theory of fixpoints, as a foundation for recursive definitions; developing a rich set of data type constructions, and recursive definitions of domains themselves; and powerdomains, to support ideas of non-deterministic and probabilistic computation.

Learning Outcomes

The student will have a working knowledge of basic concepts in Domain theory, including the idea of approximation, being able to analyze recursive definitions in terms of their meaning as least fixed points of continuous function, be able to prove properties of recursively defined objects using techniues such as computational induction.

The student will also have an understanding of the variety of type constructions used in semantics of computation, and an understanding of recursive types; and of the use of information systems to give concrete representations of algebraic domains.

---