A Comparative Study of Logic Programs with Preference

1 Introduction

Numerous approaches to logic programming with preference information have been proposed in the literature. So far, however, there is no systematic account on their structural differences, finally leading to solid semantical underpinnings. We address this shortcoming by a comparative study of a distinguished class of approaches to preference handling. This class consists of selective approaches remaining within the complexity class of extended logic programming (under answer sets semantics). These approaches are selective insofar as they use preferences to distinguish certain "models" of the original program.

We explore three different approaches that have been recently proposed in the literature, namely the ones in [Brewka and Eiter, 1999; Delgrande et al., 2000; Wang et al., 2000]. Our investigation adopts characterization techniques found in the same literature in order to shed light on the relationships among these approaches. This provides us with different characterizations in terms of (i) fixpoints, (ii) order preservation, and (iii) translations into standard logic programs. While the two former provide semantics for logic programming with preference information, the latter furnishes implementation techniques for these approaches. From another perspective, one can view (iii) as an axiomatization of the underlying strategy within the object language, while (i) may be regarded as a meta-level description of the corresponding construction process. One may view (ii) as the most semantical characterization because it tells us which "models" of the original program are selected by the respective preference handling strategy.

∗ Affiliated with the School of Computing Science at Simon Fraser University, Burnaby, Canada.

We limit (also in view of (iii)) our investigation to approaches to preference handling that remain within NP. This excludes approach like the ones in [Rintanen, 1995; Zhang and Foo, 1997] that step outside the complexity class of the underlying reasoning method. This applies also to the approach in [Sakama and Inoue, 1996], where preferences on literals are investigated. While the approach of [Gelfond and Son, 1997] remains within NP, it advocates strategies that are non-selective. Approaches that can be addressed within this framework include [Baader and Hollunder, 1993; Brewka, 1994] that were originally proposed for default logic.

2 Definitions and notation

We assume a basic familiarity with logic programming under answer set semantics [Gelfond and Lifschitz, 1991]. An extended logic program is a finite set of rules of the form

where n ≥ m ≥ 0, and each Li (0 ≤ i ≤ n) is a literal, ie. either an atom A or its negation ¬A. The set of all literals is denoted by Lit. Given a rule r as in (1), we let head(r) denote the head, L0, of r and body(r) the body, {L1, . . . ,Lm, not Lm+1, . . . , not Ln}, of r. Further, let body +(r) = {L1, , . . . ,Lm} and body -(r) = {Lm+1, . . . ,Ln}. A program is called basic if body -(r) = ∅ for all its rules.

We define the reduct of a rule r as r+ = head(r) ← body +(r). The reduct, ΠX , of a program Π relative to a set X of literals is defined by

A set of literals X is closed under a basic program Π iff for any r ∈ Π, head(r) ∈ X whenever body +(r) ⊆ X. We say that X is logically closed iff it is either consistent (ie. it does not contain both a literal A and its negation ¬A) or equals Lit . The smallest set of literals which is both logically closed and closed under a basic program Π is denoted by Cn(Π).

Finally, a set X of literals is an answer set of a program Π iff Cn(ΠX ) = X. In what follows, we deal with consistent answer sets only.

The set ΓXΠ of all generating rules of an answer set X from Π is given by

As van Gelder in [1993], we define CΠ(X) = Cn(ΠX ). Note that the operator CΠ is anti-monotonic, which implies that the operator AΠ(X) = CΠ(CΠ(X)) is monotonic. A fixpoint of AΠ is called an alternating fixpoint for Π. Different semantics are captured by distinguishing different groups of fixpoints of AΠ.

A (statically) ordered logic program 1 is a pair (Π,<), where Π is an extended logic program and < ⊆ Π×Π is an irreflexive and transitive relation. Given, r1, r2 ∈ Π, the relation r1 < r2 expresses that r2 has higher priority than r1. 2

3 Preferred alternating fixpoints

The notion of answer sets (without preference) is based on a reduction of extended logic programs to basic programs (without default negation). Such a reduction is inapplicable when addressing conflicts by means of preference information since all conflicts between rules are simultaneously resolved when turning Π into ΠX . Rather conflict resolution must be characterized among the original rules in order to account for blockage between rules. That is, once the negative body body -(r) is eliminated there is no way to detect whether head(r′ ) ∈ body -(r) holds in case of r < r′ .

Such an approach is pursued in [Wang et al., 2000] for characterizing "preferred" answer sets. Following earlier approaches based on default logic [Baader and Hollunder, 1993; Brewka, 1994], this approach is based on the concept of activeness: Let X, Y ⊆ Lit be two sets of literals in an ordered logic program (Π,<). A rule r in Π is active wrt the pair (X, Y ), if body +(r) ⊆ X and body -(r) ∩ Y = ∅.

Definition 1 (Wang et al.,2000) Let (Π,<) be an ordered logic program and let X be a set of literals. We define

X0 = ∅ and for i ≥ 0 Xi+1 = Xi ∪ {head(r) | I . r ∈ Π is active wrt (Xi,X) and II . there is no rule r′ ∈ Π with r < r′ such that (a) r′ is active wrt (X,Xi) and (b) head(r′ ) ̸∈ Xi ⎫⎪⎪⎪⎬⎪⎪⎪⎭

The idea is to apply a rule r only if the question of application has been settled for all higher-ranked rules r′ . That is, if either its prerequisites will never be derivable, viz. body +(r′ ) ̸⊆ X, or r′ is defeated by what has been derived so far, viz.

1 Also called prioritized logic program by some authors, as eg. in [Brewka and Eiter, 1999].

2 Some authors, among them [Brewka and Eiter, 1999], attribute relation < the inverse meaning.

body -(r) ∩Xi ̸= ∅, or r′ or another rule with the same head have already applied, viz. head(r′ ) ∈ Xi.

As its original CΠ, the operator C(Π,<) is anti-monotonic. Accordingly, we may define for any set X ⊆ Lit, the alternating transformation of (Π,<) as A(Π,<)(X) = C(Π,<)(C(Π,<)(X)). A fixpoint of A(Π,<) is called an alternating fixpoint of (Π,<). Note that A(Π,<) is monotonic.

Now, in analogy to Van Gelder [1993], a semantical framework for ordered logic programs in terms of sets of alternating fixpoints can be defined. Three different types of semantics are investigated in [Wang et al., 2000]: (i) Preferred 3 answer sets, viz. alternating fixpoints being also fixpoints of C(Π,<). (ii) Preferred regular extensions, viz. maximal normal 4 alternating fixpoints of (Π,<). (iii) Preferred well-founded model, viz. the least alternating fixpoint of (Π,<).

We put the prefix 'W-' whenever a distinction to other approaches is necessary.

For illustration, consider the following ordered logic program (Π2, <) due to [Baader and Hollunder, 1993]:

Observe that Π2 admits two answer sets: X = {p, b, ¬f, w} and X′ = {p, b, f, w}. As argued in [Baader and Hollunder, 1993], X is the unique W-preferred answer set. To see this, observe that

Note that w cannot be included into X′3 because r1 is active wrt (X′ ,X′2 ) and r1 is preferred to r2.

4 Compiling order preservation

A translation of ordered logic programs (Π,<) to standard ones Π′ is developed in [Delgrande et al., 2000]. The specific strategy used there ensures that the resulting program Π′ admits only those answer sets of the original program Π that are order preserving:

Definition 2 Let (Π, <) be a statically ordered program and let X be an answer set of Π.

Then, X is called <-preserving, if there exists an enumeration 〈ri〉i∈I of ΓXΠ such that for every i, j ∈ I we have that:

3 Originally called prioritized.

4 An alternating fixpoint X is normal if X ⊆ C(Π,<)(X).

Condition 0 makes the property of groundedness 5 explicit. Although any standard answer set is generated by a grounded sequence of rules, we will see in the sequel that this property is weakened when preferences are at issue. Condition 1 stipulates that 〈ri〉i∈I is compatible with <, a property invariant to all of the considered approaches. Lastly, Condition 2 is comparable with Condition II in Definition 1; it guarantees that rules can never be blocked by lower-ranked rules.

As above, X = {p, b, ¬f,w} is the only <-preserving answer set of Π2; it can be generated by the grounded sequences 〈r5, r4, r1, r2〉 and 〈r5, r1, r4, r2〉 both of which satisfy conditions 1 and 2. The only grounded sequence generating X′ = {p, b, f, w}, namely 〈r5, r4, r2, r3〉, violates 2b.

The corresponding translation integrates ordering information into the logic program via a special-purpose predicate symbol ≺. This allows also for treating ordering information in a dynamic fashion. A logic program over a propositional language L is said to be dynamically ordered iff L contains the following pairwise disjoint categories: (i) a set N of terms serving as names for rules; (ii) a set At of (propositional) atoms of a program; and (iii) a set At≺ of preference atoms s ≺ t, where s, t ∈ N are names. For each such program Π, we assume furthermore a bijective function n(·) assigning to each rule r ∈ Π a name n(r) ∈ N. To simplify notation, we usually write nr instead of n(r) (and we sometimes abbreviate nri by ni).

An atom nr ≺ nr′ ∈ At≺ amounts to asserting that r < r′ holds. A statically ordered program (Π,<) can thus be captured by programs containing preference atoms only among their facts; it is then expressed by the program Π ∪ {(nr ≺ nr′ ) ← | r < r′ }.

Given r < r′ , one wants to ensure that r′ is considered before r, in the sense that, for a given answer set X, rule r′ is known to be applied or defeated ahead of r (cf. Condition II or 2 above, respectively). This is done by translating rules so that the order of rule application can be explicitly controlled. For this purpose, one needs to be able to detect when a rule has been applied or when a rule is defeated. For a rule r, there are two cases for it not to be applied: it may be that some literal in body +(r) does not appear in the answer set, or it may be that a literal in body -(r) is in the answer set. For detecting non-applicability (i.e., blockage), for each rule r in the given programΠ, a new, special-purpose atom bl(nr) is introduced. Similarly, a special-purpose atom ap(nr) is introduced to detect the case where a rule has been applied. For controlling application of rule r the atom ok(nr) is introduced. Informally, one concludes that it is ok to apply a rule just if it is ok with respect to every <-greater rule; for such a <-greater rule r′ , this will be the case just when r′ is known to be blocked or applied.

More formally, given a dynamically ordered program Π over L, let L+ be the language obtained from L by adding, for each r, r′ ∈ Π, new pairwise distinct propositional atoms ap(nr), bl(nr), ok(nr), and ok′ (nr, nr′). Then, the translation T maps an ordered program Π over L into a standard program T (Π) over L+ in the following way.

5 This term is borrowed from the literature on default logic.

Definition 3 (Delgrande et al.,2000) Let Π = {r1, . . . , rk} be a dynamically ordered logic program over L.

Then, the logic program T (Π) over L+ is defined as T (Π) = ⋃r∈Πτ(r) , where τ(r) consists of the following rules, for L+ ∈ body +(r), L- ∈ body -(r), and r′ , r′′ ∈ Π :

We write T (Π, <) rather than T (Π′ ), whenever Π′ is the dynamically ordered program capturing (Π, <).

The first four rules of τ(r) express applicability and blocking conditions of the original rules. The second group of rules encodes the strategy for handling preferences. The first of these rules, c1(r), "quantifies" over the rules in Π. This is necessary when dealing with dynamic preferences since preferences may vary depending on the corresponding answer set. The three rules c2(r, r′ ), c3(r, r′ ), and c4(r, r′ ) specify the pairwise dependency of rules in view of the given preference ordering: For any pair of rules r, r′ with nr ≺ nr′ , we derive ok′ (nr, nr′) whenever nr ≺ nr′ fails to hold, or whenever either ap(nr′ ) or bl(nr′ ) is true. This allows us to derive ok(nr), indicating that r may potentially be applied whenever we have for all r′ with nr ≺ nr′ that r′ has been applied or cannot be applied. It is important to note that this is only one of many strategies for dealing with preferences: different strategies are obtainable by changing the specification of ok(·) and ok′ (·, ·), as we will see below.

As shown in [Delgrande et al., 2000], a set of literals X is a <-preserving answer set of Π iff X = Y ∩L for some answer set Y of T (Π,<). In the sequel, we refer to such answer sets as being D-preferred.

5 Synthesis

The last two sections have exposed three rather different ways of characterizing preferred answer sets. Despite their different characterizations, however, it turns out that the two approaches prefer similar answer sets.

5.1 Characterizing D-preference

We start by providing a fixpoint definition for D-preference. For this purpose, we assume a bijective mapping rule(·) from rule heads to rules, that is, rule(head(r)) = r; accordingly, rule({head(r) | r ∈ R}) = R. Such mappings can be defined in a bijective way by distinguishing different occurrences of literals.

Definition 4 Let (Π,<) be a statically ordered logic program and let X be a set of literals. We define

The difference between this definition and Definition 1 manifests itself in IIb. While D-preference requires that a higherranked rule has effectively applied, W-preference contents itself with the presence of the head of the rule, no matter whether this was supplied by the rule itself.

This difference is nicely illustrated by program (Π3, <):

While the only answer set {a, b} is W-preferred set, there is no D-preferred answer set. This is the same with program (Π′3 , <) obtained by replacing r1 with r′1 : a ← b.

We have the following result providing three alternative characterizations of D-preferred answer sets.

Theorem 1 Let (Π, <) be a statically ordered logic program over L and let X be a consistent set of literals.

Then, the following propositions are equivalent.

1. C D (Π,<) (X) = X;
2. X = Y ∩L for some answer set Y of T (Π,<);
3. X is a <-preserving answer set of Π.

While the last result dealt with effective answer sets, the next one shows that applying operator C D (Π,<) is equivalent to the application of vanGelder's operator CΠ′ to the translated program T (Π, <) .

Theorem 2 Let (Π, <) be a statically ordered logic program over L and let X be a consistent set of literals over L.

Then, we have that C D (Π,<) (X) = CT (Π,<)(Y )∩L for some set of literals Y over L+ such that X = Y ∩ L.

This result is important because it allows us to use the translation T (Π, <) for implementing further semantics by appeal to the alternating fixpoint idea.

5.2 Characterizing W-preference

We start by showing how W-preference can be characterized in terms of order preservation.

Definition 5 Let (Π, <) be a statically ordered program and let X be an answer set of Π.

Then, X is called <W -preserving, if there exists an enumeration 〈ri〉i∈I of ΓXΠ such that for every i, j ∈ I we have that:

1. (a) body +(ri) ⊆ {head(rj) | j < i} or
2. (c) head(r′ ) ∈ {head(rj) | j < i}.

(b) head(ri) ∈ {head(rj) | j < i}; and 1. if ri < rj, then j < i; and 2. if ri < r′ and r′ ∈ Π \ ΓXΠ , then (a) body +(r′ ) ̸⊆X or (b) body -(r′ ) ∩ {head(rj) | j < i} ̸= ∅ or

The primary difference of this concept of order preservation to the original one is clearly the weaker notion of groundedness. This involves the rules in ΓXΠ (via Condition 0b) as well as those in Π \ ΓXΠ (via Condition 2c). The rest of the definition is the same as in Definition 2. For instance, answer set {a, b} of Π3 is generated by the <W -preserving rule sequence 〈r3, r2〉. Note that r1 satisfies 2c but neither 2a nor 2b. For a complement, in (Π′3 ,<), r′1 is dealt with via Condition 0b.

Interestingly, this weaker notion of groundedness can be easily integrated into the translation given in the last section.

Definition 6 Given the same prerequisites as in Definition 3. Then, the logic program T W (Π) over L+ is defined as T W (Π) = ⋃r∈Πτ(r) ∪ {c5(r, r′ ) | r, r′ ∈ Π}, where

The purpose of c5(r, r′ ) is to eliminate rules from the preference handling process once their head has been derived.

We have the following result, showing in particular, how W-preference is implementable via off-the-shelf logic programming systems.

Theorem 3 Let (Π, <) be a statically ordered logic program over L and let X be a consistent set of literals. Then, the following propositions are equivalent.

1. C(Π,<)(X) =X;
2. X = Y ∩L for some answer set Y of T W (Π,<);
3. X is a <W -preserving answer set of Π.

In analogy to what we have shown above, we have the following stronger result, opening the avenue for implementing more semantics based on W-preference:.

Theorem 4 Let (Π, <) be a statically ordered logic program over L and let X be a consistent set of literals over L.

Then, we have that C(Π,<)(X) = CT W (Π,<)(Y ) ∩ L for some set of literals Y over L+ such that X = Y ∩ L.

6 Brewka and Eiter's concept of preference

Another approach to preference was proposed by Brewka and Eiter in [1999]. For brevity, we omit technical details and simply say that an answer set is B-preferred; the reader is referred to [Brewka and Eiter, 1999; 2000] for details.

This approach differs in two significant ways from the two approaches given above. First, the construction of answer sets is separated from verifying whether they respect the given preferences. Interestingly, this verification is done on the basis of the prerequisite-free program obtained from the original one by "evaluating" body +(r) for each rule r wrt the separately constructed (standard) answer set. Second, rules that putatively lead to counter-intuitive results are removed from the inference process. This is made explicit in [Brewka and Eiter, 2000], where the following filtering transformation is defined: 6

Then, by definition, an answer set of Π is B-preferred iff it is a B-preferred answer set of ZX(Π).

The distinguishing example of this approach is given by program (Π5, <):

Program Π5 has two standard answer sets, {a, b} and {a, ¬b}. While the former is B-preferred, neither of them is W- or Dpreferred (see below). Also, we note that both answer sets of program (Π2, <) are B-preferred, while only {p, b, ¬f, w} is W- and D-preferred.

In order to shed some light on these differences, we start by providing a fixpoint characterization of B-preference:

Definition 7 Let (Π, <) be an ordered logic program and let X be a set of literals. We define

The difference between this definition 7 and its predecessors manifests itself in Condition I, where activeness is tested wrt (X,X) instead of (Xi,X) as in Definition 1 and 4. In fact, in Example (5) it is the (unprovability of the) prerequisite a of the highest-ranked rule r1 that makes the construction of W- or D-preferred answer sets break down (cf. Definition 1 and 4). This is avoided with B-preference because once answer set {a, b} is provided, its preference-compatibility is tested wrt the program obtained by replacing r1 with b ← not ¬b.

B-preference can be captured by means of the following notion of order preservation:

Definition 8 Let (Π, <) be a statically ordered program and let X be an answer set of Π.

Then, X is called <B -preserving, if there exists an enumeration 〈ri〉i∈I of ΓXΠ such that, for every i, j ∈ I, we have that:

6 While this is integrated into [Brewka and Eiter, 1999, Def. 4.4], it is made explicit in [Brewka and Eiter, 2000, Def. 6].

7 We have refrained from integrating (4) in order to keep the fixpoint operator comparable to those given in the previous sections. This is taken care of in the second proposition of Theorem 5.

1. if ri < r′ and r′ ∈ Π \ ΓXΠ , then
2. (a) body +(r′ ) ̸⊆X or
3. (b) body -(r′ ) ∩ {head(rj) | j < i} ̸= ∅ or
4. (c) head(r′ ) ∈ X.

This definition differs in two ways from its predecessors. First, it drops any requirement on groundedness, expressed by Condition 0 above. This corresponds to using (X, X) instead of (Xi,X) in Definition 7. Hence, groundedness is fully disconnected from order preservation. In fact, observe that the B-preferred answer set {a, b} of (Π5,<) is associated with the <B -preserving sequence 〈r1, r2〉, while the standard answer set itself is generated by the grounded sequence 〈r2, r1〉.

Second, Condition 2c is more relaxed than in Definition 5. That is, any rule r′ whose head is in X (as opposed to Xi) is taken as "applied". Apart from this, Condition 2c also integrates the filter-conditions from (4). 8 For illustration, consider Example (3) extended by r3 < r2:

While this program has no D- or W-preferred answer set, it has a B-preferred one: {a, b} generated by 〈r2, r3〉. The critical rule r1 is handled by 2c. As a net result, Condition 2 is weaker than its counterpart in Definition 5.

We have the following results.

Theorem 5 Let (Π, <) be a statically ordered logic program over L and let X be a consistent answer set of Π. Then, the following propositions are equivalent.

1. X is B-preferred;
2. C B (ZX(Π),<) (X) = X;
3. X = Y ∩L for some answer set Y of T B (Π,<) (where T B is defined in [Delgrande et al., 2000]);
4. X is a <B -preserving answer set of Π.

Unlike theorems 1 and 3, the last result stipulates that X must be an answer set of Π. This requirement can only be dropped in case 3, while all other cases rely on this property.

7 Relationships

Up to now, we have tried to clarify the structural differences between the respective approaches. This has led to homogeneous characterizations that allow us to compare the examined approaches in a uniform way. As a result, we obtain insights into the relationships among these approaches.

First of all, we observe that all three approaches treat the blockage of (higher-ranked) rules in the same way. That is, a rule r′ is found to be blocked if either its prerequisites in body +(r′ ) are never derivable or if some member of body -(r′ ) has been derived by higher-ranked or unrelated rules. This is reflected by the identity of conditions IIa and 2a/b in all three approaches, respectively. Although this is arguably a sensible strategy, it leads to the loss of preferred answer sets on programs like

8 Condition body -(r′ ) ∩ X ̸= ∅ in (4) is obsolete since r′ ̸∈ ΓXΠ .

r1 : a ← not b r2 : b ← . r2 < r1

Let us now discuss the differences among the approaches. The difference between D- and W-preference can be directly read off Definition 1 and 4; it manifests itself in Condition IIb and leads to the following relationship.

Theorem 6 Every D-preferred answer set is W-preferred.

Example (3) shows that the converse does not hold.

Interestingly, a similar relationship is obtained between Wand B-preference. In fact, Definition 8 can be interpreted as a weakening of Definition 5 by dropping Condition 0 and weakening Condition 2 (via 2c). We thus obtain the following result.

Theorem 7 Every W-preferred answer set is B-preferred.

Example (5) shows that the converse does not hold.

We obtain the following summarizing result by letting AS(Π) = {X | CΠ(X) = X} and ASP (Π,<) = {X ∈ AS(Π) | X is P-preferred} for P = W, D, B.

Theorem 8 Let (Π, <) be a statically ordered logic program. Then, we have:

In principle, this hierarchy is induced by a decreasing interaction between groundedness and preference. While Dpreference requires the full compatibility of both concepts, this interaction is already weakened in W-preference, before it is fully abandoned in B-preference. This is nicely reflected by the evolution of Condition 0 in definitions 2, 5, and 8.

Notably, groundedness as such is not the ultimate distinguishing factor, as demonstrated by the fact that prerequisitefree programs do not necessarily lead to the same preferred answer sets, as witnessed in (3) and (6). Rather it is the degree of interaction between groundedness and preferences that makes the difference.

8 Conclusion

The notion of preference seems to be pervasive in logic programming when it comes to knowledge representation. This is reflected by numerous approaches that aim at enhancing logic programming with preferences in order to improve knowledge representation capacities. Despite the large variety of approaches, however, only very little attention has been paid to their structural differences and sameness, finally leading to solid semantical underpinnings.

This work is a first step towards a systematic account to logic programming with preferences. We elaborated upon three different approaches that were originally defined in rather heterogenous ways. We obtained three alternative yet uniform ways of characterizing preferred answer sets (in terms of fixpoints, order preservation, and an axiomatic account). The underlying uniformity provided us with a deeper understanding of how and which answer sets are preferred in each approach. This has led to a clarification of their relationships and subtle differences. In particular, we revealed that the investigated approaches yield an increasing number of answer sets depending on how tight they connect preference to groundedness.

An interesting technical result of this paper is given by the equivalences between the fixpoint operators and the standard logic programming operators applied to the correspondingly transformed programs (cf. Theorem 2 and 4). This opens the avenue for further concepts of preference handling on the basis of the alternating fixpoint theory and its issuing semantics. Further research includes dynamic preferences and more efficient algorithms for different semantics in a unifying way.

Acknowledgements. This workwas supported byDFGunder grant FOR 375/1-1, TP C.