Power-Domains - Wikipedia

In der Denotationssemantik und Domänentheorie sind Machtdomänen Domänen nichtdeterministischer und gleichzeitiger Berechnungen.

Die Idee der Machtdomänen für Funktionen ist, dass eine nichtdeterministische Funktion als deterministische Mengenwertfunktion beschrieben werden kann, wobei die Menge alle Werte enthält, die die nichtdeterministische Funktion für ein gegebenes Argument annehmen kann. Bei gleichzeitigen Systemen soll die Menge aller möglichen Berechnungen ausgedrückt werden.

Grob gesagt handelt es sich bei einer Energiedomäne um eine Domäne, deren Elemente bestimmte Teilmengen einer Domäne sind. Wenn Sie diesen Ansatz naiv nehmen, entstehen jedoch häufig Domänen, die nicht die gewünschten Eigenschaften haben, und so wird man zu immer komplizierteren Vorstellungen von Machtdomäne geführt. Es gibt drei häufige Varianten: die Plotkin-, oberen und unteren Leistungsdomänen. Eine Möglichkeit, diese Konzepte zu verstehen, ist das freie Modell von Theorien des Nichtdeterminismus.

Für den größten Teil dieses Artikels werden die Begriffe "Domäne" und "kontinuierliche Funktion" ziemlich lose verwendet, was eine Art geordneter Struktur und eine Art begrenzungserhaltende Funktion bedeutet. Diese Flexibilität ist echt. In einigen gleichzeitigen Systemen ist es zum Beispiel normal, die Bedingung aufzustellen, dass jede gesendete Nachricht schließlich zugestellt werden muss. Die Grenze einer Annäherungskette, in der eine Nachricht nicht zugestellt wurde, wäre jedoch eine abgeschlossene Berechnung, bei der die Nachricht nie zugestellt wurde!

Ein moderner Bezug zu diesem Thema ist das Kapitel von Abramsky und Jung [1994]. Ältere Referenzen umfassen diejenigen von Plotkin [1983, Chapter 8] und Smyth [1978].

Machtdomänen als freie Modelle von Theorien des Nichtdeterminismus [ edit ]

Domäne-Theoretiker haben Machtdomänen abstrakt als freie Modelle für Theorien des Nichtdeterminismus verstanden. Ebenso wie die Konstruktion des endlichen Powersets das freie Halbgitter ist, sollten die Machtdomänenkonstruktionen abstrakt als freie Modelle von Theorien des Nicht-Determinismus verstanden werden. Durch die Änderung der Theorien des Nicht-Determinismus entstehen unterschiedliche Machtbereiche.

Die abstrakte Charakterisierung von Powerdomains ist oft der einfachste Weg, um mit ihnen zu arbeiten, da explizite Beschreibungen so kompliziert sind. (Eine Ausnahme ist die Hoare-Powerdomain, die eine ziemlich einfache Beschreibung hat.)

Theorien des Nicht-Determinismus [ edit ]

Wir erinnern uns an drei Theorien des Nicht-Determinismus. Sie sind Variationen der Theorie der Halbgitter. Die Theorien sind keine algebraischen Theorien im herkömmlichen Sinne, da einige die Reihenfolge der zugrunde liegenden Domäne betreffen.

Alle Theorien haben eine Sorte X und eine binäre Operation ∪. Die Idee ist, dass die Operation [: X × X → X zwei Kombinationen verwendet und die nicht deterministische Auswahl davon zurückgibt.

Die Plotkin Powertheory (nach Gordon Plotkin) hat eine Sorte, X und die folgenden Axiome:

• Idempotenz: x [1945 x = x


• Kommutativität: x y y = [1945 x


• Assoziativität: ( x [1945 y ) z = x x x [ ] y ∪ z)

Die niedrigere (oder Hoare nach Tony Hoare) -Powertheorie besteht aus der Plotkin-Powertheory, die mit der Ungleichheit verstärkt wurde

Die obere (oder Smyth nach M. B. Smyth) - Powertheorie besteht aus der Plotkin-Powertheorie, die mit der Ungleichung verstärkt wird

Modelle der Powertheorien [ edit ]

Ein Modell der Plotkin-Powertheorie ist ein fortlaufendes Halbgitter: Es ist ein Halbgitter, dessen Träger eine Domäne ist und für die der Vorgang kontinuierlich ist. Beachten Sie, dass der Betreiber für die Reihenfolge der Domäne kein Meet oder Join sein muss. Ein Homomorphismus kontinuierlicher Halbgitter ist eine kontinuierliche Funktion zwischen ihren Trägern, die den Gitteroperator respektiert.

Modelle der unteren Antriebstheorie werden inflationäre Halbgitter genannt; Es gibt eine zusätzliche Anforderung, dass sich der Operator bei der Bestellung ein bisschen wie ein Join verhält. Für die obere Antriebstheorie werden Modelle als deflationäre Halbgitter bezeichnet. Hier verhält sich der Operator ein bisschen wie ein Treffen.

Stromdomänen als freie Modelle [ edit ]

Lassen Sie D eine Domäne sein. Die Plotkin-Machtdomäne am D ist das freie Modell der Plotkin-Powertheorie über D . Es ist definiert (wenn es existiert) ein Modell P ( D ) der Plotkin-Powertheorie (dh eines kontinuierlichen Halbgitters), das mit einer kontinuierlichen Funktion ausgestattet ist D . → P ( D ), so dass für jedes andere fortlaufende Halbgitter L über D ein eindeutiger durchgehender Halbgitter-Homomorphismus besteht P ( D ) → L das offensichtliche Diagramm pendeln.

Andere Machtbereiche werden auf ähnliche Weise abstrakt definiert.

Explizite Beschreibungen von Machtdomänen [ edit ]

Lassen Sie D eine Domäne sein. Die Domäne mit niedrigerer Leistung kann durch definiert werden

• P [ D ] = {Schließung [ A ] Ø∈ A ⊆ D } wobei

Schließung [ A ] = { d 5 D . | 1945 X ⊆ D X gerichtet d = ${19659036] { displaystyle vee}$ X und x X a a A A A 19659034] x ≤ a }.

Mit anderen Worten: P [ D ist die Sammlung von nach unten geschlossenen Untersätzen von ] D die auch in D unter den vorhandenen Mindestobergrenzen gerichteter Mengen geschlossen sind. Man beachte, dass die Reihenfolge auf P [ D ] durch die Teilmengenbeziehung gegeben ist, die kleinsten oberen Grenzen stimmen im Allgemeinen nicht mit den Gewerkschaften überein.

Es ist wichtig zu prüfen, welche Eigenschaften von Domänen von den Power-Domain-Konstruktionen beibehalten werden. Zum Beispiel ist die Hoare-Powerdomain einer ω-vollständigen Domäne wieder ω-vollständig.

Machtdomänen für Parallelität und Schauspieler [ edit ]

Clingers Machtdomäne [ edit

Clinger [1981] Clinger [1981] konstruierte eine Machtdomäne für das Actor-Modell, das auf der Basisdomäne von Actor-Ereignisdiagrammen aufgebaut ist, was unvollständig ist. Siehe Clinger-Modell.

Zeitdiagramme Stromdomäne [ edit ]

Hewitt [2006] konstruierte eine Machtdomäne für das Actor-Modell (das technisch einfacher und verständlicher ist als das Clinger-Modell) Basisbereich zeitgesteuerter Actor-Ereignisdiagramme. Dies ist abgeschlossen. Die Idee ist, für jede von einem Schauspieler empfangene Nachricht eine Ankunftszeit anzufügen. Siehe Zeitdiagramme.

Verbindungen mit der Topologie und dem Vietoris-Raum [ edit ]

Domänen können als topologische Räume verstanden werden, und in dieser Einstellung können die Machtdomänenkonstruktionen mit verbunden werden ] Raum der Subsets Konstruktion von Leopold Vietoris eingeführt. Siehe zum Beispiel [Smyth 1983].

Referenzen [ edit ]

• Irene Greif. Semantik kommunizierender Parallelprozesse MIT EECS-Doktorarbeit. August 1975.


• Joseph E. Stoy, Denotational Semantics: Der Scott-Strachey-Ansatz zur Programmiersprachen-Semantik . MIT Press, Cambridge, Massachusetts, 1977. (Ein Klassiker, wenn das Lehrbuch datiert ist.)


• Gordon Plotkin. Eine Powerdomain-Konstruktion SIAM Journal on Computing, September 1976.


• Carl Hewitt und Henry Baker Akteure und kontinuierliche Funktionen Durchführung der IFIP-Arbeitskonferenz über formale Beschreibung von Programmierkonzepten. 1. bis 5. August 1977.


• Henry Baker. Aktorsysteme für die Echtzeitberechnung MIT EECS-Doktorarbeit. Januar 1978.


• Michael Smyth. Machtdomänen Zeitschrift für Computer- und Systemwissenschaften. 1978.


• George Milne und Robin Milner. Gleichzeitige Prozesse und ihre Syntax JACM. April 1979.


• CAR Hoare. Kommunizieren sequenzieller Prozesse CACM. August 1978.


• Nissim Francez, CAR Hoare, Daniel Lehmann und Willem de Roever. Semantik von Nichtdeterminismus, Parallelität und Kommunikation Journal of Computer and System Sciences. Dezember 1979.


• Jerald Schwartz Semantik der Parallelität in der Semantik der gleichzeitigen Berechnung. Springer-Verlag. 1979.


• William Wadge. Eine umfangreiche Behandlung des Datenfluss-Deadlocks Semantik der gleichzeitigen Berechnung. Springer-Verlag. 1979.


• Ralph-Johan Back. Semantik des ungebundenen Nondeterminismus ICALP 1980.


• David Park. Zur Semantik des fairen Parallelismus Verfahren der Winter School über formale Software-Spezifikation. Springer-Verlarg. 1980.


• Will Clinger, Foundations of Actor Semantics . MIT Mathematics Dissertation, Juni 1981.


• Gordon Plotkin. Domänen (Anmerkungen aus Pisa) . 1983. Verfügbar ab [1].


• M. B. Smyth, Leistungsdomänen und Prädikattransformatoren: Eine topologische Ansicht LNCS 154, Springer, 1983.


• S. Abramsky, A. Jung: Domänentheorie . In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, Herausgeber, Handbook of Logic in Computer Science, vol. III. Oxford University Press, 1994. (ISBN 0-19-853762-X) (PDF herunterladen PS.GZ)