Knuth–Bendix completion algorithm

<p>The Knuth–Bendix completion algorithm (named after <a href="/facts/Donald_E._Knuth/GozNzDM6">Donald Knuth</a> and Peter Bendix) is a <a href="/facts/Semidecidable/17SHPMo0">semi-decision</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for transforming a set of <a href="/facts/Equation/pxFzLAVR">equations</a> (over <a href="/facts/Term_(logic)/M0nXp7dH">terms</a>) into a <a href="/facts/Confluence_(term_rewriting)/kzGnhPVV">confluent</a> <a href="/facts/Term_rewriting_system/9PHlnnnJ">term rewriting system</a>.  When the algorithm succeeds, it effectively solves the <a href="/facts/Word_problem_(mathematics)/UJmKtmNF">word problem</a> for the specified <a href="/facts/Algebra/nMdqczjo">algebra</a>.
</p><p><a href="/facts/Buchberger%2527s_algorithm/7z5q4K33">Buchberger's algorithm</a> for computing <a href="/facts/Gr%25C3%25B6bner_basis/efMrjM7w">Gröbner bases</a> is a very similar algorithm. Although developed independently, it may also be seen as the instantiation of Knuth–Bendix algorithm in the theory of <a href="/facts/Polynomial_ring/ua3vk8Ih">polynomial rings</a>.
</p>

Knuth–Bendix completion algorithm open-in-new

Knuth–Bendix completion algorithm