局所合流性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/17 13:50 UTC 版)
要素 a ∈ A が 局所合流性（Local confluence）を持つとは、 c ← a → b {\displaystyle c\,\leftarrow \,a\,\rightarrow \,b} となる任意の b, c ∈ A について c → ∗ d ← ∗ b {\displaystyle c\,{\overset {*}{{}\to {}}}d\,{\overset {*}{{}\leftarrow {}}}b} となるような d が存在することである。これを図で表現したものが図２である。 局所合流性は、弱合流性（Weak confluence）あるいは弱チャーチ・ロッサー性（Weak Church-Rosser property）と呼ばれることもある。 局所合流性は合流性より弱い性質で、全ての要素が局所合流性を持つ場合でも、例えば書き換え規則にループが含まれる場合など、システム全体の合流性が成立するとは限らない。 ただし、システムが停止性と局所合流性とを持つ場合、システムは合流性を持つ（ニューマンの補助定理、Newman's lemma）。
※この「局所合流性」の解説は、「合流性」の解説の一部です。
「局所合流性」を含む「合流性」の記事については、「合流性」の概要を参照ください。
ウィキペディア小見出し辞書の「局所合流性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 局所合流性のページへのリンク
