計算モデルとアルゴリズム On the Church -Rosser Property of Root -E- overlapping and Strongly Depth- preserving Term Rewriting Systems

この論文にアクセスする

この論文をさがす

著者

抄録

A term rewriting system(TRS)is said to be strongly depth-preserving if for any rewrite rule and any variable appearing in its both sides the minimal depth of the variable occurrences in the left-hand-side is greater than or equal to the maximal depth of the variable occurrences in the right-hand-side.This paper gives a sufficient condition for the Church-Rosser property of strongly depth-preserving TRS's and shows how to check this condition.By assigning a positive integer(called weight)to each function symbol the notion of a strongly depth-preserving system is naturally extended to that of a strongly weight-preserving system and a similar sufficient condition for the Church-Rosser propertyof strongly weight-preserving TRS's is obtained.A term rewriting system(TRS)is said to be strongly depth-preserving if for any rewrite rule and any variable appearing in its both sides,the minimal depth of the variable occurrences in the left-hand-side is greater than or equal to the maximal depth of the variable occurrences in the right-hand-side.This paper gives a sufficient condition for the Church-Rosser property of strongly depth-preserving TRS's and shows how to check this condition.By assigning a positive integer(called weight)to each function symbol,the notion of a strongly depth-preserving system is naturally extended to that of a strongly weight-preserving system,and a similar sufficient condition for the Church-Rosser propertyof strongly weight-preserving TRS's is obtained.

A team rewriting system(TRS)is said to be strongly depth-preserving if for any rewrite rule and any variable appearing in its both sides, the minimal depth of the variable occurrences in the left-hand-side is greater than or equal to the maximal depth of the variable occurrences in the right-hand-side. This paper gives a sufficient condition for the Church-Rosser property of strongly depth-preserving TRS's and shows how to check this condition. By assigning a positive integer(called weight)to each function symbol, the notion of a strongly depth preserving system is naturally extended to that of a strongly weight-preserving system, and a similar sufficient condition for the Church-Rosser property of strongly weight-preserving TRS's is obtained.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 39(4), 992-1005, 1998-04-15

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

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

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

各種コード

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