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.     

On Local Stratifiability of Logic Prograns and Databases

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

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.     

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.     

Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism (?) of logic programs from P to P' is a function mapping Atoms(P) to Atoms(P') and it preserves complements and program clauses. For each definite program clause a←a1,...,an∈P it implies that (?)(a)←(?)(a1),...,(?)(an) is a program clause of P'. A homomorphism (?) is an isomorphism if (?) is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP-complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI).     

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.     

On the Relationship Between TMS and Logic Programs

The relationship between TMS and general logic programs is an important issue in non-monotonic logic programming.In this paper,we prove that,after we translate the TMS theory into a general logic program,the TMS‘s well-founded assignment (or extension) is equivalent to the corresponding general logic program‘s stable model.It means that TMS can be completely integrated into a non-monotonic logic programming environment.     

A characterization of answer sets for logic programs

Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems in answer set logic programming. Solving these problems using Gelfond and Lifschitz's original definition of answer sets is not an easy task. Alternative characterizations of answer sets for nested logic pro- grams by Erdem and Lifschitz, Lee and Lifschitz, and You et al. are based on the completion semantics and various notions of tightness. However, the notion of tightness is a local notion in the sense that for different answer sets there are, in general, different level mappings capturing their tightness. This makes it hard to be used in the design of algorithms for computing answer sets. This paper proposes a characterization of answer sets based on sets of generating rules. From this char- acterization new algorithms are derived for computing answer sets and for per- forming some other reasoning tasks. As an application of the characterization a sufficient and necessary condition for the equivalence between answer set seman- tics and completion semantics has been proven, and a basic theorem is shown on computing answer sets for nested logic programs based on an extended notion of loop formulas. These results on tightness and loop formulas are more general than that in You and Lin's work.     

An algebraic approach to revising propositional rule-based knowledge bases

One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the problem. An algebraic approach is presented to revise propositional rule-based knowledge bases in this paper. A way is firstly introduced to transform a propositional rule-based knowledge base into a Petri net. A knowledge base is represented by a Petri net, and facts are represented by the initial marking. Thus, the consistency check of a knowledge base is equivalent to the reachability problem of Petri nets. The reachability of Petri nets can be decided by whether the state equation has a solution; hence the consistency check can also be implemented by algebraic approach. Furthermore, algorithms are introduced to revise a propositional rule-based knowledge base, as well as extended logic programming. Compared with related works, the algorithms presented in the paper are efficient, and the time complexities of these algorithms are polynomial.     

A Logic-Program-Based Negotiation Mechanism

This paper presents a logic-program-based mechanism of negotiation between two agents.In this mechanism an extended logic program(ELP) is regarded as an agent.The negotiation process between two agents is then modelled as multiple encounters between two ELPs,each of which selects an answer set as its initial demand.Both agents mutually revise the original sets of demands through accepting part of the opponent's demand and/or giving up part of its own demand.The overall dynamics can be regarded as mutual ...     

<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.     

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

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

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.     

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.     

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