WEKO3
アイテム
右線形右シャローな項書換え系における文脈依存停止性の決定可能性について
http://hdl.handle.net/2237/21106
http://hdl.handle.net/2237/211061b176e31-bf6d-4913-972e-9d5b073759c3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
110008001254.pdf (949.7 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2015-01-20 | |||||
| タイトル | ||||||
| タイトル | 右線形右シャローな項書換え系における文脈依存停止性の決定可能性について | |||||
| 言語 | ja | |||||
| その他のタイトル | ||||||
| その他のタイトル | On Decidability of Context-Sensitive Termination for Right-Linear Right-Shallow Term Rewriting Systems | |||||
| 言語 | en | |||||
| 著者 |
御宿, 義勝
× 御宿, 義勝× 酒井, 正彦× 坂部, 俊樹× 草刈, 圭一朗× 西田, 直樹× MISHUKU, Yoshimasa× SAKAI, Masahiro× SAKABE, Toshiki× KUSAKARI, Keiichirou× NISHIDA, Naoki |
|||||
| アクセス権 | ||||||
| アクセス権 | open access | |||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
| 権利 | ||||||
| 言語 | ja | |||||
| 権利情報 | (c)一般社団法人電子情報通信学会。本文データは学協会の許諾に基づきCiNiiから複製したものである | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 文脈依存停止性 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 決定可能性 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 右シャロー | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 依存対が右線形右シャローである項書換え系のクラスでは,停止性および最内停止性が決定可能であることが示されている(内山ら2008年).しかし,文脈依存停止性の決定可能性は同クラスのうち,さらに左シャローであるクラスでしか示されていない.文脈依存書換えでは依存鎖中に停止しない項が存在することが,その停止性の解析を困難にしている.本論文ではまず,内山らの決定手続きが働かない左シャローでない項書換え系を例示する.次に,この困難性をもたらす原因を取り除くための十分条件を追加し,このクラスで文脈依存停止性が決定可能となることを示す. | |||||
| 言語 | ja | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | It is known that termination and innermost termination are decidable for term rewriting systems (TRSs for short) whose dependency pairs are all right-linear and right-shallow (Uchiyama et al, 2008). However, decidability of context-sensitive termination requires left-shallow restriction to those TRSs. The difficulty of context-sensitive termination analysis is caused by existence of non-terminating terms in dependency chains. In this paper, we first show a left-non-shallow TRS as a counterexample against the decision procedure. Then, we give a sufficient condition to make the procedure work properly, and show that context-sensitive termination is decidable for the class. | |||||
| 言語 | en | |||||
| 出版者 | ||||||
| 出版者 | 一般社団法人電子情報通信学会 | |||||
| 言語 | ja | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプresource | http://purl.org/coar/resource_type/c_6501 | |||||
| タイプ | journal article | |||||
| 出版タイプ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 関連情報 | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://ci.nii.ac.jp/naid/110008001254 | |||||
| ISSN | ||||||
| 収録物識別子タイプ | PISSN | |||||
| 収録物識別子 | 0913-5685 | |||||
| 書誌情報 |
ja : 電子情報通信学会技術研究報告SS, ソフトウェアサイエンス 巻 109, 号 343, p. 31-36, 発行日 2009-12 |
|||||
| 著者版フラグ | ||||||
| 値 | publisher | |||||
| URI | ||||||
| 識別子 | http://ci.nii.ac.jp/naid/110008001254 | |||||
| 識別子タイプ | URI | |||||
| URI | ||||||
| 識別子 | http://hdl.handle.net/2237/21106 | |||||
| 識別子タイプ | HDL | |||||
