On domains witnessing increase in information

Dieter Spreen


The paper considers algebraic directed-complete partial orders with a semi-regular Scott topology, called regular domains. As is well know, the category of Scott domains and continuous maps is Cartesian closed. This is no longer true, if the domains are required to be regular. Two Cartesian closed subcategories of the regular Scott domains are exhibited: regular dI-domains with stable maps and strongly regular Scott domains with continuous maps. Here a Scott domains is strongly regular if all of its compact open subsets are regular open. In one considers only embeddings of dependent products and sums. Moreover, they are w-cocomplete and their object classes are closed under several constructions used in programming language semantics. It follows that recursive domains equations can be solved and models of typed and untyped lambda calculi can be constructed. Both kinds of domains can be udes in giving meaning to programming language constructs.


Scott domain; dI-domains; semi-regular topology; programming language semantics; recursive domain equations; dependent product; dependent sum; lambda calculus

Subject classification

68Q55; 06B35; 03B15; 03B40; 18B30

Full Text:



S. Abramsky and A. Jung, Domain theory, in: S. Abramsky, D. M. Gabbay and T. S. E. Maibaum, eds., Handbook of Logic in Computer Science, Vol. 3, Semantic Structures, Oxford University Press, Oxford, 1994, 1-168.

R. M. Amadio and P.-L. Curien, Domains and Lambda-Calculi, Cambridge University Press, Cambridge, 1998. https://doi.org/10.1017/CBO9780511983504

H. Barendregt, The Lambda Calculus, Its Syntax and Semantics, North-Holland, Amsterdam, 1984.

G. Berry, Stable models of typed lambda-calculi, in: G. Ausiello and C. Böhm, eds., Automata, Languages, and Programming, 5th Colloquium, Lec. Notes Comp. Sci. 62, Springer-Verlag, Berlin, 1978, 72-89. https://doi.org/10.1007/3-540-08860-1_7

T. Coquand, C. Gunter and G. Winskel, Domain theoretic models of polymorphism, Inform. and Comput. 81 (1989), 123-167. https://doi.org/10.1016/0890-5401(89)90068-0

Yu. L. Ershov, Computable functionals of finite type, Algebra I Logika 11 (1972), 367-437. https://doi.org/10.1007/BF02219096

English translation: Algebra and Logic 11 (1972), 203-242. https://doi.org/10.1007/BF02219096

C. A. Gunter, Semantics of Programming Languages, MIT Press, Cambridge, MA, 1992.

C. A. Gunter and D. S. Scott, Semantic Domains, in: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Vol. B, Formal Models and Semantics, Elsevier, Amsterdam, 1990, 633-674.

A. Jung, Notes on existential domains, manuscript, 1992.

E. Palmgren and V. Stoltenberg-Hansen, Domain interpretations of Martin-Löf's partial type theory, Ann. Pure Appl. Logic 48 (1990), 135-196. https://doi.org/10.1016/0168-0072(90)90044-3

G. D. Plotkin, A powerdomain construction, SIAM J. Comput. 5 (1976), 452-487. https://doi.org/10.1137/0205035

D. S. Scott, Outline of a mathematical theory of computation, in: 4th Annual Princeton Conference on Information Sciences and Systems, 1970, 169-176.

M. B. Smyth and G. D. Plotkin, The category-theoretic solution of recursive domain equations, SIAM J. Comput. 11 (1982), 761-783. https://doi.org/10.1137/0211062

V. Stoltenberg-Hansen, I. Lindström and E. R. Griffor, Mathematical Theory of Domains, Cambridge University Press, Cambridge, 1994. https://doi.org/10.1017/CBO9781139166386

G.-Q. Zhang, Logic of Domains, Birkhäuser, Boston, 1991. https://doi.org/10.1007/978-1-4612-0445-9

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM


Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Representations versus numberings: on the relationship of two computability notions
Dieter Spreen
Theoretical Computer Science  vol: 262  issue: 1-2  first page: 473  year: 2001  
doi: 10.1016/S0304-3975(00)00319-4

Esta revista se publica bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Universitat Politècnica de València

e-ISSN: 1989-4147   https://doi.org/10.4995/agt