<Emphasis Type="Italic">FC</Emphasis>-normal and extended stratified logic program

This paper investigates the consistency property ofFC-normal logic program and presents an equivalent deciding condition whether a logic programP is anFC-normal program. The deciding condition describes the characterizations ofFC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification ofFC-normal program are investigated. The stratification ofFC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is anFC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finiteFC-normal program.     

Consistency Property of Finite FC-Normal Logic Programs

Marek＇s forward-chaining construction is one of the important techniques for investigating the non-monotonic reasoning. By introduction of consistency property over a logic program, they proposed a class of logic programs, FC-normal programs, each of which has at least one stable model. However, it is not clear how to choose one appropriate consistency property for deciding whether or not a logic program is FC-normal. In this paper, we firstly discover that, for any finite logic programⅡ, there exists the least consistency property LCon（Ⅱ） overⅡ, which just depends onⅡitself, such that, Ⅱ is FC-normal if and only ifⅡ is FC-normal with respect to （w.r.t.） LCon（Ⅱ）. Actually, in order to determine the FC-normality of a logic program, it is sufficient to check the monotonic closed sets in LCon（Ⅱ） for all non-monotonic rules, that is LFC（Ⅱ）. Secondly, we present an algorithm for computing LFC（Ⅱ）. Finally, we reveal that the brave reasoning task and cautious reasoning task for FC-normal logic programs are of the same difficulty as that of normal logic programs.     

知识库维护过程中检查其协调性的有效方法

本文首先描述了知识库维护过程中的协调性问题，然后给出了扩充逻辑程序设计的框架，在此框架下，每个逻辑程序等价于一个知识库．为了检查知识库的协调性，本文为知识库中的推理规则构造了正支持集和负支持集，并给出了一些定义；基于这些概念和定义，提出了知识库维护过程中检查知识库协调性的一种有效方法，并证明了相关的定理；基于此方法，实现了一个算法ＣＨＩＭＥ，并给出了用ＣＨＩＭＥ分析一些知识库的实验结果．本文还提到一些相关的工作，最后给出结论.     

Disjunctive LP+integrity constraints= stable model semantics

We show that stable models of logic programs may be viewed as minimal models of programs that satisfy certain additional constraints. To do so, we transform the normal programs into disjunctive logic programs and sets of integrity constraints. We show that the stable models of the normal program coincide with the minimal models of the disjunctive program thatsatisfy the integrity constraints. As a consequence, the stable model semantics can be characterized using theextended generalized closed world assumption for disjunctive logic programs. Using this result, we develop a bottomup algorithm for function-free logic programs to find all stable models of a normal program by computing the perfect models of a disjunctive stratified logic program and checking them for consistency with the integrity constraints. The integrity constraints provide a rationale as to why some normal logic programs have no stable models.     

Logic Programs,Compatibility and Forward Chaining Construction

Logic programming under the stable model semantics is proposed as a non-monotonic language for knowledge representation and reasoning in artificial intelligence. In this paper, we explore and extend the notion of compatibility and the Λ operator, which were first proposed by Zhang to characterize default theories. First, we present a new characterization of stable models of a logic program and show that an extended notion of compatibility can characterize stable submodels. We further propose the notion of weak auto-compatibility which characterizes the Normal Forward Chaining Construction proposed by Marek, Nerode and Remmel. Previously, this construction was only known to construct the stable models of FC-normal logic programs, which turn out to be a proper subclass of weakly auto-compatible logic programs. We investigate the properties and complexity issues for weakly auto-compatible logic programs and compare them with some subclasses of logic programs.     

On Local StratifiabUity of Logic Programs and Databases

In this paper,we deal with the problem of verifying local stratifiability of logic programs anddatabases presented by Przymusinski.Necessary and sufficient conditions for the local stratifiability oflogic programs are presented and algorithms for performing the verification are developed.Finally,weprove that a database DB containing clauses with disjunctive consequents can be easily converted into alogic program P such that DB is locally stratified iff P is locally stratified.     

The expressiveness of locally stratified programs

This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be defined by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence, to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs does not increase when one considers the programs which have a unique stable model or a total well-founded model. This shows that all these classes of structures (perfect models of logically stratified logic programs, well-founded models which turn out to be total, and stable models of programs possessing a unique stable model) are all closely connected with Kleene's hyperarithmetical hierarchy. Thus, for general logic programming, negation with respect to two-valued logic is related to the hyperarithmetic hierarchy in the same way as Horn logic is to the class of recursively enumerable sets. In particular, a set is definable in the well-founded semantics by a programP whose well-founded partial model is total iff it is hyperarithmetic.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by NSF Grant IRI-9012902 and partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by NSF Grant IRI-8905166 and partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Equivalence of characterizations of fixed modes

In this paper an equivalent property of two matrix rank conditions of a family of matrices is established. This equivalent property is then used to show that two well-known characterizations of fixed modes are mutually derivable from each other when a minor condition is satisfied.     

Complexity and undecidability results for logic programming

This paper surveys complexity, degree of uncomputability, and expressive power results for logic programming. Some major decision problem complexity results and other results for logic programming are also covered. It also proves several new results filling in previous gaps in the literature. The paper considers seven logic programming semantics: the van Emden-Kowalski semantics for definite (Horn) logic programs; the perfect model semantics for stratified and for locally stratified logic programs; and the two- and three-valued program completion semantics, the well-founded semantics, and the stable semantics, all for normal logic programs, under skeptical inference. The main results concern expressibility and query complexity/uncomputability in five contexts: for propositional logic programs, for first order logic programs with infinite Herbrand universes on their Herbrand universes (a closed domain assumption), for first order logic programs with infinite Herbrand universes on those universes extended with infinitely many new elements (an open domain assumption), and for logic programs without function or constant symbols evaluated over varying extensional databases (DATALOG-type results, data complexity results only) under both closed and open domain assumptions. Several of the open domain assumption results are new to this paper. Other results surveyed are (1) results about the family of all stable models of a program and (2) decision questions about when a logic program has nice properties with respect to a semantics (e.g., a unique stable model). One decision result, for well-founded semantics, is new to this paper.Work supported in part by NSF grant IRI-8905166.     

Verifying local stratifiability of logic programs and databases

In this paper, we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski. The notion of dependency graphs is generalized from representing the priority relation between predicate symbols to representing the priority between atoms. Necessary and sufficient conditions for the local stratifiability of logic programs are presented and algorithms for performing the verification are developed. Finally, we prove that a database DB containing clauses with disjunctive consequents can easily be converted into a logic program P such that DB is locally stratified iff P is locally stratified. Yi-Dong Shen, Dr.: Department of Computer Science, Chongqing University, Chongqing, 630044, P.R. China (Present Address) c/o Ping Ran, Department of Heat Power Engineering, Chongqing UniversityResearch interests: Artificial Intelligence, Deductive Databases, Logic Programming, Non-Monotonic Reasoning, Parallel Processing     

The specification logic νZ

This paper introduces a wide-spectrum specification logic νZ. The minimal core logic is extended to a more expressive specification logic which includes a schema calculus similar (but not equivalent) to Z, new additional schema operators, and extensions to programming and program development logics.     

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

Submodular function minimization is a polynomially solvable combinatorial problem. Unfortunately the best known general-purpose algorithms have high-order polynomial time complexity. In many applications the objective function is locally defined in that it is the sum of cost functions (also known as soft or valued constraints) whose arities are bounded by a constant. We prove that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Such an equivalent instance is the result of establishing optimal soft arc consistency and can hence be found by solving a linear program. From a practical point of view, this provides us with an alternative algorithm for minimizing locally defined submodular functions. From a theoretical point of view, this brings to light a previously unknown connection between submodularity and soft arc consistency.     

The Specification Logic νZ

This paper introduces a wide-spectrum specification logic νZ. The minimal core logic is extended to a more expressive specification logic which includes a schema calculus similar (but not equivalent) to Z, some new additional schema operators and extensions to a programming and program development logic.     

Generalized disjunctive well-founded semantics for logic programs

Generalized disjunctive well-founded semantics (GDWFS) is a refined form of the generalized well-founded semantics (GWFS) of Baral, Lobo and Minker, to disjunctive logic programs. We describe fixpoint, model theoretic and procedural characterizations of GDWFS and show their equivalence. The fixpoint semantics is similar to the fixpoint semantics of the GWFS, except that it iterates over state-pairs (a pair of sets; one a set of disjunctions of atoms and the other a pair of conjunctions of atoms), rather than partial interpretations. The model theoretic semantics is based on a dynamic stratification of the program. The procedural semantics is based on SLIS refutations, + trees and SLISNF trees.     

Program partition and logic program analysis

A program partition scheme for stratified programs introduced by Apt et al. (1988) is used to study efficient computation of logic programs. We consider three types of program partitions and their corresponding graph representations: 1) the natural partition, 2) stratified partitions, and 3) the reduced partition. The natural (program) partition consists of definitions of relations, each definition being a subprogram. Subprograms of a program partition may consist of several relations. A partition graph is introduced for a program partition, each node of which corresponds to a subprogram. The partition graph for a stratified partition is a directed acyclic graph (DAG). A stratified partition decomposes a program into modules. The stratified partition with the maximum number of modules is the reduced partition. The cost to achieve a reduced partition is linear in the program size, using well known graph algorithms. We introduce the modular interpretations, which are equivalent in semantics to the standard interpretation. The modular interpretations offer encapsulation and may reduce the computation cost for some modules significantly. The modular approach can play an important role in query optimization, efficient termination, programming design, and software engineering. We classify query types and answer types then discuss query optimization for some query types. Many efficient query processing strategies are applicable to restricted subclasses of programs. The program partition method allows us to select the most efficient strategy for each module. For example, if a module is a uniformly bounded recursion, then the module can be terminated efficiently. If a module defines the transitive closure, then efficient program transformations may be applied to this module     

Characterization of an auto-compatible default theory

In this paper,an equivalence condition for deciding whether a default theory is an auto-compatible default one is presented.Under the condition,the existence of extension of an auto-compatible default theory is a natural result.By introducing a well-ordering over the set D of default rules,the extensions of an auto-compatible default theory(D,W) can be computed directly.The condition represents clearly the characterization of an auto-compatible default theory,and some properties about auto-compatible default theory,such as semi-monotonicity,become natural corollaries.Based on the characterization,the revision of default beliefs is discussed to ensure the existence of extension of the default theory,and the methos is applied to investigate stable models of a general logic program.     

扩展时段时序逻辑的模型、一致性和推理

给出了扩展时段时序逻辑的时间Petri网（TPN）模型构造方法，在构造模型的同时对时序关系进行一致性检验，在模型的基础上提出了一种时序关系推理算法，这种推理算法基于TPN模型的性质及基本不等式规则，可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系，这种推广理算法的优势在于利用了TNP模型的分析技术，减小了推理的时间复杂度比单纯利用不等式规则的推理更直观，也更简单，是一种有效的方法，最后，对扩展时段时序逻辑的TPN模型进行了扩充，增强了其模型和分析的能力。     

R-Calculus for ELP:An Operational Approach to Knowledge Base Maintenance

Sme concepts used in knowledge base maintenace,such as sequence,new law,user‘s rejection and reconstructions of a knowledge base,are first introduced,and then a framework for extended logic programming(ELP)is given,where an extended logic program is equivalent to a knowledge base.A transition system called R-calculus for ELP is provided.For a given knowledge base and a user‘s rejection,the R-calculus for ELP will deduce best revisions of the base.The soundness and the completeness of the R-calculus for ELP are proved,and the R-calculus for ELP is implemented in Prolog.In addition,the research is compared with other relevant work.     

扩充逻辑程序设计的R－演算──知识库维护的操作方法

本文首先介绍了知识库维护过程中诸如知识库序列、新规则、用户反驳以及重构等概念；然后给出了一个扩充逻辑程序设计的框架，在这一框架下，每个逻辑程序等价于一个知识库；进一步定义了一个转换系统，称为扩充逻辑程序设计的Ｒ－演算，对一个给定的知识库和用户反驳，此演算可以导出知识库的最佳修正；同时证明了该演算的可靠性和完备性；另外，对本文的工作与其他相关工作进行了比较；最后，给出了本文的结论．     

一阶子句搜索方法

子句集的可满足性判定是自动证明领域的热点之一.提出了子句搜索方法判定命题子句集Φ的可满足性,该方法查找Φ中子句的一个公共不可扩展子句C,当且仅当找到C时Φ可满足,此时C中各文字的补构成一个模型.结合部分实例化方法将子句搜索方法提升至一阶.一阶子句搜索方法可以判定子句集的M可满足性,具备终止性、正确性和完备性,是一种判定子句集可满足性的有效方法.