Home > Knuth-Bendix completion algorithm

1 Description of the algorithm

Suppose we are given a presentation , where is a set of generators and is a set of relations giving the rewriting system. Suppose further that we have a well-ordering words generated by . For each relation in , suppose . Thus we begin with the set of reductions .

First, if any relation can be reduced, replace and with the reductions.

Next, we add more reductions (that is, rewriting rules) to eliminate possible exceptions of confluence. Suppose that and , where , overlap. That is, either the prefix of equals the suffix of , or vice versa. In the former case, we can write ; in the latter case, .

Reduce the word using first, then using first. Call the results , respectively. If , then we have an instance where confluence could fail. Hence, add the reduction to .

After adding a rule to , remove any rules in that might have reducible left sides.

Repeat the procedure until all overlapping left sides have been checked.

2 Example

Consider the presentation . We use the lexicographic ordering. In fact, this is an infinite group. Nevertheless, the Knuth-Bendix algorithm is able to solve the word problem.

Our beginning three reductions are therefore (1) , (2) , and (3) .

First, we see an overlap of in (1) and (3). Consider the word . Reducing using (1), we get . Reducing using (3), we get . Hence, we get , giving the reduction rule (4) .

Similarly, using the overlap of in (2) and (3), we get the reduction (5) .

Both of these rules obsolete (3), so we remove it.

Next, consider the overlap of of (1) and (5). Considering we get the rule , so we get the rule (6) . This obsoletes rule (4) and (5), so we remove them. Considering , we get , so we get the rule (7) .

Now, we are left with the rewriting system

• (1)
• (2)
• (6)
• (7)

Checking the overlaps of these rules, we find no potential failures of confluence. Therefore, we have a confluent rewriting system, and the algorithm terminates successfully.