##  [Knuth–Bendix Completion](/knuth-bendix-completion-1) 

 Definition

An algorithmic procedure taking a set of rewrite rules (or relations) together with a well-founded reduction ordering and attempting to extend the rule set by adding consequences (resolving critical pairs) so as to produce a confluent (and terminating) rewriting system that decides word equality in the presented algebra when successful.

 

 

 

 

 

 





## Principle

Principle

Systematically compute overlaps (critical pairs) between rules, orient the resulting equalities according to a chosen term ordering, and add new rules to resolve divergences; repeat until no unresolved critical pairs remain or the process fails to terminate.

 

 

 

 

 





## Demonstration

Demonstration

Given a finitely presented monoid or group presentation, convert relations into oriented reduction rules with a length- or lexicographic ordering, compute critical pairs from overlaps of left-hand sides, add resolving rules and simplify repeatedly. If the procedure terminates in a confluent system, two words are equal in the presented algebra iff they reduce to the same normal form.

 

 

 

 

## Misapplication

Misapplication

Assuming the algorithm always terminates or always yields confluence; starting with a poor or non-well-founded ordering or ignoring equational axioms (like commutativity) can prevent success or produce incorrect conclusions about the word problem.

 

 

 

 

 





## Consequence

Consequence

When it succeeds, the completion provides a terminating confluent rewrite system and thus an effective normal-form solution to the word problem; it also exposes structural consequences like canonical representatives and decision procedures for equality.

 

 

 

 

## Reversal

Reversal

The inverse viewpoint is to introduce ambiguous overlaps deliberately (dropping rules or weakening orderings) to produce nonconfluent systems, which may be useful for exploring alternative presentations but loses decidability of normal forms.

 

 

 

 

 





## Boundary

Boundary

Applies to term-rewriting systems, monoid or group presentations and equational theories provided a compatible well-founded ordering exists; it is not guaranteed to succeed for arbitrary presentations and must be adapted (or replaced) for theories with built-in commutativity, higher arity equational constraints, or where termination cannot be enforced.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension with Gröbner-basis techniques and completion modulo theories: superficially similar but distinct methods arise in different algebraic settings (polynomial ideals versus term-rewriting for words), and users sometimes conflate termination/confluence guarantees across these frameworks.

 

 

 

 

 





## Synthesis

Synthesis

Knuth–Bendix Completion is an algorithmic attempt to turn a presentation into a confluent, terminating rewrite system by resolving overlaps via critical-pair analysis and oriented reductions; success yields normal forms and a decision procedure for word equality, but termination and confluence are not guaranteed in general.