|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 完 ： [かん] 【名詞】 1. The End (book, film, etc.) 2. Finis ・ 完備 ： [かんび] 1. (n,vs) perfection 2. completion ・ 化 ： [か] (suf) action of making something
クヌース・ベンディックス完備化アルゴリズム（）、あるいはクヌース・ベンディックス完備化手続きは、等式の有限集合をそれと等価な完備性のある項書き換えシステムに変換するアルゴリズムである。このアルゴリズムは普遍代数（en）での''語の問題''（）（en）を解くための手法としてクヌースとベンディックスから提案された〔 D. E. Knuth and P. B. Bendix. ''Simple word problems in universal algebras''. in ''Computational Problems in Abstract Algebra'' ''(Proc. Conf., Oxford, 1967)''. J. Leech (ed.), Pergamon Press. pp.263–297. 1970.〕。 アルゴリズムは必ず成功するとは限らないが、成功した場合は停止性と合流性のある項書き換えシステムを生成することができる。そのベースとなる考え方は多くの分野で応用することができる。 == 背景 == 一般に、項書き換えシステムは項の書き換え（''簡約''、）が必ず停止するとは限らず、また書き換えの際に複数の書き換え規則を適用できる場合は最終的な結果が一意になるとは限らない。 無限の簡約の列が存在しないことを''停止性''、複数の書き換え規則を適用可能な場合にその後の簡約の流れが合流することを''合流性''と言う。停止性と合流性を両方もっていれば、システムは完備（）と言う。 完備性があるシステムは、最終的な結果が必ず求まり、その結果は簡約の順序によらず一意になる。 以下では、''a'' から ''b'' への簡約を 、''a'' を簡約していってこれ以上簡約できなくなった最も単純な形（''正規形''、）を と表記する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「クヌース・ベンディックス完備化アルゴリズム」の詳細全文を読む スポンサード リンク
|