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