Knuth–Bendix completion algorithm
E94985
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
automated theorem proving technique ⓘ term rewriting procedure ⓘ |
| appliesTo |
algebraic structures
ⓘ
equational theories ⓘ word problems in groups ⓘ word problems in monoids ⓘ word problems in semigroups ⓘ |
| assumes |
finite signature of function symbols
ⓘ
well-founded reduction ordering on terms ⓘ |
| basedOn |
equational reasoning
ⓘ
term rewriting systems ⓘ |
| enables | decision of the word problem for the completed theory ⓘ |
| field |
automated theorem proving
ⓘ
equational logic ⓘ term rewriting ⓘ universal algebra ⓘ |
| goal |
confluence
ⓘ
termination of the rewrite system ⓘ |
| hasProperty |
can produce a confluent and terminating rewrite system when it succeeds
ⓘ
may not terminate in general ⓘ semi-decision procedure ⓘ |
| input | finite set of equations ⓘ |
| inventedBy |
Donald E. Knuth
NERFINISHED
ⓘ
Peter B. Bendix ⓘ |
| output |
confluent term rewriting system when completion succeeds
ⓘ
set of oriented rewrite rules ⓘ |
| publishedIn | Journal of the ACM ⓘ |
| purpose |
decide word problems in algebraic structures
ⓘ
transform a set of equations into a confluent rewriting system ⓘ |
| relatedTo |
Buchberger algorithm
ⓘ
Church–Rosser property ⓘ Gröbner basis NERFINISHED ⓘ Knuth–Bendix order ⓘ confluent rewriting system ⓘ critical pair lemma ⓘ termination orderings ⓘ |
| step |
add new equations from unresolved critical pairs
ⓘ
compute critical pairs of rewrite rules ⓘ orient equations into rewrite rules using a reduction ordering ⓘ simplify equations and rules using existing rules ⓘ |
| usedIn |
automated theorem provers
ⓘ
completion-based theorem proving systems ⓘ equational theorem proving ⓘ |
| uses |
completion of rewrite rules
ⓘ
critical pair computation ⓘ reduction orderings ⓘ |
| yearProposed | 1970 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.