Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
- Comment
- enThe Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
- Has abstract
- enThe Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra. Buchberger's algorithm for computing Gröbner bases is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of polynomial rings.
- Hypernym
- Algorithm
- Is primary topic of
- Knuth–Bendix completion algorithm
- Label
- enKnuth–Bendix completion algorithm
- Link from a Wikipage to an external page
- books.google.com/books%3Fhl=en&lr=&id=UytXH6rLUDwC&oi=fnd&pg=PA256&dq=%22Logged+rewriting+and+identities+among+relators%22&ots=KYif_N4FmE&sig=We5TmSZlfdt1o8Xyxg1AYF1A4Vk%23v=onepage&q&f=false
- cl-informatik.uibk.ac.at/software/kbcv/
- www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf
- hal.inria.fr/inria-00076536/file/RR-0025.pdf%7C
- Link from a Wikipage to another Wikipage
- Algebra
- Algorithm
- Binary relation
- Buchberger's algorithm
- Category:Combinatorics on words
- Category:Computational group theory
- Category:Donald Knuth
- Category:Rewriting systems
- Computational group theory
- Confluence (abstract rewriting)
- Confluence (term rewriting)
- Convergent term rewrite system
- Converse relation
- Coset
- Critical pair (logic)
- Critical pair lemma
- Donald E. Knuth
- Encompassment ordering
- Equation
- Equivalence closure
- E theorem prover
- Finitely presented group
- Finitely presented monoid
- Free Abelian group
- Generating set of a group
- Gröbner basis
- Ground confluent
- Group (mathematics)
- Logged rewriting
- Newman's lemma
- Normal form (term rewriting)
- Polynomial ring
- Presentation of a group
- Reduction ordering
- Reflexive transitive closure
- Relation (mathematics)
- Relation composition
- Resolution (logic)
- Rewrite closure
- Semi-algorithm
- Semidecidable
- Shortlex order
- Term (logic)
- Term rewriting system
- Variant (logic)
- Well-ordered
- Word problem (mathematics)
- SameAs
- 2e2w7
- Complétion de Knuth-Bendix
- m.02wqch
- Q2835803
- クヌース・ベンディックス完備化アルゴリズム
- Subject
- Category:Combinatorics on words
- Category:Computational group theory
- Category:Donald Knuth
- Category:Rewriting systems
- Title
- enKnuth–Bendix Completion Algorithm
- Urlname
- enKnuth-BendixCompletionAlgorithm
- WasDerivedFrom
- Knuth–Bendix completion algorithm?oldid=1117289232&ns=0
- WikiPageLength
- 21397
- Wikipage page ID
- 614147
- Wikipage revision ID
- 1117289232
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal
- Template:Donald Knuth navbox
- Template:EquationNote
- Template:EquationRef
- Template:Math
- Template:MathWorld
- Template:Mset
- Template:Mvar
- Template:NumBlk
- Template:Overunderset
- Template:Reflist
- Template:Underset