右線形右シャローな項書換え系における文脈依存停止性の決定可能性について

• 御宿, 義勝

• 酒井, 正彦

• 坂部, 俊樹

• 草刈, 圭一朗

• 西田, 直樹

• MISHUKU, Yoshimasa

• SAKAI, Masahiro

• SAKABE, Toshiki

• KUSAKARI, Keiichirou

• NISHIDA, Naoki

書誌事項

タイトル別名

• ミギ センケイ ミギ シャロー ナ コウ カキカエ ケイ ニ オケル ブンミャク イソン テイシセイ ノ ケッテイ カノウセイ ニ ツイテ
• On Decidability of Context-Sensitive Termination for Right-Linear Right-Shallow Term Rewriting Systems

抄録

依存対が右線形右シャローである項書換え系のクラスでは,停止性および最内停止性が決定可能であることが示されている(内山ら2008年).しかし,文脈依存停止性の決定可能性は同クラスのうち,さらに左シャローであるクラスでしか示されていない.文脈依存書換えでは依存鎖中に停止しない項が存在することが,その停止性の解析を困難にしている.本論文ではまず,内山らの決定手続きが働かない左シャローでない項書換え系を例示する.次に,この困難性をもたらす原因を取り除くための十分条件を追加し,このクラスで文脈依存停止性が決定可能となることを示す.

収録刊行物

• 電子情報通信学会技術研究報告SS, ソフトウェアサイエンス

  電子情報通信学会技術研究報告SS, ソフトウェアサイエンス 109 (343), 31-36, 2009-12

  一般社団法人電子情報通信学会

キーワード

• 文脈依存停止性
• 決定可能性
• 右シャロー

詳細情報

• CRID: 1050564288756914560
• NII論文ID: 120005527808
• NII論文ID: 110008001254
• NII書誌ID: AA1123312X
• HANDLE: 2237/21106
• NDL書誌ID: 10509053
• ISSN: 09135685
• Web Site: https://nagoya.repo.nii.ac.jp/records/19002
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I10509053
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN