WEKO3
アイテム
Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs
http://hdl.handle.net/2237/21159
http://hdl.handle.net/2237/211591fe75a88-0b6b-49fe-a666-0dcf5460cfc4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
e93-d_5_953.pdf (505.8 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2015-01-29 | |||||
| タイトル | ||||||
| タイトル | Decidability of Termination and Innermost Termination for Term Rewriting Systems with Right-Shallow Dependency Pairs | |||||
| 言語 | en | |||||
| 著者 |
UCHIYAMA, Keita
× UCHIYAMA, Keita× SAKAI, Masahiko× SAKABE, Toshiki |
|||||
| アクセス権 | ||||||
| アクセス権 | open access | |||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
| 権利 | ||||||
| 言語 | ja | |||||
| 権利情報 | (c)一般社団法人電子情報通信学会。本文データは学協会の許諾に基づきCiNiiから複製したものである | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | looping sequence | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | argument propagation | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | In this paper, we show that the termination and the innermost termination properties are decidable for the class of term rewriting systems (TRSs for short) all of whose dependency pairs are right-linear and right-shallow. We also show that the innermost termination is decidable for the class of TRSs all of whose dependency pairs are shallow. The key observation common to these two classes is as follows: for every TRS in the class, we can construct, by using the dependency-pairs information, a finite set of terms such that if the TRS is non-terminating then there is a looping sequence beginning with a term in the finite set. This fact is obtained by modifying the analysis of argument propagation in shallow dependency pairs proposed by Wang and Sakai in 2006. However we gained a great benefit that the resulted procedures do not require any decision procedure of reachability problem used in Wang's procedure for shallow case, because known decidable classes of reachability problem are not larger than classes discussing in this paper. | |||||
| 言語 | en | |||||
| 出版者 | ||||||
| 出版者 | 一般社団法人電子情報通信学会 | |||||
| 言語 | ja | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 出版タイプ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 関連情報 | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | URI | |||||
| 関連識別子 | https://search.ieice.org/ | |||||
| ISSN | ||||||
| 収録物識別子タイプ | PISSN | |||||
| 収録物識別子 | 0916-8532 | |||||
| 書誌情報 |
en : IEICE transactions on information and systems 巻 E93D, 号 5, p. 953-962, 発行日 2010-05 |
|||||
| 著者版フラグ | ||||||
| 値 | publisher | |||||
| URI | ||||||
| 識別子 | https://search.ieice.org/ | |||||
| 識別子タイプ | URI | |||||
| URI | ||||||
| 識別子 | http://hdl.handle.net/2237/21159 | |||||
| 識別子タイプ | HDL | |||||
