domain theory

theory A branch of mathematics introduced by Dana Scott in

1970 as a mathematical theory of programming languages, and

for nearly a quarter of a century developed almost exclusively

in connection with denotational semantics in computer

science.

In denotational semantics of programming languages, the

meaning of a program is taken to be an element of a domain. A

domain is a mathematical structure consisting of a set of

values (or "points") and an ordering relation, #@= on those

values. Domain theory is the study of such structures.

("=" is written in LaTeX as subseteq)

Different domains correspond to the different types of object

with which a program deals. In a language containing

functions, we might have a domain X - Y which is the set of

functions from domain X to domain Y with the ordering f #@= g

iff for all x in X, f x = g x. In the pure lambda-calculus

all objects are functions or applications of functions to

other functions. To represent the meaning of such programs,

we must solve the recursive equation over domains,

D = D - D

which states that domain D is (isomorphic to) some functionspace from D to itself. I.e. it is a fixed point D = F(D)

for some operator F that takes a domain D to D -@# D. The

equivalent equation has no non-trivial solution in settheory.

There are many definitions of domains, with different

properties and suitable for different purposes. One commonly

used definition is that of Scott domains, often simply called

domains, which are omega-algebraic, consistently complete

CPOs.

There are domain-theoretic computational models in other

branches of mathematics including dynamical systems,

fractals, measure theory, integration theory,

probability theory, and stochastic processes.

See also abstract interpretation, bottom, pointeddomain.

(1999-12-09)