# A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

I’m looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative examples preferably with drawings, and reasonably self-contained. It can be inside a book, an article, lecture notes, website, whatever. Possible languages: English, French, German.

The two obvious references are:

Note that neither refers to completion as "Knuth-Bendix" completion in the index, since the science of completion has come a long way since it was first introduced. This survey by Dershowitz and Jouannaud might be a bit more historical.

It might help to understand what your needs are, since the field is vast, and somewhat technical. Are you trying to use a completion algorithm? Implement it? Adapt it to a specific setting?

Answered by cody on December 11, 2020

There is a rather technically-detailed description to be found in any of the following:

D.F. Holt, D.B.A. Epstein, and S. Rees. The use of knuth-bendix methods to solve the word problem in automatic groups. J. Symbolic Computation, 12:397--414, 1991.

Charles C. Sims. Computation with Finitely Presented Groups. Cambridge, 1994.

Derek F. Holt. The warwick automatic groups software. In Proceedings of DIMACS Conference on Computational Group Theory, Rutgers, March 1994

Answered by NietzscheanAI on December 11, 2020

## Related Questions

### What does it mean by the statement: “a problem is hard to approximate “?

0  Asked on February 11, 2021 by inuyasha-yagami

### Reference request: DFA linear-time minimization

0  Asked on January 23, 2021 by shyperson

### Proof of $LP$ is in $coNP$ without showing it is in $P$?

1  Asked on January 19, 2021

### Computing chromatic number of subcubic graphs

0  Asked on January 13, 2021 by cyriac-antony

### What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

1  Asked on January 7, 2021

### Büchi automata with acceptance strategy

2  Asked on November 26, 2020

### Reference request: Depth- (or Breadth-) first search with hints?

1  Asked on November 16, 2020 by wei-wang