クヌース・ベンディックス完備化アルゴリズム

クヌース・ベンディックス完備化アルゴリズム（）、あるいはクヌース・ベンディックス完備化手続きは、等式の有限集合をそれと等価な完備性のある項書き換えシステムに変換するアルゴリズムである。このアルゴリズムは普遍代数（）での"語の問題"（）（）を解くための手法としてクヌースとベンディックスから提案された。
アルゴリズムは必ず成功するとは限らないが、成功した場合は停止性と合流性のある項書き換えシステムを生成することができる。そのベースとなる考え方は多くの分野で応用することができる。
背景.
一般に、項書き換えシステムは項の書き換え（"簡約"、）が必ず停止するとは限らず、また書き換えの際に複数の書き換え規則を適用できる場合は最終的な結果が一意になるとは限らない。
無限の簡約の列が存在しないことを"停止性"、複数の書き換え規則を適用可能な場合にその後の簡約の流れが合流することを"合流性"と言う。停止性と合流性を両方もっていれば、システムは完備（）と言う。
完備性があるシステムは、最終的な結果が必ず求まり、その結果は簡約の順序によらず一意になる。
以下では、"a" から "b" への簡約を formula_1 、"a" を簡約していってこれ以上簡約できなくなった最も単純な形（"正規形"、）を formula_2 と表記する。
危険対.
ある要素に対し2つの書き換え規則を適用可能な場合がありうる。2つの規則の条件に重なりがあるとき、それらの規則で簡約した異なる結果のペアを危険対（）と呼ぶ。危険対が存在する場合、どの書き換え規則を適用するかにより簡約の結果が変わる可能性がある。
例えば、以下の項書き換え規則を考える。
項 formula_5 を考える。 ρ1 を適用すると項 formula_6 が得られ、ρ2 を適用すると項 formula_7 が得られる。このときの危険対は、formula_8 である。
クヌース・ベンディックスの合流条件.
危険対の要素をそれぞれ簡約化して正規形を求めたとき、両者が一致する場合を"収束する"、一致しない場合を"発散する"という。危険対について、以下の定理が成立する。
 クヌース・ベンディックスの合流条件
 停止性を満たす項書き換えシステム "R" が合流性（つまり完備性）をもつための
 必要十分条件は "R" の全ての危険対が収束することである。
書き換え規則が有限であれば危険対も有限であり、項書き換えシステムが停止性をみたす場合は危険対の各要素の正規形も有限の簡約ステップで求めることができる。つまり、停止性を満たす項書き換えシステムの合流性は以下の有限のステップで分かる。
アルゴリズム.
クヌース・ベンディックス完備化アルゴリズムは等式の有限集合をそれと等価な完備性のある項書き換えシステムに変換する。等式の有限集合とは、例えば以下の formula_14 ようなものである。これは群の公理である単位元の存在、逆元の存在、結合法則を表す。
これらより formula_16, formula_17, formula_18 のような項書き換えの規則 formula_19 を作成する。特定の等式 formula_20 が成立するかどうかを調べるためには、"u", "v" それぞれを規則で正規形に書き換え、一致するかを調べればよい。
クヌース・ベンディックス完備化アルゴリズムのベースとなる考え方は以下のように表現できる。
単純化したクヌース・ベンディックス完備化アルゴリズムは以下の通りである。"R" は書き換え規則の有限集合、"E" は等式の有限集合、＞ は停止性を保証する項順序を表す。また、危険対 formula_9 は "E" 中の等式 formula_22 として表現される。"E" の初期値は対象となる等式、"R" の初期値は空である。
 "E" が空になるまで繰り返す。
 "E" から等式 formula_23 を1つ選択し、取り除く。
 正規形 formula_24、 formula_25 を求める
 もし formula_26 ならば、
 もし formula_27 ならば
 formula_28 を "R" に追加する。
 もし formula_29 ならば
 formula_30 を "R" に追加する。
 そうでなければ完備化失敗として終了
 新しい "R" から生成される全ての危険対を等式にして "E" に追加する。
このアルゴリズムの結果は、(1)停止して結果が "R" に求まる、(2)停止しない、(3)完備化失敗として終了、の3通りがある。
例えば危険対を合流させる規則の追加により新たな危険対が発生し続ける場合など、規則が有限にならない場合、このアルゴリズムは停止しない。つまり、正確には半アルゴリズム（）である。また、等式の左右の項が順序化できない場合、書き換え規則を作成できず完備化は失敗する。
しかし、クヌース・ベンディックス完備化アルゴリズムが停止する場合、生成された項書き換えシステムが完備性を持っていることは証明されている。
なお、上記の手続きのままでは、規則の追加に伴って冗長な規則が増えていき、発散する危険対も多くなる。実際には、規則を追加していく際に以下のルールを用いて等式や書き換え規則の正規化を行い、冗長なものを取り除く。
具体例.
具体例として群の公理を完備化する。群の公理は以下の通り。
完備化アルゴリズムは以下のように行う。
このような作業を数十回繰り返し、冗長な物を取り除くと、最終的にこの式が残る。
拡張.
完備化アルゴリズムでは、適当な項順序による向き付けを決めないと書き換え規則が作れない。そのため formula_34 のように左右の項の向き付けができない等式が現れると完備化が失敗する。失敗無し完備化（、あるいは）は、このような等式を両方向に使える可能性のある書き換え規則と見なし、適当な代入で停止性が保証される向き付けが得られた場合のみ、この等式を向き付けられた書き換え規則として簡約を行うやり方である。例えば、 formula_35 の場合、formula_36 のように引数の辞書式順序を用い、等式 formula_37 を formula_38 のように向き付けを行い簡約を行う。
他分野との関連.
合流性を保証するための危険対や停止性を保証する項順序の考え方は、一般の簡約系でも有効であり、他分野でも同様の手続きが知られている。
グレブナー基底.
グレブナー基底は、多変数多項式の簡約化を一意に行える多項式の集合であり、グレブナー基底を求めるブッフベルガーアルゴリズムは数式処理の分野での連立代数方程式の解法や、可換環論、代数幾何、微分方程式論、整数計画問題などに出てくる様々な数学的対象物を構成するための基礎となっている。
クヌース・ベンディックス完備化アルゴリズムでの危険対はブッフベルガーアルゴリズムでの"S-多項式"、項順序は"単項式順序"に対応する。