The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra.
Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
Introduction
For a set E of equations, its deductive closure () is the set of all equations that can be derived by applying equations from E in any order. Formally, E is considered a binary relation, () is its rewrite closure, and () is the equivalence closure of (). For a set R of rewrite rules, its deductive closure ( ∘ ) is the set of all equations that can be confirmed by applying rules from R left-to-right to both sides until they are literally equal. Formally, R is again viewed as a binary relation, () is its rewrite closure, () is its converse, and ( ∘ ) is the relation composition of their reflexive transitive closures ( and ).
For example, if are the group axioms, the derivation chain
demonstrates that a−1⋅(a⋅b) b is a member of E'''s deductive closure. If is a "rewrite rule" version of E, the derivation chains
demonstrate that (a−1⋅a)⋅b ∘ b is a member of Rs deductive closure. However, there is no way to derive a−1⋅(a⋅b) ∘ b similar to above, since a right-to-left application of the rule is not allowed.
The Knuth–Bendix algorithm takes a set E of equations between terms, and a reduction ordering (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system R that has the same deductive closure as E. While proving consequences from E often requires human intuition, proving consequences from R does not. For more details, see Confluence (abstract rewriting)#Motivating examples, which gives an example proof from group theory, performed both using E and using R.
Rules
Given a set E of equations between terms, the following inference rules can be used to transform it into an equivalent convergent term rewrite system (if possible): Here: sect.8.1, p.293 They are based on a user-given reduction ordering (>) on the set of all terms; it is lifted to a well-founded ordering (▻) on the set of rewrite rules by defining if in the encompassment ordering, or and are literally similar and .
Example
The following example run, obtained from the E theorem prover, computes a completion of the (additive) group axioms as in Knuth, Bendix (1970). It starts with the three initial equations for the group (neutral element 0, inverse elements, associativity), using f(X,Y) for X+Y, and i(X) for −X. The 10 starred equations turn out to constitute the resulting convergent rewrite system. "pm" is short for "paramodulation", implementing deduce. Critical pair computation is an instance of paramodulation for equational unit clauses. "rw" is rewriting, implementing compose, collapse, and simplify. Orienting of equations is done implicitly and not recorded.
See also Word problem (mathematics) for another presentation of this example.
String rewriting systems in group theory
An important case in computational group theory are string rewriting systems which can be used to give canonical labels to elements or cosets of a finitely presented group as products of the generators. This special case is the focus of this section.
Motivation in group theory
The critical pair lemma states that a term rewriting system is locally confluent (or weakly confluent) if and only if all its critical pairs are convergent. Furthermore, we have Newman's lemma which states that if an (abstract) rewriting system is strongly normalizing and weakly confluent, then the rewriting system is confluent. So, if we can add rules to the term rewriting system in order to force all critical pairs to be convergent while maintaining the strong normalizing property, then this will force the resultant rewriting system to be confluent.