ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について On the Church-Rosser Property of Root-E-overlapping and 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 the 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 occurrence; in the right-hand-side. This paper gives a sufficient condition for Church-Rosser of strongly depth-preserving TRS's and describes how to check this condition. By assigning a positive integer (called weight) to each function symbol, the notion of strongly depth-preserving is naturally extended to that of strongly weight-preserving and a similar sufficient condition for Church-Rosser of strongly weight-preserving TRS's is obtained.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 96(488), 9-16, 1997-01-24

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

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

各種コード

  • NII論文ID(NAID)
    110003191441
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • データ提供元
    CJP書誌  NII-ELS 
ページトップへ