2024-03-29T14:20:46Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00007651
2023-01-16T03:53:06Z
312:313:314
項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係
村田, 龍彦
21634
MURATA, Tatsuhiko
21635
酒井, 正彦
21636
SAKAI, Masahiko
21637
西田, 直樹
21638
NISHIDA, Naoki
21639
草刈, 圭一朗
21640
KUSAKARI, Keiichirou
21641
坂部, 俊樹
21642
SAKABE, Toshiki
21643
木オートマトン
近似
項到
2005-04
項到達可能性問題とは、与えられた2つの項と項書換え系(TRS) に対し、片方の項(初期項)からもう片方の項(標的項)へ到達できるかという問題である。この問題は一般には決定不能だが、決定可能なTRSのクラスも存在する。F.Jacquemardは、TRSが右線形逆成長の場合において、初期項から到達可能な全ての項を受理する木オートマトン(TA)を構成し、標的項がTAに受理されるかで到達可能性を判定する方法を提案した。さらに、TRSが右線形の場合においては初期項から到達可能な項を全て受理するTAを構築して到達不可能性を判定する手法を示した。本稿では、Jacquemard の手法を元にして、任意のTRSにおいて初期項から到達可能な項を全て受理するTA を、TA生成ツールTimbukが必ず出力するような、Timbukの入力生成アルゴリズムを提案する。また、提案手法とJacquemardの手法を比較し、TRSが右線形の場合においては得られるTAの能力が等価であることを示す、さらに、提案したアルゴリズムを改良し近似精度の向上を図る。
departmental bulletin paper
京都大学数理解析研究所
2005-04
京都大学数理解析研究所講究録
1426
106
112
http://hdl.handle.net/2237/9355
1880-2818
jpn
http://hdl.handle.net/2433/47265