The Smyth powerdomain [dt-0064]

As before, let X, Y \in \mathcal {P}_f^\ast (\mathsf {K}(A)) be finite, non-empty sets of compact elements of a Scott domain A. The Smyth powerdomain construction is based on the following preorder: X \preceq _S Y\quad \text {iff}\quad (\forall y \in Y.\ \exists x \in X.\ x \sqsubseteq _A y) The intuition here is "Everything Y can do, X can do worse". It satisfies the equation X \cup Y \preceq _S X, which intuitively means that a non-deterministic choice is considered to have less information than any of its components. When applied to a flat domain, it simplifies to: X \preceq _S Y\quad \text {iff}\quad \bot \in X \lor Y \subseteq X As with the Hoare powerdomain, this fails to be a partial order, but we can use the same ideal completion trick to induce an algebraic domain where compact elements correspond to equivalence classes of elements under \approx _S (where X \approx _S Y is, as with \approx _H, just defined as X \preceq _S Y \land Y \preceq _S X).

Context

Lecture. Domain theory › Monadic semantics, Scott domains and nondeterminism [dt-005V]

Backlinks

Remark. Demonic nondeterminism [dt-0066]

The Plotkin powerdomain [dt-0067]

Related

Definition. Algebraicity [dt-0041]

Definition. Compactness [dt-003U]

Definition. Equivalence class [dm-000X]

Definition. Flat domain [dt-0008]

Definition. Ideal completion [dt-0046]

Definition. Partial order [dm-0000]

Preorder [dm-000V]

Definition. Scott domain [dt-004G]

The Hoare powerdomain [dt-0061]