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

本文从左，右线性递归规则组的定义出发，提出了广义左，右线性递归规则组的定义，放宽了左，右线性递归规则组寻规则形式的限制，扩展了Ｕｌｌｍａｎ提出的左，右线性递归规则组改写方法的适用范围。本文证明了由广义左，右线性递归规则组向左，右线性规则组转换的相容性，并给出了具体的转换算法。     

一类链规则递归查询优化

利用正则语言与有限自动机的关系以及数据库图，对一类链规则递归查询（即正则路问题）作研究。并且重写规则使递归谓词元数减少，以达到优化的目的。     

递归查询算法的研究

本文介绍了ＤｅＤＢ的递归查询算法，提出为减少冗余及回溯计算的基本原理．根据该原理，提出了一种高效的递归查询算法ＧＣＱＡ，它包括２部分，一是预编译算法；另一个是递归编译算法．实验结果表明这种算法是高效的．     

一个线性递归查询算法的设计与实现

旨在解决在演绎数据库中，如何利用递归规则进行递归查询的问题。介绍了一个线性递归查询算法的基本思想，阐述了该算法的设计与具体实现，包括算法采用的数据结构、程序中各功能模块的功能，对算法进行了分析。     

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

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

基于分布式的Web log挖掘模型

本文提出了一种基于分布式web log挖掘模型，并针对该模型设计了一种有效的基于分布式的挖掘算法。该算法首先在各分布式服务器上进行关联规则挖掘，然后将各个服务器上的挖掘结果合成。这有利于减轻网络频繁的通讯负担，体现并行计算、异步挖掘、异构数据挖掘的优点。     

信息网数据库管理系统规则的设计与实现

为了实现信息网数据库管理系统INMDBMS(Information Network Database Management System)的逻辑推理功能,提出了适用于INMDBMS的信息规则语言IRL(Information Rule Language)用于规则的表示。总结Datalog语言中几种传统的递归查询算法,同时结合INMDBMS的数据模型特点,设计并实现了IGQA(INMDB Goal_driven Recursive Query Algorithm)作为IRL规则语言的递归查询算法。IGQA以深度优先、回退的方式来实现递归查询。在真实数据集上的实验表明,当数据规模增长时,IGQA具有较高的执行成功率和较好的执行时间稳定性。     

上下文无关文法推断中的几条启发规则及其应用

本文先简要介绍了一种上下文无关文法的推断方法--逐步求精法，然后论述了递归概念在文法推断中的核心作用，并从递归概念的特殊性质出发提出了多条启发规则，能有效减少无效探求和与用户交互的次数，尤其适合于文法较复杂、例句集信息量较大的情况。这些启发规则同时也适用于对上下文无关文法的其它推断方法。     

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

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

堆栈、队列的CDT

ＣＤＴ（范畴数据类型）为并行计算的研究提供了一种新的工具和方法。该文为堆栈、队列类型构造了 ＣＤＴ,给出了它们的ＣＤＴ变换及同态操作的递归算法并用实际例子说明了它们同志操作中固有的并行性。     

Asynchronous chain recursions

The authors study the compilation and efficient processing of asynchronous chain recursions and show that many complex function-free recursions, which may contain single or multiple linear recursive rules, nonlinear recursive rules, mutually recursive rules, and multiple-level recursions, can be compiled to asynchronous chain recursions. The study on the compilation methods, the simplification of compiled formulas, and the query-processing techniques shows that asynchronous chain recursions can be compiled to relatively simple compiled formulas and processed efficiently using transitive closure query-processing methods     

On linear list recursion in parallel

We propose a classification for a set of linearly recursive functions, which can be expressed as instances of a skeleton for parallel linear recursion, and present new parallel implementations for them. This set includes well known higher-order functions, like Broadcast, Reduction and Scan, which we call basic components. Many compositions of these basic components are also linearly recursive functions; we present transformation rules from compositions of up to three basic components to instances of our skeleton. The advantage of this approach is that these instances have better parallel implementations than the compositions of the individual implementations of the corresponding basic components. Received: 27 May 1997 / Revised version: 17 March 1998     

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.     

Processing recursive queries on transputers

There is a perceived need within the database community to extend the traditional relational database systems so as to accommodate applications which are deductive in nature. One major problem involved in such an extension is the efficient processing of recursive queries. To this end, parallel processing is expected to play an important role. While substantial work has been done in devising strategies for processing recursive queries in parallel, it is perhaps surprising that little has been reported on the implementation and the run-time performance of these strategies. In the paper we report our experience of implementing a pipelined evaluation strategy on transputers. A wide range of queries, database structures and architectural configurations are considered as benchmarks in this study. The performance is studied in terms of both speed-up factors and communication costs. The experimental results show the potential of processing recursive queries in parallel, and provide insight into the usefulness of using transputers for such applications.     

Optimizing FORTRAN Programs for Hierarchical Memory Parallel Processing Systems

Parallel loops account for the greatest amount of parallelism in numerical programs.Executing nested loops in parallel with low run-time overhead is thus very important for achieving high performance in parallel processing systems.However,in parallel processing systems with caches or local memories in memory hierarchies,“thrashing problemmay”may arise whenever data move back and forth between the caches or local memories in different processors.Previous techniques can only deal with the rather simple cases with one linear function in the perfactly nested loop.In this paper,we present a parallel program optimizing technique called hybri loop interchange(HLI)for the cases with multiple linear functions and loop-carried data dependences in the nested loop.With HLI we can easily eliminate or reduce the thrashing phenomena without reucing the program parallelism.     

Linearizing some recursive logic programs

We give a sufficient condition under which the least fixpoint of the equation X=a+f(X)X equals the least fixpoint of the equation X=a+f(a)X. We then apply that condition to recursive logic programs containing chain rules: we translate it into a sufficient condition under which a recursive logic program containing n⩾2 recursive calls in the bodies of the rules is equivalent to a linear program containing at most one recursive call in the bodies of the rules. We conclude with a discussion comparing our condition with the other approaches to linearization studied in the literature     

Compiling general linear recursions by variable connection graph analysis

Compilation is a powerful preprocessing technique in the processing of recursions in knowledge-based systems. This paper develops a method of compiling and optimizing complex function-free linear recursions using a variable connection graph, the V-graph. It shows that a function-free recursion consisting of a linear recursive rule and one or more nonrecursive rules can be compiled to (1) a bounded recursion, in which recursion can be eliminated from the program, or (2) an n -chain recursion, whose compiled formula consists of one chain, when n = 1, or n synchronized compiled chains, when n > 1. The study is based on a classification of linear recursions and a study of the compilation results of each class. Using the variable connection graph, linear recursions are classified into six classes: acyclic paths, unit cycles, uniform cycles, nonuniform cycles, connected components, and their disjoint mixtures. Recursions in each class share some common properties in compilation. Our study presents an organized picture for the compilation of general function-free linear recursions. After compilation, the processing of complex linear recursions becomes essentially the processing of primitive n -chain recursions or bounded recursions to which efficient processing methods are available.     

Efficient finite impulse response filters in massively-parallel recursive systems

This paper presents strategies to massively parallelize complete recursive systems. Each algorithm handles systems with feedforward and feedback coefficients allowing to compute high-complexity filtering operators. The final algorithm is linear in time and memory, exposes a high number of parallel tasks, and it is implemented on graphics processing units, i.e. GPUs. The key to the final algorithm is the derivation of closed-form formulas to combine both non-recursive and recursive linear filters, based on an efficient state-of-the-art block-based strategy. Applications to early vision are considered in this work, hence the GPU implementation runs on images computing an approximation of the Gaussian filter and its first and second derivatives. Finally, comparison results are given showing that this work outperforms prior state-of-the-art algorithms, enabling it to achieve real-time image filtering on ultra-high-definition videos.