論文

査読有り
1998年4月

On the Church -Rosser Property of Root -E- overlapping and Strongly Depth- preserving Term Rewriting Systems

情報処理学会論文誌
  • Hiroshi Gomi
  • ,
  • Michio Oyamaguchi
  • ,
  • Yoshikatsu Ohta

39
4
開始ページ
992
終了ページ
1005
記述言語
英語
掲載種別

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.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/170000125333
CiNii Resolver ID
http://ci.nii.ac.jp/nrid/9000346948637