Simpson, Alexander

Plotkin, Gordon

Battenfeld, Ingo

University of Edinburgh

2008-05-15T14:37:47Z

2008-05-15T14:37:47Z

2008

This thesis presents Topological Domain Theory as a powerful and flexible framework for denotational semantics. Topological Domain Theory models a wide range of type constructions and can interpret many computational features. Furthermore, it has close connections to established frameworks for denotational semantics, as well as to well-studied mathematical theories, such as topology and computable analysis.

We begin by describing the categories of Topological Domain Theory, and their categorical structure. In particular, we recover the basic constructions of domain theory, such as products, function spaces, fixed points and recursive types, in the context of Topological Domain Theory.

As a central contribution, we give a detailed account of how computational effects can be modelled in Topological Domain Theory. Following recent work of Plotkin and Power, who proposed to construct effect monads via free algebra functors, this is done by showing that free algebras for a large class of parametrised equational theories exist in Topological Domain Theory. These parametrised equational theories are expressive enough to generate most of the standard examples of effect monads. Moreover, the free algebras in Topological Domain Theory are obtained by an explicit inductive construction, using only basic topological and set-theoretical principles.

We also give a comparison of Topological and Classical Domain Theory. The category of omega-continuous dcpos embeds into Topological Domain Theory, and we prove that this embedding preserves the basic domain-theoretic constructions in most cases. We show that the classical powerdomain constructions on omega-continuous dcpos, including the probabilistic powerdomain, can be recovered in Topological Domain Theory.

Finally, we give a synthetic account of Topological Domain Theory. We show that Topological Domain Theory is a specific model of Synthetic Domain Theory in the realizability topos over Scott's graph model. We give internal characterisations of the categories of Topological Domain Theory in this realizability topos, and prove the corresponding categories to be internally complete and weakly small. This enables us to show that Topological Domain Theory can model the polymorphic lambda-calculus, and to obtain a richer collection of free algebras than those constructed earlier.

In summary, this thesis shows that Topological Domain Theory supports a wide range of semantic constructions, including the standard domain-theoretic constructions, computational effects and polymorphism, all within a single setting.

917178 bytes

application/pdf

http://hdl.handle.net/1842/2214

en

Electr. Notes Theor. Comput. Sci., 158, 2006, 59-80

Math. Struct. in Comp. Science, 16(2), 2006, 141-161

Electr. Notes Theor. Comput. Sci., 172, 2007, 69-100

Informatics

Computer Science

Computational Effects

Topology

Denotational Semantics

Domain Theory

Topological Domain Theory

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy