Power domains

Power domains

In denotational semantics and domain theory, power domains are domains of nondeterministic and concurrent computations.

The idea of power domains for functions is that a nondeterministic function may be described as a deterministic set-valued function, where the set contains all values the nondeterministic function can take for a given argument. For concurrent systems, the idea is to express the set of all possible computations.

Roughly speaking, a power domain is a domain whose elements are certain subsets of a domain. Taking this approach naively, though, often gives rise to domains that don't quite have the desired properties, and so one is led to increasingly complicated notions of power domain. There are three common variants: the Plotkin, upper, and lower power domains. One way to understand these concepts is as free models of theories of nondeterminism.

For most of this article we use the terms "domain" and of "continuous function" quite loosely, meaning respectively some kind of ordered structure and some kind of limit-preserving function. This flexibility is genuine; for example, in some concurrent systems it is natural to impose the condition that every message sent must eventually be delivered. However, the limit of a chain of approximations in which a message was not delivered, would be a completed computation in which the message was never delivered!

A modern reference to this subject is the chapter of Abramsky and Jung [1994] . Older references include those of Plotkin [1983, Chapter 8] and Smyth [1978] .

Power domains as free models of theories of non-determinism

Domain theorists have come to understand power domains abstractly as free models for theories of non-determinism. Just as the finite-powerset construction is the free semilattice, the powerdomain constructions should be understood abstractly as free models of theories of non-determinism. By changing the theories of non-determinism, different power domains arise.

The abstract characterisation of powerdomains is often the easiest way to work with them, because explicit descriptions are so intricate. (One exception is the Hoare powerdomain, which has a rather straightforward description.)

Theories of non-determinism

We recall three theories of non-determinism. They are variations of the theory of semilattices. The theories are not algebraic theories in the conventional sense, because some involve the order of the underlying domain.

All theories have one sort "X", and one binary operation ∪. The idea is that the operation "∪:X×X→X" takes two combinations and returns the non-deterministic choice of them.

The Plotkin powertheory (after Gordon Plotkin) has one sort, "X", and the following axioms:
* Idempotency: "x∪x"="x"
* Commutativity: "x∪y"="y∪x"
* Associativity: "(x∪y)∪z"="x∪(y∪z)"

The lower (or Hoare, after Tony Hoare) powertheory consists of the Ploktin powertheory augmented with the inequality
* "x"≤"x∪y".

The upper (or Smyth, after M. B. Smyth) powertheory consists of the Ploktin powertheory augmented with the inequality
* "x∪y"≤"x".

Models of the powertheories

A model of the Plotkin powertheory is a continuous semilattice: it is a semilattice whose carrier is a domain and for which the operation is continuous. Note that the operator need not be a meet or join for the order of the domain. A homorphism of continuous semilattices is a continuous function between their carriers that respects the lattice operator.

Models of the lower powertheory are called inflationary semilattices; there is an additional requirement that the operator behave a little like a join for the order. For the upper powertheory, models are called deflationary semilattices; here, the operator behaves a little like a meet.

Power domains as free models

Let "D" be a domain. The Plotkin powerdomain on "D" is the free model of the Plotkin powertheory over "D". It is defined to be (when it exists) a model "P"("D") of the Plotkin powertheory (ie a continuous semilattice) equipped with a continuous function "X"→"P"("D") such that for any other continuous semilattice "L" over "D", there is a unique continuous semilattice homomorphism "P"("D")→"L" making the evident diagram commute.

Other powerdomains are defined abstractly in a similar manner.

Explicit descriptions of power domains

Let "D" be a domain. The lower power domain can be defined by
* "P" ["D"] = {closure ["A"] | Ø∈"A"⊆"D"} where::::"closure" ["A"] = {"d"∈"D" | ∃"X"⊆"D", "X" "directed", "d" = vee "X", "and" ∀"x"∈"X" ∃"a"∈"A" "x"≤"a"}.

In other words, "P" ["D"] is the collection of downward-closed subsets of "D" that are also closed under existing least upper bounds of directed sets in "D". Note that while the ordering on "P" ["D"] is given by the subset relation, least upper bounds do not in general coincide with unions.

It is important to check which properties of domains are preserved by the power domain constructions. For example, the Hoare powerdomain of an ω-complete domain is again ω-complete.

Power domains for concurrency and Actors

Clinger's power domain

Clinger [1981] constructed a power domain for the Actor model building on the base domain of Actor event diagrams, which is incomplete. See Clinger's model.

Timed diagrams power domain

Hewitt [2006] constructed a power domain for the Actor model (which is technically simpler and easier to understand than Clinger's model) building on a base domain of timed Actor event diagrams, which is complete. The idea is to attach an arrival time for each message received by an Actor. See Timed Diagrams Model.

Connections with topology and the Vietoris space

Domains can be understood as topological spaces, and, in this setting, the power domain constructions can be connected with the "space of subsets" construction introduced by Leopold Vietoris. See, for instance, [Smyth 1983] .

References

*Irene Greif. "Semantics of Communicating Parallel Professes" MIT EECS Doctoral Dissertation. August 1975.
* Joseph E. Stoy, "Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics". MIT Press, Cambridge, Massachusetts, 1977. (A classic if dated textbook.)
* Gordon Plotkin. "A powerdomain construction" SIAM Journal of Computing September 1976.
* Carl Hewitt and Henry Baker "Actors and Continuous Functionals" Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977.
* Henry Baker. "Actor Systems for Real-Time Computation" MIT EECS Doctoral Dissertation. January 1978.
* Michael Smyth. "Power domains" Journal of Computer and System Sciences. 1978.
* George Milne and Robin Milner. "Concurrent processes and their syntax" JACM. April, 1979.
* CAR Hoare. "Communicating Sequential Processes" CACM. August, 1978.
* Nissim Francez, CAR Hoare, Daniel Lehmann, and Willem de Roever. "Semantics of nondeterminism, concurrency, and communication" Journal of Computer and System Sciences. December 1979.
* Jerald Schwartz "Denotational semantics of parallelism" in Semantics of Concurrent Computation. Springer-Verlag. 1979.
* William Wadge. "An extensional treatment of dataflow deadlock" Semantics of Concurrent Computation. Springer-Verlag. 1979.
* Ralph-Johan Back. "Semantics of Unbounded Nondeterminism" ICALP 1980.
* David Park. "On the semantics of fair parallelism" Proceedings of the Winter School on Formal Software Specification. Springer-Verlarg. 1980.
* Will Clinger, "Foundations of Actor Semantics". MIT Mathematics Doctoral Dissertation, June 1981.
* Gordon Plotkin. "Domains (Pisa notes)". 1983. Available from [http://homepages.inf.ed.ac.uk/gdp/publications/] .
* M. B. Smyth, "Power domains and predicate transformers: A topological view", LNCS 154, Springer, 1983.
* S. Abramsky, A. Jung: "Domain theory". In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, vol. III. Oxford University Press, 1994. (ISBN 0-19-853762-X) (download [http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.pdf PDF] [http://www.cs.bham.ac.uk/~axj/pub/papers/handy1.ps.gz PS.GZ] )


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Power graph analysis — In computational biology, power graph analysis is a method for the analysis andrepresentation of complex networks. Power graph analysis is the computation, analysis and visual representation of a power graph from a graphs (networks).Power graph… …   Wikipedia

  • Common Power Format — The Si2 Common Power Format, or CPF is a file format for specifying power saving techniques early in the design process. In the design of integrated circuits, saving power is a primary goal, and designers are forced to use sophisticated… …   Wikipedia

  • United-domains — United Internet AG Unternehmensform Aktiengesellschaft ISIN …   Deutsch Wikipedia

  • Infrastructural power — is the capacity of the state to penetrate civil society and to use this penetration to enforce policy throughout its entire territory. [1] The concept of infrastructural power was introduced by sociologist Michael Mann in his article The… …   Wikipedia

  • Career domains in computer science — The knowledge developed by academic computer science (CS) is applied to various non academic situations to arrive at systems that help humans perform tasks that were either out of their reach for being too complex or the tasks that are repetitive …   Wikipedia

  • Denotational semantics of the Actor model — The denotational semantics of the Actor model is the subject of denotational domain theory for Actors. The historical development of this subject is recounted in [Hewitt 2008b]. Contents 1 Actor fixed point semantics 2 Compositionality in… …   Wikipedia

  • Denotational semantics — In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach to formalizing the meanings of programming languages by constructing mathematical objects (called denotations)… …   Wikipedia

  • Completeness (order theory) — In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). A special use of the term refers to complete partial orders or complete lattices.… …   Wikipedia

  • IEEE P1801 — As of November 2007, the IEEE Standards Association DASC sponsored working group IEEE P1801 is working on extending the capabilities of the draft standard contributed by Accellera and extended by the committee to: * clarify the semantics of the… …   Wikipedia

  • Unbounded nondeterminism — In computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”