書誌事項
- タイトル別名
-
- ミギ センケイ ミギ シャロー ナ コウ カキカエ ケイ ニ オケル ブンミャク イソン テイシセイ ノ ケッテイ カノウセイ ニ ツイテ
- On Decidability of Context-Sensitive Termination for Right-Linear Right-Shallow Term Rewriting Systems
この論文をさがす
抄録
依存対が右線形右シャローである項書換え系のクラスでは,停止性および最内停止性が決定可能であることが示されている(内山ら2008年).しかし,文脈依存停止性の決定可能性は同クラスのうち,さらに左シャローであるクラスでしか示されていない.文脈依存書換えでは依存鎖中に停止しない項が存在することが,その停止性の解析を困難にしている.本論文ではまず,内山らの決定手続きが働かない左シャローでない項書換え系を例示する.次に,この困難性をもたらす原因を取り除くための十分条件を追加し,このクラスで文脈依存停止性が決定可能となることを示す.
収録刊行物
-
- 電子情報通信学会技術研究報告SS, ソフトウェアサイエンス
-
電子情報通信学会技術研究報告SS, ソフトウェアサイエンス 109 (343), 31-36, 2009-12
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050564288756914560
-
- NII論文ID
- 120005527808
- 110008001254
-
- NII書誌ID
- AA1123312X
-
- HANDLE
- 2237/21106
-
- NDL書誌ID
- 10509053
-
- ISSN
- 09135685
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- IRDB
- NDL
- CiNii Articles
- KAKEN