# 計算モデルとアルゴリズム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

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

## 各種コード

• 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

ページトップへ