
	Logic Programming at KR'98 Miroslaw Truszczynski The Sixth International Conference on Principles of Knowledge Representation and Reasoning was held in June 2-5, 1998 in Trento, Italy. The environs of a beautiful old town surrounded by Dolomites made for an excellent conference site. The technical program of the conference consisted of three invited plenary talks, a panel that discussed main themes at the five co-located workshops, and 55 contributed presentations. Six of these presentations dealt with logic programming and its applications to knowledge representation. They were grouped into two technical sessions: Logic Programming-Based Representations I and II. I will briefly review these papers below. The three papers that were presented during the first of these two sessions were: A comparison of the static and the disjunctive well-founded semantics and its implementation by Stefan Brass, Juergen Dix, Ilkka Niemelä and Teodor Przymusinski, Preferred answer sets for extended logic programs by Gerhard Brewka and Thomas Eiter, and Dynamic Logic Programming by Jose Alferes, Joao Leite. Luis Pereira, Halina Przymusinska and Teodor Przymusinski. The second session was comprised of the remaining three papers: Specifying transactions for extended abduction by Katsumi Inoue and Chiaki Sakama, The KR system: progress report, comparisons and benchmarks by Thomas Eiter, Nicola Leone, Cristine Mateis, Gerald Pfeifer and Francesco Scarcello, and Disjunctive ordered logic: semantics and expressiveness by Francesco Buccafurri, Nicola Leone and Pasquale Rullo. The paper by Brass, Dix, Niemelä and Przymusinski compares two semantics proposed for the class of disjunctive logic programs: the static semantics by Przymusinski and the disjunctive well-founded semantics (D-WFS) by Brass and Dix. These semantics are based on very different ideas. The static semantics is obtained from the notion of the least static expansion of a translation of a program into the Autoepistemic Logic of Beliefs, while the D-WFS is defined as the least semantics invariant under some program transformations. The main result of the paper shows that, despite these differences, both semantics are closely related. Namely, a version of the static semantics defined for a modal language which does not allow for nested beliefs is shown to imply a semantics for disjunctive logic programs which coincides with D-WFS. The results of the paper also suggest a method to compute the D-WFS (and, hence, also a restricted static semantics) by means of a tableau method developed recently by Niemelä for circumscription. The paper Preferred answer sets for extended logic programs by Brewka and Eiter discusses problems with semantics for logic programs whose clauses are ordered to express preferences. Several proposals for the semantics of prioritized default theories were proposed in the literature but, arguably, none of them quite satisfactory. The novel element of the paper is that it presents two general principles on the preference relation between belief sets (answer sets in logic programming, extensions in default logic) that should be satisfied by any system based on prioritized defeasible rules. The authors then argue that the failure of previous approaches can be explained by each of them violating at least one of the two principles described in the paper. The authors follow this up by introducing their own generalization of the answer set semantics for extended logic programs to the case with priorities. They show that their notion of a preferred answer set satisfies the two principles they introduced earlier. There are prioritized logic programs that do not have preferred answer sets in the sense of the paper. Thus, the authors go on to define a weaker version of the notion of a preferred answer set, a weakly preferred answer set. Every program has a weakly preferred answer set. However, if preferred answer sets exist, weakly preferred answer sets and preferred answer sets coincide. The paper is concluded by a detailed analysis of computational complexity of problems related to the existence of preferred answer sets of prioritized programs. The paper leaves us with an interesting question of deciding whether the set of principles for the preference among belief sets is in any sense complete. The third paper in the first session, Dynamic logic programming by Alferes, Leite, Pereira, Przymusinska and Przymusinski deals with the problem of knowledge base updates. In the approach used in the paper, both the knowledge base and the updates to be enforced are represented by a generalized logic program, that is, a logic program which allows literals of the form not L in the heads of clauses. This class of programs and some of its generalizations were first introduced by Lifschitz and Woo. The Dynamic logic programming paper shows how to update a generalized logic program P by another generalized logic program U and obtain, as a result, an updated generalized logic program oplus. In the most original contribution of the paper the authors demonstrate that in order to properly capture updates, the principle of inertia} should be applied not just to individual literals but to entire clauses of the program representing the knowledge base being updated. The authors demonstrate how earlier approaches to knowledge base updates, in particular, revision programming by Marek and Truszczynski, can be viewed as a special case of program updates. The authors conclude their paper by discussing dynamic program updates, the concept that applies in any situation when several different logic programs (modules) represent knowledge states at different times or under different priorities. Consequently, different modules may contain contradictory or superfluous information. The dynamic program update, a generalization of the program update, provides declarative and procedural semantics of the collection of all the modules. Inoue and Sakama, in their paper Specifying transactions for extended abduction, consider an abductive system in which the background knowledge is specified as a nonmonotonic theory, specifically, a normal logic program (possibly with integrity constraints). This concept, extended abduction}, was introduced by Inoue and Sakama in their IJCAI-95 paper. It is based on one of the most basic properties of nonmonotonic reasoning systems - the set of conclusions grows when new facts are added but also, and this is the key insight behind the extended abduction, it may grow when some facts are deleted. The main contribution of the present paper is an algorithmic method to compute minimal explanations under the concept of extended abduction. The method consists of translating an abductive logic program into a transaction program. A transaction program is a collection of disjunctive production rules that provide a declarative specification of which abducibles must be "in'' and which abducibles must be "out'' in order to explain an observation. The authors define a fixpoint operator for transaction programs. They then show that if the initial abductive logic program is acyclic, the least fixpoint of this fixpoint operator represents all minimal explanations of an observation. The paper also contains an extensive discussion of other related work on abduction and database updates. The paper The KR system : progress report, comparisons and benchmarks} by Eiter, Leone, Mateis, Pfeifer and Scarcello describes a knowledge representation system {\tt dlv}, under development at the Technical University of Vienna. The system supports knowledge bases expressed as function-free disjunctive logic programs extended by integrity constraints and true negation. The system allows for querying knowledge bases and supports both brave and cautious reasoning. The system is one of the most advanced implementations of nonmonotonic reasoning systems to date. The bulk of the paper consists of a systematic comparison of the system with two other available systems for nonmonotonic reasoning: DeReS, developed at the University of Kentucky, and smodels, developed at the Technical University of Helsinki. For this comparative study, problems were encoded as disjunctive logic programs for use with or logic programs for use with smodels or DeReS (neither smodels nor DeReS support disjunctive clauses). The experiments reported in the paper show the promise of the - in many cases its performance was comparable to or only slightly slower than this of smodels or DeReS (even when DeReS was able to take advantage of relaxed stratification of some of the theories). In the paper Disjunctive ordered logic: semantics and expressiveness, Buccafurri, Leone and Rullo describe a new knowledge representation formalism. Disjunctive ordered logic or DOL, can be viewed as an extension of disjunctive DATALOG with negation by allowing negation in the heads of clauses, modularization (clauses can be grouped into modules), and inheritance (modules can be ordered by a partial ordering relation). The paper defines a semantics of disjunctive ordered logic programs. Expressive power of the new formalism (and its specializations) is thoroughly investigated as is its computational complexity. The main point made by the authors is that adding inheritance and true negation to the formalism of disjunctive DATALOG with negation does not increase the computational complexity of the system but makes it easier to use in modeling practical applications. Overall, in my opinion, the KR-98 conference was a big success. The co-located workshops and conferences helped boost the attendance and were very interesting themselves. The technical program of KR-98 was of high quality. And, most importantly, logic programming papers presented at KR-98 provided convincing evidence that the field of logic programming significantly contributes to the area of knowledge representation. Department of Computer Science University of Kentucky Lexington, KY 40506-0046 mirek@cs.engr.uky.edu

Logic Programming at KR'98

Miroslaw Truszczynski

The Sixth International Conference on Principles of Knowledge Representation and Reasoning was held in June 2-5, 1998 in Trento, Italy. The environs of a beautiful old town surrounded by Dolomites made for an excellent conference site.

The technical program of the conference consisted of three invited plenary talks, a panel that discussed main themes at the five co-located workshops, and 55 contributed presentations. Six of these presentations dealt with logic programming and its applications to knowledge representation. They were grouped into two technical sessions: Logic Programming-Based Representations I and II. I will briefly review these papers below.

The three papers that were presented during the first of these two sessions were: A comparison of the static and the disjunctive well-founded semantics and its implementation by Stefan Brass, Juergen Dix, Ilkka Niemelä and Teodor Przymusinski, Preferred answer sets for extended logic programs by Gerhard Brewka and Thomas Eiter, and Dynamic Logic Programming by Jose Alferes, Joao Leite. Luis Pereira, Halina Przymusinska and Teodor Przymusinski. The second session was comprised of the remaining three papers: Specifying transactions for extended abduction by Katsumi Inoue and Chiaki Sakama, The KR system: progress report, comparisons and benchmarks by Thomas Eiter, Nicola Leone, Cristine Mateis, Gerald Pfeifer and Francesco Scarcello, and Disjunctive ordered logic: semantics and expressiveness by Francesco Buccafurri, Nicola Leone and Pasquale Rullo.

The paper by Brass, Dix, Niemelä and Przymusinski compares two semantics proposed for the class of disjunctive logic programs: the static semantics by Przymusinski and the disjunctive well-founded semantics (D-WFS) by Brass and Dix. These semantics are based on very different ideas. The static semantics is obtained from the notion of the least static expansion of a translation of a program into the Autoepistemic Logic of Beliefs, while the D-WFS is defined as the least semantics invariant under some program transformations. The main result of the paper shows that, despite these differences, both semantics are closely related. Namely, a version of the static semantics defined for a modal language which does not allow for nested beliefs is shown to imply a semantics for disjunctive logic programs which coincides with D-WFS. The results of the paper also suggest a method to compute the D-WFS (and, hence, also a restricted static semantics) by means of a tableau method developed recently by Niemelä for circumscription.

The paper Preferred answer sets for extended logic programs by Brewka and Eiter discusses problems with semantics for logic programs whose clauses are ordered to express preferences. Several proposals for the semantics of prioritized default theories were proposed in the literature but, arguably, none of them quite satisfactory. The novel element of the paper is that it presents two general principles on the preference relation between belief sets (answer sets in logic programming, extensions in default logic) that should be satisfied by any system based on prioritized defeasible rules. The authors then argue that the failure of previous approaches can be explained by each of them violating at least one of the two principles described in the paper. The authors follow this up by introducing their own generalization of the answer set semantics for extended logic programs to the case with priorities. They show that their notion of a preferred answer set satisfies the two principles they introduced earlier. There are prioritized logic programs that do not have preferred answer sets in the sense of the paper. Thus, the authors go on to define a weaker version of the notion of a preferred answer set, a weakly preferred answer set. Every program has a weakly preferred answer set. However, if preferred answer sets exist, weakly preferred answer sets and preferred answer sets coincide. The paper is concluded by a detailed analysis of computational complexity of problems related to the existence of preferred answer sets of prioritized programs. The paper leaves us with an interesting question of deciding whether the set of principles for the preference among belief sets is in any sense complete.

The third paper in the first session, Dynamic logic programming by Alferes, Leite, Pereira, Przymusinska and Przymusinski deals with the problem of knowledge base updates. In the approach used in the paper, both the knowledge base and the updates to be enforced are represented by a generalized logic program, that is, a logic program which allows literals of the form not L in the heads of clauses. This class of programs and some of its generalizations were first introduced by Lifschitz and Woo. The Dynamic logic programming paper shows how to update a generalized logic program P by another generalized logic program U and obtain, as a result, an updated generalized logic program oplus. In the most original contribution of the paper the authors demonstrate that in order to properly capture updates, the principle of inertia} should be applied not just to individual literals but to entire clauses of the program representing the knowledge base being updated. The authors demonstrate how earlier approaches to knowledge base updates, in particular, revision programming by Marek and Truszczynski, can be viewed as a special case of program updates. The authors conclude their paper by discussing dynamic program updates, the concept that applies in any situation when several different logic programs (modules) represent knowledge states at different times or under different priorities. Consequently, different modules may contain contradictory or superfluous information. The dynamic program update, a generalization of the program update, provides declarative and procedural semantics of the collection of all the modules.

Inoue and Sakama, in their paper Specifying transactions for extended abduction, consider an abductive system in which the background knowledge is specified as a nonmonotonic theory, specifically, a normal logic program (possibly with integrity constraints). This concept, extended abduction}, was introduced by Inoue and Sakama in their IJCAI-95 paper. It is based on one of the most basic properties of nonmonotonic reasoning systems - the set of conclusions grows when new facts are added but also, and this is the key insight behind the extended abduction, it may grow when some facts are deleted. The main contribution of the present paper is an algorithmic method to compute minimal explanations under the concept of extended abduction. The method consists of translating an abductive logic program into a transaction program. A transaction program is a collection of disjunctive production rules that provide a declarative specification of which abducibles must be "in'' and which abducibles must be "out'' in order to explain an observation. The authors define a fixpoint operator for transaction programs. They then show that if the initial abductive logic program is acyclic, the least fixpoint of this fixpoint operator represents all minimal explanations of an observation. The paper also contains an extensive discussion of other related work on abduction and database updates.

The paper The KR system : progress report, comparisons and benchmarks} by Eiter, Leone, Mateis, Pfeifer and Scarcello describes a knowledge representation system {\tt dlv}, under development at the Technical University of Vienna. The system supports knowledge bases expressed as function-free disjunctive logic programs extended by integrity constraints and true negation. The system allows for querying knowledge bases and supports both brave and cautious reasoning. The system is one of the most advanced implementations of nonmonotonic reasoning systems to date. The bulk of the paper consists of a systematic comparison of the system with two other available systems for nonmonotonic reasoning: DeReS, developed at the University of Kentucky, and smodels, developed at the Technical University of Helsinki. For this comparative study, problems were encoded as disjunctive logic programs for use with or logic programs for use with smodels or DeReS (neither smodels nor DeReS support disjunctive clauses). The experiments reported in the paper show the promise of the - in many cases its performance was comparable to or only slightly slower than this of smodels or DeReS (even when DeReS was able to take advantage of relaxed stratification of some of the theories).

In the paper Disjunctive ordered logic: semantics and expressiveness, Buccafurri, Leone and Rullo describe a new knowledge representation formalism. Disjunctive ordered logic or DOL, can be viewed as an extension of disjunctive DATALOG with negation by allowing negation in the heads of clauses, modularization (clauses can be grouped into modules), and inheritance (modules can be ordered by a partial ordering relation). The paper defines a semantics of disjunctive ordered logic programs. Expressive power of the new formalism (and its specializations) is thoroughly investigated as is its computational complexity. The main point made by the authors is that adding inheritance and true negation to the formalism of disjunctive DATALOG with negation does not increase the computational complexity of the system but makes it easier to use in modeling practical applications.

Overall, in my opinion, the KR-98 conference was a big success. The co-located workshops and conferences helped boost the attendance and were very interesting themselves. The technical program of KR-98 was of high quality. And, most importantly, logic programming papers presented at KR-98 provided convincing evidence that the field of logic programming significantly contributes to the area of knowledge representation.

Department of Computer Science

University of Kentucky
Lexington, KY 40506-0046
mirek@cs.engr.uky.edu