Abstract
Domain theory studies ordered structures used to model approximation, partial information, and non-termination. It provides a mathematical setting for interpreting recursive definitions and for giving semantics to programs whose computations may proceed by successive approximations.
Definition
In domain theory, one works with partially ordered sets whose order is read as an information order:
means that is at least as defined or informative as .
The basic objects are often complete partial orders or related ordered structures with suprema of suitable directed families. These suprema represent limits of increasing approximations.
Core Ideas
- Approximation: computations are built in stages, starting from incomplete information.
- Bottom element: a least element represents undefinedness or divergence.
- Directed suprema: increasing compatible approximations have a least upper bound.
- Fixed points: recursive definitions are interpreted by least fixed points of suitable monotone or continuous operators.
For an operator , one studies the approximation chain
and interprets the recursive computation by the supremum of this chain.
Applications
Domain theory is central in the semantics of recursive and potentially non-terminating computations.
- It gives semantics to partial programs by treating divergence as genuine mathematical information.
- It supports least fixed-point interpretations of recursive definitions.
- It underlies many constructions related to partial functions and partiality monads.