The Mixed Powerdomain

This paper introduces an operator M called the mixed powerdomain which generalizes the convex (Plotkin) powerdomain. The construction is based on the idea of representing partial information about a set of data items using a pair of sets, one representing partial information in the manner of the upper (Smyth) powerdomain and the other in the manner of the lower (Hoare) powerdomain where the components of such pairs are required to satisfy a consistency condition. This provides a richer family of meaningful partial descriptions than are available in the convex powerdomain and also makes it possible to include the empty set in a satisfactory way. The new construct is given a rigorous mathematical treatment like that which has been applied to the known powerdomains. It is proved that M is a continuous functor on bifinite domains which is left adjoint to the forgetful functor from a category of continuous structures called mix algebras. For a domain D with a coherent Scott topology, elements of M D can be represented as pairs (U, V) where U ⊆ D is a compact upper set, V ⊆ D is a closed set and the downward closure of U ∩ V is equal to V. A Stone dual characterization of M is also provided