順方向ナローイングに基づく右線形右シャロー項書換え系の非停止性証明について

• 服部, 達哉

• 酒井, 正彦

• 西田, 直樹

• 草刈, 圭一朗

• 坂部, 俊樹

• HATTORI, Tatsuya

• SAKAI, Masahiko

• NISHIDA, Naoki

• KUSAKARI, Keiichirou

• SAKABE, Toshiki

書誌事項

タイトル別名

• ジュン ホウコウ ナローイング ニ モトズク ウセンケイ ウシャローコウ カキカエ ケイ ノ ヒテイシセイ ショウメイ ニ ツイテ
• On non-termination proof of right-linear and right-shallow term rewriting systems based on forward narrowing

抄録

順方向ナローイングに基づく非停止性証明解析はAProVE等の停止性証明ツールに採用されている.しかしながら,それが完全である項書換え系のクラス,すなわち,非停止性をもつならば順方向ナローイングに基づく解析でそれが証明可能となるクラスは知られていない.本論文では,依存対が右線形右シャローである項書換え系においては,順方向ナローイングに基づく解析が完全であることを示す.

収録刊行物

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

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

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

キーワード

• 停止性証明ツール
• 完全性
• 依存対
• termination tool
• completeness
• dependency pair

詳細情報

• CRID: 1050001338803500416
• NII論文ID: 110008675938
• NII論文ID: 120005530808
• NII書誌ID: AA1123312X
• HANDLE: 2237/21154
• NDL書誌ID: 10936543
• ISSN: 09135685
• Web Site: https://nagoya.repo.nii.ac.jp/records/19048
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I10936543
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles