KnuthBendixVervollständigung

The Knuth-Bendix completion algorithm is a procedure in computational group theory and term rewriting systems. Its primary goal is to transform a given set of rewrite rules into an equivalent, terminating, and confluent set of rules, also known as a complete set. This means that for any term, there is a unique irreducible form obtainable by applying the rules.

The algorithm was developed by Donald Knuth and Peter Bendix in the early 1970s. It operates by systematically eliminating ambiguities and non-termination issues that may arise from the initial set of rules. When two distinct rule applications lead to different results for the same term, the algorithm introduces new rules to resolve this conflict. This process continues iteratively, adding new rules and simplifying existing ones until the set becomes complete.

A key component of the Knuth-Bendix algorithm is the concept of critical pairs. A critical pair arises when two rules overlap or when one rule's left-hand side is a subterm of another rule's left-hand side. By processing these critical pairs and ensuring they can be reduced to a common form, the algorithm aims to achieve confluence.

If the algorithm terminates, it produces a complete set of rewrite rules for the original presentation. This complete set is highly desirable as it guarantees unique normal forms for all terms, making computations within the system decidable and efficient. However, the Knuth-Bendix algorithm is not guaranteed to terminate for all input sets of rules. In some cases, it may continue indefinitely or produce an infinite number of rules. Despite this limitation, it remains a fundamental tool for analyzing and manipulating algebraic structures.