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

クリティカルペア補題によれば、項書き換えシステムは、そのすべてのクリティカルペアが収束する場合に限り、局所的に合流性（または弱合流性）を持つ。さらに、ニューマンの補題によれば、（抽象的な）書き換えシステムが強正規化かつ弱合流性であれば、その書き換えシステムは合流性を持つ。したがって、強正規化特性を維持しながらすべてのクリティカルペアが収束するように項書き換えシステムにルールを追加できれば、結果として得られる書き換えシステムは合流性を持つことになる。

有限表示モノイドを考える${\displaystyle M=\langle X\mid R\rangle }$ここで、X は有限個の生成元集合であり、R は X 上の定義関係の集合である。X ^*を X 内のすべての単語の集合 (すなわち、X によって生成される自由モノイド) とする。関係 R は X* 上に同値関係を生成するので、M の要素を R の下での X ^{*の同値類と考えることができる。各クラス}{w ₁ , w ₂ , ... }に対して、標準代表w _kを選択することが望ましい。この代表は、クラス内の各単語w _kの標準形または正規形と呼ばれる。各w _kの正規形w _iを決定する計算可能な方法があれば、単語の問題は容易に解決できる。合流書き換えシステムでは、まさにこれを実現できる。

標準形式の選択は理論的には任意の方法で行うことができますが、この方法は一般的に計算できません。（言語上の同値関係は無限個の無限クラスを生成する可能性があることを考えてみてください。）言語が整列している場合、順序 < は最小代表を定義するための一貫した方法を提供しますが、これらの代表を計算することは依然として不可能な場合があります。特に、書き換えシステムを使用して最小代表を計算する場合、順序 < は次の性質も持つ必要があります。

A < B → XAY < XBY は、すべての単語 A、B、X、Y に適用されます。

この性質は並進不変性と呼ばれます。並進不変性と整列性の両方を満たす順序は、縮約順序と呼ばれます。

モノイドの表示から、関係 R によって与えられる書き換えシステムを定義することができます。A x B が R に含まれる場合、A  <  B となり、その場合は B  →  A が書き換えシステムの規則となります。そうでない場合は A  >  B となり、A  →  B となります。< は還元順序であるため、与えられた単語 W は W > W_1 > ... > W_n に還元できます。ここで W_n は書き換えシステムの下で既約です。ただし、各 W _i  →  W _{i+1に適用される規則によっては、W の 2 つの異なる既約還元 W n}  ≠  W' _mが得られる可能性があります。しかし、関係によって与えられる書き換えシステムを Knuth–Bendix アルゴリズムによって合流書き換えシステムに変換すると、すべての還元で同じ既約単語、つまりその単語の正規形が生成されることが保証されます。

プレゼンテーションが与えられたとしましょう${\displaystyle \langle X\mid R\rangle }$、 どこ${\displaystyle X}$はジェネレーターのセットであり、${\displaystyle R}$これは書き換えシステムを与える関係の集合である。さらに、還元順序があると仮定する。${\displaystyle <}$生成された単語の中で${\displaystyle X}$（例：ショートレックス順序）。各関係について${\displaystyle P_{i}=Q_{i}}$で${\displaystyle R}$、 仮定する${\displaystyle Q_{i}<P_{i}}$ということで、まずは還元の集合から始めます。${\displaystyle P_{i}\rightarrow Q_{i}}$。

まず、何らかの関係がある場合${\displaystyle P_{i}=Q_{i}}$削減、交換可能${\displaystyle P_{i}}$そして${\displaystyle Q_{i}}$削減により。

次に、合流の例外の可能性を排除するために、さらに削減（つまり、ルールの書き換え）を追加します。${\displaystyle P_{i}}$そして${\displaystyle P_{j}}$重複。

1. ケース 1: 接頭辞${\displaystyle P_{i}}$の接尾辞に等しい${\displaystyle P_{j}}$、またはその逆。前者の場合、次のように書くことができる。${\displaystyle P_{i}=BC}$そして${\displaystyle P_{j}=AB}$後者の場合、${\displaystyle P_{i}=AB}$そして${\displaystyle P_{j}=BC}$。
2. ケース2：${\displaystyle P_{i}}$完全に囲まれている ${\displaystyle P_{j}}$、またはその逆。前者の場合、次のように書くことができる。${\displaystyle P_{i}=B}$そして${\displaystyle P_{j}=ABC}$後者の場合、${\displaystyle P_{i}=ABC}$そして${\displaystyle P_{j}=B}$。

単語を減らす${\displaystyle ABC}$使用${\displaystyle P_{i}}$まず、次に${\displaystyle P_{j}}$まず、結果を呼び出します。${\displaystyle r_{1},r_{2}}$それぞれ。${\displaystyle r_{1}\neq r_{2}}$すると、合流が失敗する可能性があるケースが発生します。したがって、削減を追加します。${\displaystyle \max r_{1},r_{2}\rightarrow \min r_{1},r_{2}}$に${\displaystyle R}$。

ルールを追加した後${\displaystyle R}$ルールを削除${\displaystyle R}$（そのような規則が他の規則と重要なペアを持っているかどうかを確認した後で）左辺が簡約可能である可能性がある。

重なり合う左側の辺がすべてチェックされるまで、この手順を繰り返してください。