Class Tutor

Nikos Tzevelekos

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.

Prerequisites

Discrete mathematics: sets, functions, relations, order relations. Domain theory would make a good combination with the course on Lambda calculus, but neither requires the other. Similar remarks apply to the course on Categories, Proofs and Programs.

Synopsis

1. Basic concepts of partial orders. Mathematical models of syntax.
2. Fixpoints and recursive definitions, illustrated by a range of examples.
3. Data types: functions, sums and products.
4. Recursive types. Applications: streams, trees, untyped lambda calculus.
5. Algebraicity and continuity. Approximating infinite objects.
6. Powerdomains for non-determinism and probability. Applications to transition systems and processes.

Reading list

• Abramsky and Jung, Domain Theory, in Handbook of Logic in Computer Science
• Davey and Priestley, Introduction to Lattices and Order
• Plotkin, Notes on Domains, available from web.

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.