基礎理論 On the Church - Rosser Property of Non -E- overlapping and Strongly Depth - preserving Term Rewriting Systems

この論文にアクセスする

この論文をさがす

著者

抄録

A term rewriting system (TRS) is said to be depth-preserving if for any rewrite rule and any variable appearing in the both sides the maximal depth of the variable occurrences in the left-hand-side is greater than or equal to that of the variable occurrences in the right-hand-side and to be strongly depth-preserving if it is depth-preserving and for any rewrite rule and any variable appearing in the left-hand-side all the depths of the variable occurrences in the left-hand-side are the same. This paper shows that there exit non-E-overlapping and depth-preserving TRS's which are not Church-Rosser but all the non-E-overlapping and strongly depth-preserving TRS's are Church-Rosser.A term rewriting system (TRS) is said to be depth-preserving if for any rewrite rule and any variable appearing in the both sides, the maximal depth of the variable occurrences in the left-hand-side is greater than or equal to that of the variable occurrences in the right-hand-side, and to be strongly depth-preserving if it is depth-preserving and for any rewrite rule and any variable appearing in the left-hand-side, all the depths of the variable occurrences in the left-hand-side are the same. This paper shows that there exit non-E-overlapping and depth-preserving TRS's which are not Church-Rosser, but all the non-E-overlapping and strongly depth-preserving TRS's are Church-Rosser.

A term rewriting system (TRS) is said to be depth-preserving if for any rewrite rule and any variable appearing in the both sides, the maximal depth of the variable occurrences in the left-hand-side is greater than or equal to that of the variable occurrences in the right-hand-side, and to be strongly depth-preserving if it is depth-preserving and for any rewrite rule and any variable appearing in the left-hand-side, all the depths of the variable occurrences in the left-hand-side are the same. This paper shows that there exit non-E-overlapping and depth-preserving TRS's which are not Church-Rosser, but all the non-E-overlapping and strongly depth-preserving TRS's are Church-Rosser.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 37(12), 2147-2160, 1996-12-15

    一般社団法人情報処理学会

参考文献:  9件中 1-9件 を表示

被引用文献:  3件中 1-3件 を表示

各種コード

  • NII論文ID(NAID)
    110002723107
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    ENG
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    4095181
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ