Algebraic Characterization of Edible Powerdomains

Powerdomains like mixes, sandwiches, snacks and scones are typically used to provide semantics of collections of descriptions of partial data. In particular, they were used to give semantics of databases with partial information. In this paper we argue that to be able to put these constructions into the context of a programming languages it is necessary to characterize them as free (ordered) algebras. Two characterizations — for mixes and snacks — are already known, and in the first part of the paper we give characterizations for scones and sandwiches and provide an alternative characterization of snacks. The algebras involved have binary and unary operations and relatively simple equational theories. We then define a new construction, which is in essence all others put together (hence called salad) and give its algebraic characterization. It is also shown how all algebras considered in the paper are related in a natural way, that is, in a way that corresponds to embeddings of their powerdomains. We also discuss some semantic issues such as relationship between the orderings and the semantics and justification for choosing the orderings. Finally, we outline prospects for further research.