組合せ子の非循環性について
スポンサーリンク
概要
- 論文の詳細を見る
Sumllyanは,書換え規則Lxy→x(yy)を持つ組合せ子Lと書換え規則Oxy→y(xy)を持つ組合せ子Oを提案した.本稿では,組合せ子の非循環性に対する十分条件を与える.最初に,Bergstraらの手法を一般化した組合せ子の非循環性に対する十分条件を与える.その十分条件を用いて,組合せ子LとOの非循環性を示す.また,組合せ子Oは,Oのみから成る項上で停止性を持たないことを示す.次に,Waldmannと同様の手法により,組合せ子Oは非基礎ループ性を持つことを示す.最後に,書換え規則Lxy→x(yy)による書換え→の逆関係→^<-1>が停止性を持つことを示し,組合せ子Lの非循環性の簡潔な証明を与える.さらに,組合せ子Lが基礎ループを持つことを示す.
- 社団法人電子情報通信学会の論文
- 2007-12-10
著者
関連論文
- 左線形かつ$K$-開発閉包な項書換えシステムの合流性に関する考察 (代数と言語のアルゴリズムと計算理論)
- 組合せ子 $L$ の非循環性とその応用(代数、形式言語、計算システム理論とその応用)
- 不動点組合せ子の非循環性と関連する性質について (代数系アルゴリズムと言語および計算理論)
- 組合せ子$O$の非基礎ループ性 (証明論と論理・計算の構造)
- 組合せ子の非循環性と非停止性 (代数、言語のアルゴリズムと計算理論)
- 組合せ子の非循環性について
- 左線形かつK-開発閉包な項書換えシステムの合流性(研究速報)
- LA-007 組合せ子Lの非循環性(モデル・アルゴリズム・プログラミング)
- $K$- 開発閉包な左線形項書換えシステムの合流性(計算機科学の理論とその応用)
- An Improved Recursive Decomposition Ordering for Term Rewriting Systems Revisited (Theoretical Computer Science and its Applications)