The mixed powerdomain

Research output: Contribution to journalArticle

Abstract

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 MD 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 {frown} V is equal to V. A Stone dual characterization of M is also provided.

Original languageEnglish (US)
Pages (from-to)311-334
Number of pages24
JournalTheoretical Computer Science
Volume103
Issue number2
DOIs
StatePublished - Sep 14 1992
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The mixed powerdomain'. Together they form a unique fingerprint.

  • Cite this