A Uniform Approach to Domain Theory in Realizability Models

John R. Longley, Alex Simpson

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a uniform way of isolating a subcategory of predomains within the category of modest sets determined by a partial combinatory algebra (PCA). Given a divergence on a PCA (which determines a notion of partiality), we identify a candidate category of predomains, the well-complete objects. We show that, whenever a single strong completeness axiom holds, the category satisfies appropriate closure properties. We consider a range of examples of PCAs with associated divergences and show that in each case the axiom does hold. These examples encompass models allowing a ‘parallel’ style of computation (for example, by interleaving), as well as models that seemingly allow only ‘sequential’ computation, such as those based on term-models for the lambda-calculus. Thus, our approach provides a uniform approach to domain theory across a wide class of realizability models. We compare our treatment with previous approaches to domain theory in realizability models. It appears that no other approach applies across such a wide range of models.
Original languageEnglish
Pages (from-to)469-505
Number of pages37
JournalMathematical Structures in Computer Science
Volume7
Issue number5
DOIs
Publication statusPublished - 1 Oct 1997

Fingerprint

Dive into the research topics of 'A Uniform Approach to Domain Theory in Realizability Models'. Together they form a unique fingerprint.

Cite this