WEKO3
アイテム
項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係
http://hdl.handle.net/2237/9355
http://hdl.handle.net/2237/9355dc46f893-572e-4b55-92b5-fed5a6b94098
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2008-01-22 | |||||
タイトル | ||||||
タイトル | 項到達可能性の判定における成長TRSに対する手法と正規化規則による手法の関係 | |||||
言語 | ja | |||||
著者 |
村田, 龍彦
× 村田, 龍彦× MURATA, Tatsuhiko× 酒井, 正彦× SAKAI, Masahiko× 西田, 直樹× NISHIDA, Naoki× 草刈, 圭一朗× KUSAKARI, Keiichirou× 坂部, 俊樹× SAKABE, Toshiki |
|||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 木オートマトン | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 近似 | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | 項到 | |||||
抄録 | ||||||
内容記述 | 項到達可能性問題とは、与えられた2つの項と項書換え系(TRS) に対し、片方の項(初期項)からもう片方の項(標的項)へ到達できるかという問題である。この問題は一般には決定不能だが、決定可能なTRSのクラスも存在する。F.Jacquemardは、TRSが右線形逆成長の場合において、初期項から到達可能な全ての項を受理する木オートマトン(TA)を構成し、標的項がTAに受理されるかで到達可能性を判定する方法を提案した。さらに、TRSが右線形の場合においては初期項から到達可能な項を全て受理するTAを構築して到達不可能性を判定する手法を示した。本稿では、Jacquemard の手法を元にして、任意のTRSにおいて初期項から到達可能な項を全て受理するTA を、TA生成ツールTimbukが必ず出力するような、Timbukの入力生成アルゴリズムを提案する。また、提案手法とJacquemardの手法を比較し、TRSが右線形の場合においては得られるTAの能力が等価であることを示す、さらに、提案したアルゴリズムを改良し近似精度の向上を図る。 | |||||
言語 | ja | |||||
内容記述タイプ | Abstract | |||||
出版者 | ||||||
言語 | ja | |||||
出版者 | 京都大学数理解析研究所 | |||||
言語 | ||||||
言語 | jpn | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | departmental bulletin paper | |||||
出版タイプ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
関連情報 | ||||||
関連タイプ | isVersionOf | |||||
識別子タイプ | URI | |||||
関連識別子 | http://hdl.handle.net/2433/47265 | |||||
ISSN(print) | ||||||
収録物識別子タイプ | PISSN | |||||
収録物識別子 | 1880-2818 | |||||
書誌情報 |
ja : 京都大学数理解析研究所講究録 巻 1426, p. 106-112, 発行日 2005-04 |
|||||
フォーマット | ||||||
application/pdf | ||||||
著者版フラグ | ||||||
値 | publisher | |||||
URI | ||||||
識別子 | http://hdl.handle.net/2237/9355 | |||||
識別子タイプ | HDL |