クヌースベンディックスの合流条件とは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキング

クヌース・ベンディックスの合流条件

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/14 18:33 UTC 版)

「クヌース・ベンディックス完備化アルゴリズム」の記事における「クヌース・ベンディックスの合流条件」の解説

危険対の要素をそれぞれ簡約化して正規形を求めたとき、両者が一致する場合を"収束する"、一致しない場合を"発散する"という。危険対について、以下の定理が成立する。クヌース・ベンディックスの合流条件停止性を満たす項書き換えシステム R が合流性（つまり完備性）をもつための必要十分条件は R の全ての危険対が収束することである。書き換え規則が有限であれば危険対も有限であり、項書き換えシステムが停止性をみたす場合は危険対の各要素の正規形も有限の簡約ステップで求めることができる。つまり、停止性を満たす項書き換えシステムの合流性は以下の有限のステップで分かる。システムの危険対を全て求める。危険対 ( p , q ) {\displaystyle \left(p,q\right)} について正規形 ( p ↓ , q ↓ ) {\displaystyle \left(p\downarrow ,q\downarrow \right)} を求める。 p ↓= q ↓ {\displaystyle p\downarrow =q\downarrow } であるかどうかを調べる。全ての ( p , q ) {\displaystyle \left(p,q\right)} について p ↓= q ↓ {\displaystyle p\downarrow =q\downarrow } であれば、システムは合流性を持つ。

※この「クヌース・ベンディックスの合流条件」の解説は、「クヌース・ベンディックス完備化アルゴリズム」の解説の一部です。
「クヌース・ベンディックスの合流条件」を含む「クヌース・ベンディックス完備化アルゴリズム」の記事については、「クヌース・ベンディックス完備化アルゴリズム」の概要を参照ください。

ウィキペディア小見出し辞書の「クヌースベンディックスの合流条件」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。


	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのクヌース・ベンディックス完備化アルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。