next up previous
Next: References Up: Well-Founded Semantics for Extended Previous: Relation to Answer

Related Work and Conclusions

Several approaches treating preferences in the context of logic programming have been described in the literature. We will now discuss how they relate to our proposal.

Kowalski and Sadri (1991) proposed to consider rules with negation in the head as exceptions to more general rules and to give them higher priority. Technically, this is achieved by a redefinition of answer sets. It turns out that the original answer sets remain answer sets according to the new definition whenever they are consistent. The main achievement is that programs whose single answer set is inconsistent become consistent in the new semantics. The approach can hardly be viewed as a satisfactory treatment of preferences for several reasons:

  1. preferences are implicit and highly restricted; the asymmetric treatment of positive and negative information seems unjustified,
  2. it is difficult to see how, for instance, exceptions of exceptions can be represented,
  3. fewer conclusions are obtained than in the original answer set semantics, contrary to what one would expect when preferences are taken into account.
It is, therefore, more reasonable to view Kowalski and Sadri's approach as a contribution to inconsistency handling rather than preference handling.

An approach that is closer in spirit to ours is ordered logic programming [5]. An ordered logic program is a set of components forming an inheritance hierarchy. Each component consists of a set of rules. The inheritance hierarchy is used to settle conflicts among rules: rules lower in the hierarchy have preference over those higher up in the hierarchy since the former are considered more specific. A notion of a stable model for ordered logic programs can be defined (see Buccafurri et al., 1996, for the details).

There are two main differences between ordered logic programs and our extension of well-founded semantics:

  1. ordered logic programs use only one kind of negation, the distinction between negation as failure and classical negation is not expressible in the language,
  2. the preferences of ordered logic programs are predefined through the inheritance hierarchy, there is no way of deriving context-dependent preferences dynamically.

Finally we would like to mention an approach recently presented by Prakken and Sartor (1995). They extend Dung's argument system style reconstruction of logic programming [DungDung1993] with a preference handling method that is very close to ours. This is not astonishing since, as the authors point out, their approach is based on ``unpublished ideas of Gerhard Brewka''. In fact, it was a preliminary version of this paper that led to their formulation.

We presented in this paper an extension of logic programs with two types of negation where preference information among rules can be expressed in the logical language. This extension is very useful for practical applications, as was demonstrated using an example from legal reasoning. The main advantage of our approach is that also this type of information is context-dependent and can be reasoned upon and derived dynamically.

From well-founded semantics we inherit some drawbacks and advantages. Sometimes reasonable conclusions are not obtained. On the other hand, the addition of preference information can make the set of conclusions considerably larger, as we have shown. Moreover, - and this certainly is the greatest advantage of well-founded semantics and our proposed extension - reasoning can be done in polynomial time.

The simple and natural representation of the legal example discussed in Sect. 4 seems to indicate that our generalization of well-founded semantics may provide a new attractive compromise between expressiveness and efficiency with a number of interesting potential applications.

I would like to thank Franz Baader, Jürgen Dix, Tom Gordon, Henry Prakken, Cees Witteveen, and two anonymous referees for interesting comments helping to improve the quality of this paper.

next up previous
Next: References Up: Well-Founded Semantics for Extended Previous: Relation to Answer

Gerd Brewka
Thu Feb 8 10:26:15 MET 1996