next up previous
Next: Related Work and Up: Well-Founded Semantics for Extended Previous: Complexity

Relation to Answer Sets

In this section we will investigate the relation of our modification of well-founded semantics to answer set semantics [8]. Since our approach handles an extended language in which certain symbols are given a particular pre-defined meaning a thorough investigation of this relationship is only possible after a corresponding extension of answer set semantics to prioritized logic programs has been defined. We are not planning to introduce and defend such an extension in this paper. Nevertheless, we can give some preliminary results here. More precisely, we will show that the conclusions produced in our proposal are correct wrt. a particular subclass of answer sets, the so-called priority-preserving answer sets.

The intuition behind the definition is the following: whenever a rule r is rebutted in an answer set A but its rebuttal is solely based on rules dominated by r with respect to A and the rules not defeated by A we consider this as a violation of the available preference information and ``reject'' the answer set.

We can now show correctness of our approach wrt. priority preserving answer sets.

Proof: The proof is similar to the correctness proof of wrt. answer set semantics (Proposition 2). Again the proposition is trivially satisfied whenever there is no priority preserving answer set, or Lit is the single priority preserving answer set. We may therefore assume that every priority preserving answer set of R is consistent.

In the inductive step we show that for an arbitrary priority preserving answer set A a rule r is not defeated in A whenever , given that X is a set of literals true in A. From this it follows that contains only literals true in all priority preserving answer sets.

Let be defined as in Def. 6 (the inductive definition of X-safeness) and assume it is already known that the rules in are not defeated in A. By definition iff r is not defeated by . We distinguish two cases:

Case 1: : Since and Dom is monotonic in both indices we have . Therefore r cannot be defeated in A since A is priority preserving.

Case 2: : Since the prerequisites of r cannot be derived from the set contains only rules defeated by alone. Since A is an answer set these rules can't be contained in . Therefore and thus . Since by assumption A is consistent we also have and therefore r cannot be defeated in A. We have seen that our approach is guaranteed to produce only conclusions contained in all priority preserving answer sets. We can also ask the opposite question: given a particular answer set A, is it always possible to obtain A (or, more precisely, a superset of A containing additional preference information) through prioritized well-founded semantics by adding adequate preference information?

The answer to this question is no. The reason is that for sake of tractability we always consider single rules when determining X-safeness in our approach. Here is an example:

This program has two answer sets and . Consider . Even if we add the preference information that both and are preferred to each of and we are unable to derive b and d. For instance, is not X-safe because its head does not defeat .

In order to derive it would be necessary to take the possibility of sets of rules (here and ) defeating less preferred sets of rules (here and ) into account. Although this is possible in principle it would clearly lead to intractability since in the worst case an exponential number of subsets of rules would have to be checked. Giving up tractability seems too high a price for what is gained and we stick to our more cautious approach for this reason.

next up previous
Next: Related Work and Up: Well-Founded Semantics for Extended Previous: Complexity

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