带函数析取逻辑程序的无基集及其应用

基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的）,目前还没有有效的方法来计算带函数析取逻辑程序的回答集,主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念,发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系,在此基础上,证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的,从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。     

Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction

In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.     

The List Introduction Strategy for the Derivation of Logic Programs

We present a new program transformation strategy based on the introduction of lists. This strategy is an extension of the tupling strategy which is based on the introduction of tuples of fixed length. The list introduction strategy overcomes some of the limitations of the tupling strategy and, in particular, it makes it possible to transform general recursive programs into linear recursive ones also in cases when this transformation cannot be performed by the tupling strategy. The linear recursive programs we derive by applying the list introduction strategy have in most cases very good time and space performance because they avoid repeated evaluations of goals and unnecessary constructions of data structures. Received December 2000 / Accepted in revised form January 2002     

Elimination of Local Variables from Definite Logic Programs

In logic programming, a variable is said to be local if it occurs in a clause body but not in its head atom. It is well-known that local variables are the main cause of inefficiency (sometimes even incompleteness) in negative goal computation. The problem is twofold. First, the negation of a clause body that contains a local variables is not expressible without universal quantification, whereas the abscence of local variables guarantees that universal quantification can be avoided to compute negation. Second, computation of universal quantification is an intrinsically difficult task. In this paper, we introduce an effective method that takes a definite logic program and transforms it into a local variable free (definite) program. Source and target programs are equivalent w.r.t. three-valued logical consequences of program completion. In further work, we plan to extend our results to normal logic programs.     

The Branching-Time Transformation Technique for Chain Datalog Programs

The branching-time transformation technique has proven to be an efficient approach for implementing functional programming languages. In this paper we demonstrate that such a technique can also be defined for logic programming languages. More specifically, we first introduce Branching Datalog, a language that can be considered as the basis for branching-temporal deductive databases. We then present a transformation algorithm from Chain Datalog programs to the class of unary Branching Datalog programs with at most one IDB atom in the body of each clause. In this way, we obtain a novel implementation approach for Chain Datalog, shedding at the same time new light on the power of branching-time logic programming.     

Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.A preliminary version of this paper appears as: Reducing Nondeterminism while Specializing Logic Programs. Proceedings of the 24th Annual ACM Symposium on Principles of Programming Languages, Paris, France, January 15–17, 1997, ACM Press, 1997, pp. 414–427.     

Static and Dynamic Slicing of Constraint Logic Programs

Slicing is a program analysis technique originally developed for imperative languages. It facilitates understanding of data flow and debugging.This paper discusses slicing of Constraint Logic Programs. Constraint Logic Programming (CLP) is an emerging software technology with a growing number of applications. Data flow in constraint programs is not explicit, and for this reason the concepts of slice and the slicing techniques of imperative languages are not directly applicable.This paper formulates declarative notions of slice suitable for CLP. They provide a basis for defining slicing techniques (both dynamic and static) based on variable sharing. The techniques are further extended by using groundness information.A prototype dynamic slicer of CLP programs implementing the presented ideas is briefly described together with the results of some slicing experiments.     

逻辑程序的事实维护

事实是逻辑程序的重要组成部分,事实维护影响着整个逻辑程序的一致性和完整性,并能够促进和完善规则维护。论文在分析了人工进行维护操作的弊端后,对事实维护中可能出现的情况进行分类分析,提出了事实维护系统的框架,重点描述了预警检测子系统所扮演的核心作用。     

一个支持非独立“与”并行的逻辑程序“与”并行执行模型

本提出了一种支持非独立“与”并行的新型“与”并行执行模型ＤＡＰＭ，它通过在共享变元之间建立一种类似生产和消费的同步依赖关系以防止它们在并行执行时产生的约束冲突。与其它模型相比，ＤＡＰＭ可以开发更多的“与”并行。本还从理论上对ＤＡＰＭ的运行代价进行了分析，其分析结果表明ＤＡＰＭ只需较小的运行时刻支持。