Knuth-Bendix-Vervollständigungsalgorithmus - Knuth–Bendix completion algorithm

Die Knuth-Bendix Vervollständigung Algorithmus (benannt nach Donald Knuth und Peter Bendix) ist ein semi-Entscheidungsalgorithmus einen Satz von für die Transformation von Gleichungen (über Bedingungen ) in einen konfluenten Begriff Schreibungssystem . Wenn der Algorithmus erfolgreich ist, löst er effektiv das Wortproblem für die angegebene Algebra .

Der Buchberger-Algorithmus zur Berechnung von Gröbner-Basen ist ein sehr ähnlicher Algorithmus. Obwohl unabhängig entwickelt, kann es auch als Instantiierung des Knuth-Bendix-Algorithmus in der Theorie der Polynomringe angesehen werden .

Einführung

Für eine Menge E von Gleichungen ist ihre deduktive Abgeschlossenheit (Ich⟷E) ist die Menge aller Gleichungen, die durch Anwendung von Gleichungen aus E in beliebiger Reihenfolge abgeleitet werden können. Formal wird E als binäre Relation betrachtet , (⟶E) ist die Umschreibungsschließung und (Ich⟷E) ist der Äquivalenzabschluss von (⟶E). Für eine Menge R von Rewrite-Regeln ist ihre deduktive Schließung (Ich⟶R ∘ Ich⟵R) ist die Menge aller Gleichungen, die durch Anwenden von Regeln von R von links nach rechts auf beide Seiten bestätigt werden können, bis sie buchstäblich gleich sind. Formal wird R wieder als binäre Relation betrachtet, (⟶R) ist der Umschreibeschluss, (⟵R) ist die Umkehrung und (Ich⟶R ∘ Ich⟵R) ist die Relationszusammensetzung ihrer reflexiven transitiven Abschlüsse (Ich⟶R und Ich⟵R).

Wenn beispielsweise E = {1⋅ x = x , x ⁻¹ ⋅ x = 1, ( x ⋅ y )⋅ z = x ⋅( y ⋅ z )} die Gruppenaxiome sind , ist die Ableitungskette

a ⁻¹ ⋅( a ⋅ b )   Ich⟷E   ( a ⁻¹ ⋅ a )⋅ b   Ich⟷E   1⋅ b   Ich⟷E   B

zeigt, dass a ⁻¹ ⋅( a ⋅ b ) Ich⟷E b ist ein Mitglied des deduktiven Abschlusses von E. Wenn R = { 1⋅ x → x , x ⁻¹ ⋅ x → 1, ( x ⋅ y )⋅ z → x ⋅( y ⋅ z ) } eine "Umschreibregel"-Version von E ist , sind die Ableitungsketten

( a ⁻¹ ⋅ a )⋅ b   Ich⟶R   1⋅ b   Ich⟶R   b       und       b   Ich⟵R   B

Zeigen Sie, dass ( a ⁻¹ ⋅ a )⋅ b Ich⟶R∘Ich⟵R b ist ein Mitglied des deduktiven Abschlusses von R. Es gibt jedoch keine Möglichkeit, a ⁻¹ ⋅( a ⋅ b ) abzuleitenIch⟶R∘Ich⟵R b ähnlich wie oben, da eine von rechts nach links Anwendung der Regel ( x ⋅ y ) ⋅ z → x ⋅ ( y ⋅ Z ) ist nicht erlaubt.

Der Knuth-Bendix-Algorithmus verwendet einen Satz E von Gleichungen zwischen Termen und eine Reduktionsordnung (>) für den Satz aller Terme und versucht, ein konfluentes und terminierendes Termumschreibsystem R zu konstruieren , das dieselbe deduktive Abgeschlossenheit wie E hat . Während der Beweis von Konsequenzen aus E oft menschliche Intuition erfordert, ist der Beweis von Konsequenzen aus R nicht erforderlich. Weitere Einzelheiten finden Sie unter Confluence (abstract rewriting)#Motivating Examples , das einen Beispielbeweis aus der Gruppentheorie liefert, der sowohl mit E als auch mit R durchgeführt wurde .

Regeln

Bei einem gegebenen Satz E von Gleichungen zwischen Termen können die folgenden Inferenzregeln verwendet werden, um ihn in ein äquivalentes konvergentes Term-Umschreibsystem zu transformieren (wenn möglich): Sie basieren auf einer benutzerdefinierten Reduktionsreihenfolge (>) auf der Menge aller Terme ; es wird auf eine wohlbegründete Ordnung (▻) auf dem Satz von Rewrite-Regeln gehoben, indem man ( s → t ) ▻ ( l → r ) if . definiert

• S >e l , oder
• s und l sind buchstäblich ähnlich und t > r .

Löschen	‹  E ∪{ s = s }	, R  ›	⊢	‹  E	, R  ›
Komponieren	‹  E	, R ∪{ s → t } ›	⊢	‹  E	, R ∪{ s → u } ›	wenn ich ⟶R du
Vereinfachen	‹  E ∪{ s = t }	, R  ›	⊢	‹  E ∪{ s = u }	, R  ›	wenn ich ⟶R du
Orient	‹  E ∪{ s = t }	, R  ›	⊢	‹  E	, R ∪{ s → t } ›	wenn s > t
Zusammenbruch	‹  E	, R ∪{ s → t } ›	⊢	‹  E ∪{ u = t }	, R  ›	wenn ja ⟶R u um l → r mit ( s → t ) ▻ ( l → r )
Ableiten	‹  E	, R  ›	⊢	‹  E ∪{ s = t }	, R  ›	wenn ( s , t ) ein kritisches Paar von R . ist

Beispiel

Der folgende Beispiellauf, der aus dem E-Theorem-Beweiser erhalten wurde , berechnet eine Vervollständigung der (additiven) Gruppenaxiome wie in Knuth, Bendix (1970). Es beginnt mit den drei Anfangsgleichungen für die Gruppe (neutrales Element 0, inverse Elemente, Assoziativität) f(X,Y)für X + Y und i(X)für − X . Es stellt sich heraus, dass die 10 mit Sternen versehenen Gleichungen das resultierende konvergente Rewrite-System bilden. "pm" ist die Abkürzung für " paramodulation ", Implementierung deduce . Die Berechnung kritischer Paare ist ein Fall von Paramodulation für Gleichungseinheitenklauseln. „rw“ neu schreibt, Implementierung compose , Zusammenbruch und vereinfachen . Die Ausrichtung der Gleichungen erfolgt implizit und wird nicht aufgezeichnet.

Nr		Lhs		Rhs	Quelle
1:	*	f(X,0)	=	x	initial("GROUP.lop", at_line_9_column_1)
2:	*	f(X,i(X))	=	0	initial("GROUP.lop", at_line_12_column_1)
3:	*	f(f(X,Y),Z)	=	f(X,f(Y,Z))	initial("GROUP.lop", at_line_15_column_1)
5:		f(X,Y)	=	f(X,f(0,Y))	Uhr(3,1)
6:		f(X,f(Y,i(f(X,Y))))	=	0	pm(2,3)
7:		f(0,Y)	=	f(X,f(i(X),Y))	Uhr(3,2)
27:		f(X,0)	=	f(0,i(i(X)))	pm(7,2)
36:		x	=	f(0,i(i(X)))	rw(27,1)
46:		f(X,Y)	=	f(X,i(i(Y)))	Uhr(5,36)
52:	*	f(0,X)	=	x	rw(36,46)
60:	*	ich(0)	=	0	pm(2,52)
63:		i(i(X))	=	f(0,X)	Uhr(46,52)
64:	*	f(X,f(i(X),Y))	=	Ja	rw(7,52)
67:	*	i(i(X))	=	x	rw(63,52)
74:	*	f(i(X),X)	=	0	Uhr(2,67)
79:		f(0,Y)	=	f(i(X),f(X,Y))	pm(3,74)
83:	*	Ja	=	f(i(X),f(X,Y))	rw(79,52)
134:		f(i(X),0)	=	f(Y,i(f(X,Y)))	Uhr(83,6)
151:		ich(X)	=	f(Y,i(f(X,Y)))	rw(134,1)
165:	*	f(i(X),i(Y))	=	i(f(Y,X))	pm(83,151)

Siehe auch Word-Aufgabe (Mathematik) für eine weitere Darstellung dieses Beispiels.

String-Rewriting-Systeme in der Gruppentheorie

Ein wichtiger Fall in der rechnerischen Gruppentheorie sind String - Rewriting - Systeme , die verwendet werden können , um Elementen oder Nebenklassen einer endlich präsentierten Gruppe als Produkte der Generatoren kanonische Labels zu geben . Dieser Sonderfall steht im Mittelpunkt dieses Abschnitts.

Motivation in der Gruppentheorie

Das Lemma kritischer Paare besagt, dass ein Termumschreibsystem genau dann lokal konfluent (oder schwach konfluent) ist, wenn alle seine kritischen Paare konvergent sind. Darüber hinaus haben wir das Lemma von Newman, das besagt, dass wenn ein (abstraktes) Umschreibsystem stark normalisiert und schwach konfluent ist, dann ist das Umschreibsystem konfluent. Wenn wir also dem Begriff Rewriting-System Regeln hinzufügen können, um zu erzwingen, dass alle kritischen Paare konvergent sind, während die starke Normalisierungseigenschaft beibehalten wird, dann wird dies das resultierende Rewriting-System zwingen, konfluent zu sein.

Betrachten Sie ein endlich präsentiertes Monoid, wobei X eine endliche Menge von Generatoren und R eine Menge von definierenden Relationen auf X ist. Sei X ^* die Menge aller Wörter in X (dh das von X erzeugte freie Monoid). Da die Relationen R eine Äquivalenzrelation auf X* erzeugen, kann man Elemente von M als Äquivalenzklassen von X ^* unter R betrachten. Für jede Klasse {w ₁ , w ₂ , ... } ist es wünschenswert, einen Standard zu wählen Vertreter w _k . Dieser Repräsentant wird die kanonische oder normale Form für jedes Wort w _k in der Klasse genannt. Wenn es ein berechenbares Verfahren gibt, um für jedes w _k seine Normalform w _i zu bestimmen, dann ist das Wortproblem leicht zu lösen. Ein konfluentes Rewriting-System ermöglicht genau dies. ${\displaystyle M=\langle X\mid R\rangle}$

Obwohl die Wahl einer kanonischen Form theoretisch beliebig erfolgen kann, ist dieser Ansatz im Allgemeinen nicht berechenbar. (Beachten Sie, dass eine Äquivalenzrelation auf einer Sprache unendlich viele unendliche Klassen erzeugen kann.) Wenn die Sprache wohlgeordnet ist, dann liefert die Ordnung < eine konsistente Methode zur Definition minimaler Repräsentanten, jedoch ist die Berechnung dieser Repräsentanten möglicherweise immer noch nicht möglich. Insbesondere wenn ein Rewriting-System verwendet wird, um minimale Repräsentanten zu berechnen, sollte die Reihenfolge < auch die Eigenschaft haben:

A < B → XAY < XBY für alle Wörter A,B,X,Y

Diese Eigenschaft wird als Translationsinvarianz bezeichnet . Eine Ordnung, die sowohl translationsinvariant als auch wohlgeordnet ist, wird Reduktionsordnung genannt .

Aus der Darstellung des Monoids lässt sich ein durch die Relationen R gegebenes Umschreibsystem definieren. Wenn A x B in R ist, dann ist entweder A < B, dann ist B → A eine Regel im Umschreibsystem, ansonsten A > B und A → B. Da < eine Reduktionsordnung ist, kann ein gegebenes Wort W reduziert werden W > W_1 > ... > W_n wobei W_n unter dem Umschreibsystem irreduzibel ist. Abhängig von den Regeln, die bei jedem W _i  → W _i+1 angewendet werden, kann es jedoch zu zwei verschiedenen irreduziblen Reduktionen W _n  ≠ W' _m von W kommen zu einem konfluenten Umschreibungssystem über den Knuth-Bendix-Algorithmus, dann erzeugen alle Reduktionen garantiert das gleiche irreduzible Wort, nämlich die Normalform für dieses Wort.

Beschreibung des Algorithmus für endlich präsentierte Monoide

Angenommen, wir erhalten eine Präsentation , in der ein Satz von Generatoren und ein Satz von Beziehungen das Rewriting-System darstellen. Nehmen wir weiter an, dass wir eine Reduktionsreihenfolge zwischen den Wörtern haben, die von erzeugt werden (zB shortlex order ). Angenommen für jede Beziehung in . Wir beginnen also mit der Menge der Reduktionen . ${\displaystyle \langle X\mid R\rangle }$${\displaystyle X}$${\displaystyle R}$${\displaystyle <}$${\displaystyle X}$${\displaystyle P_{i}=Q_{i}}$${\displaystyle R}$${\displaystyle Q_{i}<P_{i}}$${\displaystyle P_{i}\rightarrow Q_{i}}$

Erstens, wenn eine Beziehung reduziert werden kann, ersetzen Sie und mit den Reduzierungen. ${\displaystyle P_{i}=Q_{i}}$${\displaystyle P_{i}}$${\displaystyle Q_{i}}$

Als Nächstes fügen wir weitere Reduzierungen (d. h. Umschreibungsregeln) hinzu, um mögliche Ausnahmen des Zusammenflusses zu eliminieren. Angenommen, und überlappen. ${\displaystyle P_{i}}$${\displaystyle P_{j}}$

1. Fall 1: Entweder ist das Präfix von gleich dem Suffix von oder umgekehrt. Im ersteren Fall können wir schreiben und ; im letzteren Fall und .${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle P_{i}=BC}$${\displaystyle P_{j}=AB}$${\displaystyle P_{i}=AB}$${\displaystyle P_{j}=BC}$
2. Fall 2: entweder ist vollständig in (umgeben von) enthalten oder umgekehrt. Im ersteren Fall können wir schreiben und ; im letzteren Fall und .${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle P_{i}=B}$${\displaystyle P_{j}=ABC}$${\displaystyle P_{i}=ABC}$${\displaystyle P_{j}=B}$

Reduzieren Sie das Wort mit first, dann mit first. Rufen Sie die Ergebnisse auf. Wenn , dann haben wir eine Instanz, in der die Konfluenz fehlschlagen könnte. Addieren Sie daher die Reduktion zu . ${\displaystyle ABC}$${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1}\neq r_{2}}$${\displaystyle \max r_{1},r_{2}\rightarrow \min r_{1},r_{2}}$${\displaystyle R}$

Nachdem Sie eine Regel zu hinzugefügt haben , entfernen Sie alle Regeln , die möglicherweise reduzierbare linke Seiten haben (nachdem Sie überprüft haben, ob diese Regeln kritische Paare mit anderen Regeln aufweisen). ${\displaystyle R}$${\displaystyle R}$

Wiederholen Sie den Vorgang, bis alle überlappenden linken Seiten überprüft wurden.

Beispiele

Ein abschließendes Beispiel

Betrachten Sie das Monoid:

${\displaystyle \langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle}$.

Wir verwenden die Shortlex-Bestellung . Dies ist ein unendliches Monoid, aber dennoch kann der Knuth-Bendix-Algorithmus das Wortproblem lösen.

Unsere ersten drei Ermäßigungen sind daher

${\displaystyle x^{3}\rightarrow 1}$

( 1 )

${\displaystyle y^{3}\rightarrow 1}$

( 2 )

${\displaystyle (xy)^{3}\rightarrow 1}$.

( 3 )

Ein Suffix von (nämlich ) ist ein Präfix von , also betrachten Sie das Wort . Reduzieren mit ( 1 ) erhalten wir . Reduzieren mit ( 3 ) erhalten wir . Damit erhalten wir , was die Reduktionsregel ${\displaystyle x^{3}}$${\displaystyle x}$${\displaystyle (xy)^{3}=xyxyxy}$${\displaystyle x^{3}yxyxy}$${\displaystyle yxyxy}$${\displaystyle x^{2}}$${\displaystyle yxyxy=x^{2}}$

${\displaystyle yxyxy\rightarrow x^{2}}$.

( 4 )

In ähnlicher Weise erhalten wir durch Verwenden und Reduzieren mit ( 2 ) und ( 3 ) . Daher die Reduktion ${\displaystyle xyxyxy^{3}}$${\displaystyle xyxyx=y^{2}}$

${\displaystyle xyxyx\rightarrow y^{2}}$.

( 5 )

Beide Regeln sind veraltet ( 3 ), daher entfernen wir sie.

Betrachten Sie als nächstes, indem Sie ( 1 ) und ( 5 ) überlappen . Reduzieren wir erhalten , also fügen wir die Regel hinzu ${\displaystyle x^{3}yxyx}$${\displaystyle yxyx=x^{2}y^{2}}$

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$.

( 6 )

Betrachten wir durch Überlappen von ( 1 ) und ( 5 ), erhalten wir , also fügen wir die Regel hinzu ${\displaystyle xyxyx^{3}}$${\displaystyle xyxy=y^{2}x^{2}}$

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

( 7 )

Diese veralteten Regeln ( 4 ) und ( 5 ), deshalb entfernen wir sie.

Jetzt bleibt uns das Umschreibsystem

${\displaystyle x^{3}\rightarrow 1}$

( 1 )

${\displaystyle y^{3}\rightarrow 1}$

( 2 )

${\displaystyle yxyx\rightarrow x^{2}y^{2}}$

( 6 )

${\displaystyle y^{2}x^{2}\rightarrow xyxy}$.

( 7 )

Wenn wir die Überschneidungen dieser Regeln überprüfen, finden wir keine möglichen Fehler bei der Konfluenz. Daher haben wir ein konfluentes Umschreibungssystem und der Algorithmus wird erfolgreich beendet.

Ein nicht abschließendes Beispiel

Die Reihenfolge der Generatoren kann entscheidend beeinflussen, ob die Knuth-Bendix-Vervollständigung beendet wird. Betrachten Sie als Beispiel die freie Abelsche Gruppe durch die Monoiddarstellung:

${\displaystyle \langle x,y,x^{-1},y^{-1}\,|\,xy=yx,xx^{-1}=x^{-1}x=yy^{- 1}=y^{-1}y=1\rangle.}$

Die Knuth-Bendix-Vervollständigung in Bezug auf die lexikographische Ordnung endet mit einem konvergenten System, jedoch in Anbetracht der längenlexikographischen Ordnung nicht, da es keine endlichen konvergenten Systeme gibt, die mit dieser letzteren Ordnung kompatibel sind. ${\displaystyle x<x^{-1}<y<y^{-1}}$${\displaystyle x<y<x^{-1}<y^{-1}}$

Verallgemeinerungen

Wenn Knuth-Bendix nicht erfolgreich ist, wird es entweder ewig laufen oder scheitern, wenn es auf eine nicht ausrichtbare Gleichung stößt (dh eine Gleichung, die es nicht in eine Umschreibregel umwandeln kann). Die verbesserte Vervollständigung ohne Fehler wird bei nicht orientierbaren Gleichungen nicht fehlschlagen und stellt ein Halbentscheidungsverfahren für das Wortproblem bereit .

Der Begriff des protokollierten Umschreibens , der in dem unten aufgeführten Aufsatz von Heyworth und Wensley diskutiert wird, ermöglicht eine gewisse Aufzeichnung oder Protokollierung des Umschreibprozesses, während er fortschreitet. Dies ist nützlich, um Identitäten zwischen Beziehungen für Präsentationen von Gruppen zu berechnen.

Verweise

• D. Knuth; P. Bendix (1970). J. Blutegel (Hrsg.). Einfache Wortaufgaben in universellen Algebren (PDF) . Pergamon-Presse. S. 263–297.
• Gérard Huet (1981). "Ein vollständiger Beweis für die Richtigkeit des Knuth-Bendix-Vervollständigungsalgorithmus" (PDF) . J. Computer. Syst. Sci . 23 (1): 11–21. doi : 10.1016/0022-0000(81)90002-7 .
• C. Sims. 'Berechnungen mit endlich präsentierten Gruppen.' Cambridge, 1994.
• Anne Heyworth und CD Wensley. " Protokollierte Umschreibungen und Identitäten unter den Relatoren ." Gruppen St. Andrews 2001 in Oxford. vol. I, 256–276, London Math. Soz. Vorlesungsnotiz Ser., 304, Cambridge Univ. Presse, Cambridge, 2003.

Externe Links

• Weisstein, Eric W. "Knuth-Bendix Completion Algorithm" . MathWorld .
• Knuth-Bendix Completion Visualizer