拓广的左线性递仅变换算法及其正确性  

TRANSFORMATION FOR GENERALIZED LEFT-LINEAR RECURSIONS: ALGORITHM AND ITS CORRECTNESS

作　　者：范明[1] 

机构地区：[1]郑州大学计算机科学系

出　　处：《软件学报》1994年第1期56-61,共6页Journal of Software

基　　金：河南省优秀中青年教师奖励基金

摘　　要：本文给出拓广的左线性递归变换算法并证明其正确性．拓广的左线性递归中可以包含一个或多个ＩＤＢ谓词，它是左线性递归的一般化．和左线性递归计算算法一样，本文提供的算法遵循魔集的模式：首先改写规则，然后用半扑质的自底向上算法计算新规则．算法的有效性也在本文作简略讨论．This paper presents an algorithm which transform a generalized left-linear recursion into more efficient rules,and shows the correctness of the given algorithm. A generalized left-linear recursion contains one or more IDB predicates and its definition is essentially generalized from that of left-linear recursions. As the algorithm for the evaluation of left - linear recursions, the algorithm we present here follows the magic-sets paradigm of a rewriting phase followed by semi -naive bottom-up evaluation. The efficinecy of the transformed rules is also discussed in this paper.

关 键 词：演绎数据库 线性递归 左线性递归 

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