Ein algorithmisches Verfahren, das eine Menge von Umschreibungsregeln (oder Relationen) und eine wohlfundierte Reduktionsordnung annimmt und versucht, die Regelmenge durch Hinzufügen von Konsequenzen (Auflösen kritischer Paare) so zu erweitern, dass ein konfluentes (und terminierendes) Umschreibungssystem entsteht, das im Erfolgsfall das Wortproblem in der präsentierten Algebra löst.

Prinzip

Systematisch Überlappungen (kritische Paare) zwischen Regeln berechnen, die resultierenden Gleichheiten gemäß einer gewählten Termordnung orientieren und neue Regeln hinzufügen, um Divergenzen zu beheben; wiederholen, bis keine ungelösten kritischen Paare mehr bestehen oder der Prozess nicht terminiert.

Demonstration

Für eine endlich präsentierte Monoid- oder Gruppenpräsentation wandelt man Relationen in orientierte Reduktionsregeln mit einer Längen- oder lexikografischen Ordnung um, berechnet kritische Paare aus Überlappungen der linken Seiten, fügt auflösende Regeln hinzu und vereinfacht iterativ. Terminiert das Verfahren mit einem konfluenten System, so sind zwei Wörter in der präsentierten Algebra genau dann gleich, wenn sie zur gleichen Normalform reduziert werden.

Fehlanwendung

Anzunehmen, der Algorithmus terminiert stets oder liefere immer Konfluenz; die Wahl einer ungeeigneten oder nicht wohlfundierten Ordnung oder das Ignorieren äquationaler Axiome (z. B. Kommutativität) kann den Erfolg verhindern oder zu falschen Schlüssen über das Wortproblem führen.

Konsequenz

Im Erfolgsfall liefert die Vervollständigung ein terminierendes konfluentes Umschreibungssystem und somit eine effektive Normalformenlösung des Wortproblems; sie offenbart zudem strukturelle Konsequenzen wie kanonische Repräsentanten und Entscheidungsverfahren für Gleichheit.

Umkehrung

Die Umkehr besteht darin, Überlappungen bewusst einzuführen (Regeln fallen zu lassen oder Ordnungen zu schwächen), um nichtkonfluente Systeme zu erzeugen; das kann beim Untersuchen alternativer Präsentationen nützlich sein, verliert aber die Entscheidbarkeit von Normalformen.

Abgrenzung

Gilt für Term-Umschreibungssysteme, Monoid- oder Gruppenpräsentationen und äquationale Theorien, sofern eine kompatible wohlfundierte Ordnung existiert; ein Erfolg ist für beliebige Präsentationen nicht garantiert, und das Verfahren muss für Theorien mit eingebauter Kommutativität, höher-ordnigen äquationalen Zwängen oder wenn Terminierung nicht erzwingbar ist, angepasst werden.

Semantische Spannung

Spannung zu Gröbner-Basis-Verfahren und Kompletion modulo Theorien: zwar oberflächlich verwandt, aber in unterschiedlichen algebraischen Kontexten unterschiedliche Methoden; Nutzer verwechseln gelegentlich die Terminierungs-/Konfluenzgarantien zwischen diesen Frameworks.

Synthese

Die Knuth–Bendix-Vervollständigung ist der algorithmische Versuch, eine Präsentation durch Analyse kritischer Paare und orientierte Reduktionen in ein konfluentes, terminierendes Umschreibungssystem zu überführen; Erfolg liefert Normalformen und ein Entscheidungsverfahren für Wortgleichheit, doch Terminierung und Konfluenz sind allgemein nicht garantiert.