氏名: 西村 徹 (289634342)
論文題目: 直交な条件付き項書換え系の合流性
論文概要
条件付き項書換え系は項書換え系の書換え規則に条件を付加し規則の適用
を制限した書換え型の計算モデルである。条件付き項書換え系は計算は非
決定的に進むため、計算結果の一意性を保証する合流性の概念は非常に重
要である。
直交な項書換え系においては合流性を持つが、直交な条件付き項書換え系
においては成立しない。これは、一般には条件部が書換え関係に関して閉
じておらず、計算によってリデックスが保存されないためである。
したがって、直交な条件付き項書換え系については、合流性が成立するク
ラスの発見が研究の対象になっている。これまでに、I型およびIII_n型
条件付き項書換え系は合流性を持つこと、II型条件付き項書換え系は合流
性を持たないことが知られている。しかしながら、直交なII_n型条件付き
項書換え系の合流性は未解決であった。
本論文では、この問題を肯定的に解決する。さらに、II_n型条件付き項
書換え系を一般化したII_S型条件付き項書換え系を提案し、合流性のた
めの十分条件を与える。またIII型条件付き項書換え系の合流性の十分条件
についても述べる。
目次に戻る