危険対
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/14 18:33 UTC 版)
「クヌース・ベンディックス完備化アルゴリズム」の記事における「危険対」の解説
ある要素に対し2つの書き換え規則を適用可能な場合がありうる。2つの規則の条件に重なりがあるとき、それらの規則で簡約した異なる結果のペアを危険対（英: critical pair）と呼ぶ。危険対が存在する場合、どの書き換え規則を適用するかにより簡約の結果が変わる可能性がある。 例えば、以下の項書き換え規則を考える。 ρ 1 : f ( g ( x , y ) , z ) → g ( x , z ) {\displaystyle \rho _{1}\ :\ f(g(x,y),z)\rightarrow g(x,z)} ρ 2 : g ( x , y ) → x {\displaystyle \rho _{2}\ :\ g(x,y)\rightarrow x} 項 f ( g ( x , x ) , x ) {\displaystyle f\left(g(x,x),x\right)} を考える。 ρ1 を適用すると項 g ( x , x ) {\displaystyle g\left(x,x\right)} が得られ、ρ2 を適用すると項 f ( x , x ) {\displaystyle f\left(x,x\right)} が得られる。このときの危険対は、 ( g ( x , x ) , f ( x , x ) ) {\displaystyle \left(g(x,x),f(x,x)\right)} である。
※この「危険対」の解説は、「クヌース・ベンディックス完備化アルゴリズム」の解説の一部です。
「危険対」を含む「クヌース・ベンディックス完備化アルゴリズム」の記事については、「クヌース・ベンディックス完備化アルゴリズム」の概要を参照ください。
- 危険対のページへのリンク
