广义左、右线性递归规则组改写  

RULE TRANSFORMATION FOR GENERAL RIGHT-AND LEFT-LINEAR RECURSIVE RULES

作　　者：袁军[1] 陈栋[1] 王能斌[1] 

机构地区：[1]东南大学计算机科学与工程系

出　　处：《计算机学报》1996年第1期36-42,共7页Chinese Journal of Computers

摘　　要：本文从左、右线性递归规则组的定义出发，提出了广义左、右线性递归规则组的定义，放宽了左、右线性递归规则组对递归规则形式的限制，扩展了Ｕｌｌｍａｎ提出的左、右线性递归规则组改写方法的适用范围．本文证明了由广义左、右线性递归规则组向左、右线性递归规则组转换的相容性，并给出了具体的转换算法．This paper gives the definitions of general right-linear and left-linear recursive rules. The definitions weaken the restriction, imposed by the definition ofright-linear and left-linear recursive rules, on the form of linear recursive rule. It is proved that any general right-linear and left-linear recursive rule can be rewritteninto a set of right-linear and left-linear recursive rules with same semantics, and the algorithm of the transformation is presented in this paper. Therefore, the optimization strategy for right-linear and left-linear recursive rules proposed by Ullman canbe used in a wider range of linear recursive rules.

关 键 词：规则改写 数据库 线性递归规则 递归规则 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]