Zusammenfluss

In der Informatik ist Zusammenfluss eine Eigenschaft des Ersetzungssysteme, die beschreiben, welche Begriffe in einem solchen System kann in mehr als einer Weise umgeschrieben werden, um das gleiche Ergebnis zu erhalten. Dieser Artikel beschreibt die Eigenschaften in der abstraktesten Einstellung eines reduktionssystem.

Motivierende Beispiele

Die üblichen Regeln der elementaren Arithmetik bilden ein abstraktes Neuschreiben-System. Zum Beispiel können die Expressions × beginnend entweder an der linken oder an der rechten Klammern ausgewertet werden; Jedoch wird in beiden Fällen das gleiche Ergebnis wird schließlich erhalten. Dies legt nahe, dass die Rechen Umschreibesystem ein konfluenter eins.

Eine zweite, abstraktes Beispiel wird aus der folgenden Beweis jedes Gruppenelement gleich der Inversen der inversen:

Dieser Beweis geht von der gegebenen Gruppe Axiome A1-A3 und stellt fünf Sätze R4, R6, R10, R11, und R12 jedes von ihnen mit einigen früheren, und R12 ist der Hauptsatz. Einige der Beweise erfordern nicht offensichtlich, wenn nicht kreativ, Schritte, wie die Anwendung Axiom A2 umgekehrt, wodurch Umschreiben "1" bis "a ⋅ a" in der ersten Stufe des R6 Beweis. Einer der historischen Motivationen, die Theorie der Begriff Neuschreiben Entwicklung war es, die Notwendigkeit solcher Schritte, die schwierig durch unerfahrene menschlichen finden sind, zu vermeiden, ganz zu schweigen von einem Computerprogramm.

Wenn ein Termersetzungssystem ist konfluent und Abschluss besteht eine unkomplizierte Methode, um zu beweisen Gleichstellung von zwei Ausdrücke s und t: Beginnend mit s, gelten Gleichheiten von links nach rechts so lange wie möglich, schließlich den Erhalt ein Begriff s '. Erhalten von t einer Laufzeit t 'in ähnlicher Weise. Wenn beide Begriffe s 'und t' buchstäblich einverstanden sind, s und t gleich bewährt. Noch wichtiger ist, wenn sie nicht einverstanden sind, s und t können nicht gleich sein. Das heißt, jede zwei Begriffe s und t, die gleich nachgewiesen werden kann, überhaupt, können so durch diese Methode.

Der Erfolg dieser Methode nicht auf eine bestimmte anspruchsvolle Reihenfolge, in der Rewrite-Regeln gelten ab, als Zusammenfluss gewährleistet, dass jede Folge von Regelanwendungen wird schließlich zu dem gleichen Ergebnis führen. Deshalb, wenn ein konfluenter und Beenden von Termersetzungssystem kann für einige Gleichungstheorie zur Verfügung gestellt werden, nicht ein Hauch von Kreativität ist erforderlich, um Beweise der Begriff Gleichheit durchzuführen; diese Aufgabe wird somit zugänglich für Computerprogramme. Moderne Ansätze behandeln allgemeineren abstrakten Ersetzungssysteme eher als Termersetzungssysteme; Letztere sind ein Spezialfall des ersteren.

Allgemeinen Fall und Theorie

Ein Überschreibungssystem kann als ein gerichteter Graph, bei dem Knoten repräsentieren Ausdrücke und Kanten stellen umschreibt ausgedrückt werden. So, zum Beispiel, wenn der Ausdruck der Dose in b umgeschrieben werden, so sagt man, b eine reduct von a. Dies wird mit Hilfe der Pfeil Notation dargestellt; a → b zeigt, daß eine reduziert auf b. Intuitiv bedeutet dies, dass der entsprechende Graph eine gerichtete Kante von a nach b.

Wenn es einen Weg zwischen zwei Graphknoten C und D, so werden die Zwischenknoten bilden eine Reduktionsfolge. So, zum Beispiel, wenn c → c '→ c' '→ ... → d' → d, dann können wir c → d schreiben, die das Vorhandensein eines Untersetzungssequenz von c nach d. Formal ist → die reflexive-transitive Hülle von →. Am Beispiel vom vorherigen Absatz, haben wir × → 20 × und 20 × → 20 × 6, so × → 20 × 6.

Damit etabliert, können Zusammenfluss wie folgt definiert werden. Lassen Sie a, b, c ∈ S, mit einem → b und c →. a gilt als konfluent wenn es ad ∈ S mit b → d und c → d. Wenn jedes a ∈ S ist konfluent, sagen wir, dass → konfluent ist, oder hat die Church-Rosser-Eigenschaft. Diese Eigenschaft wird auch manchmal den Diamanten Eigenschaft, nach der die Form der Abbildung auf der rechten Seite angezeigt. Einige Autoren behalten tige Diamant Eigenschaft für eine Variante des Diagramms mit Einzelsenkungen überall; das heißt, wann immer ein → B und A → c, muss ad solche bestehen, dass b → d und c → d. Die Single-Reduktion Variante ist strikt stärker als die multi-Reduktion ein.

Lokale Zusammenfluss

Ein Element a ∈ S gilt als lokal konfluent, wenn für alle b, c ∈ S mit einem → b und c → existiert d ∈ S mit b → d und c → * d sein. Wenn jedes a ∈ S lokal konfluent, dann → lokal genannt konfluent oder mit der schwachen Church-Rosser-Eigenschaft. Dies unterscheidet sich von Konfluenz daß b und c von einem in einem Schritt reduziert werden. In Analogie dazu wird Konfluenz manchmal als globale Zusammen bezeichnet.

Die Beziehung →, als Notation für Reduktionssequenzen eingeführt, kann als ein Neuschreiben-System in seinem eigenen Recht, dessen Beziehung ist die reflexive-transitive Hülle von → betrachtet werden. Seit einer Reihe von Reduktionssequenzen ist wieder eine Reduktion Sequenz, → = →. Daraus folgt, daß → konfluent ist, wenn und nur wenn → lokal konfluent.

Eine Überschreibungssystem lokal konfluent ohne konfluent sein. Beispiele sind in Bild 3 und 4 jedoch gezeigt, Newman Lemma besagt, dass wenn ein lokal konfluent Umschreibesystem hat keine unendliche Reduktion Sequenzen, dann ist es global konfluent.

Semi-Mündung

Die Definition der lokalen Zusammenfluss unterscheidet sich von der globalen Konfluenz, dass nur Elemente aus einem bestimmten Element in einem einzigen Schritt Neuschreiben betrachtet erreicht. Durch Betrachtung eines Elements in einem einzigen Schritt und ein anderes Element durch eine beliebige Sequenz erreicht erreicht, kommen wir zu dem Zwischenbegriff halb Konfluenz: a ∈ S wird gesagt, dass halbkonfluente wenn für alle b, c ∈ S mit a → b und a → c existiert, d ∈ S mit b → d und c → d; wenn jedes a ∈ S ist halbkonfluenten, sagen wir, dass → ist halbkonfluenten.

A halbkonfluente Element nicht konfluent werden, aber ein halbkonfluente Umschreibesystem notwendigerweise konfluent und eine konfluente System trivial halbkonfluente.

Starke Zusammenfluss

Starke Zusammenfluss ist eine weitere Variation über lokale Zusammenfluss, die uns zu dem Schluss, dass eine Überschreibungssystem ist weltweit konfluenten ermöglicht. Ein Element a ∈ S gilt als stark konfluent werden, wenn für alle b, c ∈ S mit einem → b und c → existiert d ∈ S mit b → d, und entweder c → d oder c = d; wenn jedes a ∈ S ist stark konfluent, sagen wir, dass → stark konfluent wird.

Ein stark konfluenten Element nicht konfluent werden, aber eine stark konfluent Umschreibesystem notwendigerweise konfluent.

Beispiele für Zusammenflusssysteme

  • Reduzierung der Polynome modulo ideal ist eine konfluente Rewrite System man arbeitet mit einer Gröbner-Basis.
  • Matsumoto-Theorem folgt, Zusammenfluss der Geflecht Beziehungen.
  0   0
Vorherige Artikel 2009-10 ukrainischen Cup
Nächster Artikel Camp Bondsteel

In Verbindung Stehende Artikel

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha