@article{oai:nagoya.repo.nii.ac.jp:00007651,
 author = {村田, 龍彦 and MURATA, Tatsuhiko and 酒井, 正彦 and SAKAI, Masahiko and 西田, 直樹 and NISHIDA, Naoki and 草刈, 圭一朗 and KUSAKARI, Keiichirou and 坂部, 俊樹 and SAKABE, Toshiki},
 journal = {京都大学数理解析研究所講究録},
 month = {Apr},
 note = {項到達可能性問題とは、与えられた2つの項と項書換え系(TRS) に対し、片方の項(初期項)からもう片方の項(標的項)へ到達できるかという問題である。この問題は一般には決定不能だが、決定可能なTRSのクラスも存在する。F.Jacquemardは、TRSが右線形逆成長の場合において、初期項から到達可能な全ての項を受理する木オートマトン(TA)を構成し、標的項がTAに受理されるかで到達可能性を判定する方法を提案した。さらに、TRSが右線形の場合においては初期項から到達可能な項を全て受理するTAを構築して到達不可能性を判定する手法を示した。本稿では、Jacquemard の手法を元にして、任意のTRSにおいて初期項から到達可能な項を全て受理するTA を、TA生成ツールTimbukが必ず出力するような、Timbukの入力生成アルゴリズムを提案する。また、提案手法とJacquemardの手法を比較し、TRSが右線形の場合においては得られるTAの能力が等価であることを示す、さらに、提案したアルゴリズムを改良し近似精度の向上を図る。},
 pages = {106--112},
 title = {項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係},
 volume = {1426},
 year = {2005}
}