powerdomains

Powerdomains are a family of constructions in domain theory used to model nondeterministic computation in the denotational semantics of programming languages. Given a base domain D, a powerdomain P(D) is a new domain whose elements are certain sets of elements of D. Intuitively, these sets represent the possible outcomes of a computation that may nondeterministically choose among several results. The order on P(D) is chosen so that the domain structure is preserved, making P(D) a dcpo (or more generally a domain) and enabling the interpretation of fixed-point operators.

The three canonical variants, often discussed in the literature, are the lower (Hoare) powerdomain, the upper (Smyth) powerdomain, and the Plotkin (convex) powerdomain. The lower powerdomain uses nonempty downward-closed (lower) sets of D, the upper powerdomain uses nonempty upward-closed (upper) sets, and the Plotkin powerdomain uses nonempty convex subsets. Each variant embodies a different way of interpreting nondeterminism and thus supports different semantic notions, such as may, must, or mixed semantics.

Powerdomains are monadic constructions: there is a unit that embeds D into P(D) by singletons and a multiplication that flattens nests of nondeterminism. They generalize the powerset construction to the setting of domains and retain continuity properties important for fixed-point reasoning.

Extensions include probabilistic powerdomains, which combine nondeterminism with probabilistic choice, and other refined constructions for concurrent or quantitative semantics. Powerdomains thus provide a foundational tool for reasoning about programs with nondeterministic behavior.