线性递归规则的并行计算方法

本文通过对现有的递归规则的并行计算方法以及并行计算的二分技术的讨论，提出了一种新颖的递归规则并行计算的基本策略，并给出了一种基于线性递归规则的并行计算方法。     

具有多值约束的线性递归查询的有效计算

本文给出三个算法,分别用于把给定的右线性、左线性或左-右线性递归程序改写为一组更有效的规则.与Ullman等人的变换算法不同,本文的算法允许查询的初始约束可以是含任意多个约束元组的集合,而不必是单值的;这样,本文的算法不仅可以用于查询的求值,而且也可以用于子目标的处理.变换算法的正确性和变换后规则的有效性也在本文简略讨论.     

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

本文给出拓广的左线性递归变换算法并证明其正确性．拓广的左线性递归中可以包含一个或多个ＩＤＢ谓词，它是左线性递归的一般化．和左线性递归计算算法一样，本文提供的算法遵循魔集的模式：首先改写规则，然后用半扑质的自底向上算法计算新规则．算法的有效性也在本文作简略讨论．     

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

本给出拓广的左线性递归变换算法并证明其正确性。拓广的左线性递归中可以包含一个或多个ＩＤＢ谓词，它是左线性递归的一般化和左线性递归计算算法一样，本提供的算法遵循魔集的模式：首先改写规则，然后用半扑质的自底向上算法计算新规则，算法的有效性也在本作简略讨论。     

拓广的右线性递归变换算法及其正确性

本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个IDB谓词,它是右线性递归的一般化.和右线性递归计算算法一样,本文提供的算法遵循魔集的模式:首先改写规则,然后用半扑质的自底向上算法计算新规则.算法的有效性通过减少递归谓词的元数实现.     

XML中的主动规则及其可终止性分析

主动XML系统一般采用触发器，即“事件-条件-动作”(ECA)规则来提供主动行为。本文提出了一种新的事件监测机制，在XML系统中引入‘主动节点’，即把规则也融入节点，各节点上的ECA规则只需在节点修改时被激活并进行检查，提高了动作的执行效率，增强了系统的实时性。本文结合规则实例给出了分析规则终止性的静态判定算法，引入触发图、活化图、修改后的触发图、触发环等概念，对触发图中的简单触发环进行转换，产生一个对应于触发环的循环语句，对触发环中每一个被修改的节点产生一个递归等式。展开递归等式检验它的可满足性可以用来分析规则集的可终止性。这一算法提高了可终止性判定的精确性，降低了复杂度。     

递归程序的计算规划分析与研究

在程序设计中，为了处理重复性的计算，最常用的办法是采用递归计算。理论上讲，对递归程序的处理有不同的计算规则。本文从理论上及实践上对递归程序的计算过程进行了详细的探讨，在对多种程序设计语言中关于递归程序的计算过程进行分析基础之上，对递归程序计算规则进行了总结。     

递归程序的计算规则分析与研究

在程序设计中 ,为了处理重复性的计算 ,最常用的办法是采用递归计算。理论上讲 ,对递归程序的处理有不同的计算规则。本文从理论上及实践上对递归程序的计算过程进行了详细的探讨 ,在对多种程序设计语言中关于递归程序的计算过程进行分析基础之上 ,对递归程序计算规则进行了总结     

线性链规则递归查询的研究

讨论Ｄａｔａｌｏｇ线性链规则递归查询问题，利用数据库图可将它归约为普通传递闭包问题。     

广义查询的计数算法

计数算法是最著名的ＳＬ递归处理算法之一．对于一类称作计数线性的递归，它具有良好的性能．然而，计数算法要求查询的约束集为单值的，因此很难用作子目标的处理策略．本文提供一种新的广义查询计数算法，它能处理任意的多值约束集．从而本文提供的算法不仅能够用于查询的求值，而且也能用于子目标的处理．算法的正确性和变换后的规则的有效性也在本文简略讨论．     

Decidability for Left-Linear Growing Term Rewriting Systems

A term rewriting system is called growing if each variable occurring on both the left-hand side and the right-hand side of a rewrite rule occurs at depth zero or one in the left-hand side. Jacquemard showed that the reachability and the sequentiality of linear (i.e., left-right-linear) growing term rewriting systems are decidable. In this paper we show that Jacquemard's result can be extended to left-linear growing rewriting systems that may have right-nonlinear rewrite rules. This implies that the reachability and the joinability of some class of right-linear term rewriting systems are decidable, which improves the results for right-ground term rewriting systems by Oyamaguchi. Our result extends the class of left-linear term rewriting systems having a decidable call-by-need normalizing strategy. Moreover, we prove that the termination property is decidable for almost orthogonal growing term rewriting systems.     

右线性文法与有限自动机等价性的一个新证明

迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...     

On the completeness of naive memoing in Prolog

Memoing is often used in logic programming to avoid redundant evaluation of similar goals, often on programs that are inherently recursive in nature. The interaction between memoing and recursion, however, is quite complex. There are several top-down evaluation strategies for logic programs that utilize memoing to achieve completeness in the presence of recursion. This paper’s focus, however, is on the use ofnaive memoing in Prolog. Using memoingnaively in conjunction with recursion in Prolog may not produce expected results. For example, adding naive memoing to Prolog’s evaluation of a right-recursive transitive closure may be incomplete, whereas adding naive memoing to Prolog’s evaluation of a left-recursive transitive closure may be terminating and complete. This paper examines the completeness of naive memoing in linear-recursive, function-free logic programs evaluated with Prolog’s top-down evaluation strategy. In addition, we assume that the program is definite and safe, having finite base relations and exactly one recursive predicate. The goal of the paper is a theoretical study of the completeness of naive memoing and recursion in Prolog, illustrating the limitations imposed even for this simplified class of programs. The naive memoing approach utilized for this study is based on extension tables, which provide a memo mechanism with immediate update view semantics for Prolog programs, through a source transformation known as ET. We introduce the concept ofET-complete, which refers to the completeness of the evaluation of a query over a Prolog program that memos selected predicates through the ET transformation. We show that left-linear recursions defined by a single recursive rule are ET-complete. We generalize the class of left-linear recursions that are ET-complete by introducing pseudo-left-linear recursions, which are also defined by a single linear recursive rule. To add left-linear recursions defined bymultiple linear recursive rules to the class of ET-complete recursions, we present a left-factoring algorithm that converts left-linear recursions defined by multiple recusive rules into pseudo-left-linear recursions defined by a single recursive rule. Based on these results, the paper concludes by identifying research directions for expanding the class of Prolog programs to be examined in future work. This work was partially supported by the National Science Foundation under Grant CCR-9008737. Suzanne Wagner Dietrich, Ph.D.: She is an Associate Professor in the Department of Computer Science and Engineering at Arizona State University. Her research emphasis is on the evaluation of declarative logic programs especially in the context of deductive databases, including materialized view maintenance and condition monitoring in active deductive databases. More recently, her research interests include the integration of active, object-oriented and deductive databases as well as the application of this emerging database technology to various disciplines such as software engineering. She received the B. S. degree in computer science in 1983 from the State University of New York at Stony Brook, and as the recipient of an Office of Naval Research Graduate Fellowship, earned her Ph.D. degree in computer science at Stony Brook in 1987. Changguan Fan, M.S.: He is a Ph.D. candidate in the Department of Computer Science and Engineering at Arizona State University and a software engineer at the Regenisys Corporation in Scottsdale, AZ. His research interests include the evaluation of logic programs, deductive database systems and database management systems. He received his B.S. in Computer Science from the Shanghai Institute of Railway Technology, Shanghai, China in 1982 and his M.S. in the Department of Computer Science and Engineering at Arizona State University in 1989.     

Graphic representation of linear recursive rules

Recursive rules are important to deductive databases. A recursive rule may be compiled into expansions. In this article, the variable-predicate graph (V-P graph) based on the α-graph by loannidis is developed to represent linear recursive function-free rules and their expansions. A naming convention is used for variables and predicates in the V-P graph so that all equivalent recursive rules may map into a unique V-P graph. We propose a graphic construction method (g.c.m.) which derives V-P graphs of expansions directly from the V-P graph of the original rule. This graphic representation reveals some expansion properties not easy to obtain otherwise. We also propose a rule rewriting method in the context of deductive database so that constants, repeated distinguished variables, and/or repeated recursive variables may be removed from recursive rules.     

Non-Linear Rewrite Closure and Weak Normalization

A rewrite closure is an extension of a term rewrite system with new rules, usually deduced by transitivity. Rewrite closures have the nice property that all rewrite derivations can be transformed into derivations of a simple form. This property has been useful for proving decidability results in term rewriting. Unfortunately, when the term rewrite system is not linear, the construction of a rewrite closure is quite challenging. In this paper, we construct a rewrite closure for term rewrite systems that satisfy two properties: the right-hand side term in each rewrite rule contains no repeated variable (right-linear) and contains no variable occurring at depth greater than one (right-shallow). The left-hand side term is unrestricted, and in particular, it may be non-linear. As a consequence of the rewrite closure construction, we are able to prove decidability of the weak normalization problem for right-linear right-shallow term rewrite systems. Proving this result also requires tree automata theory. We use the fact that right-shallow right-linear term rewrite systems are regularity preserving. Moreover, their set of normal forms can be represented with a tree automaton with disequality constraints, and emptiness of this kind of automata, as well as its generalization to reduction automata, is decidable. A preliminary version of this work was presented at LICS 2009 (Creus 2009).     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.