Strong Equivalence for Logic Programs with Preferences

1 Introduction

During the last decade, Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988] has become an increasingly acknowledged tool for knowledge representation and reasoning. A main advantage of ASP is that it is based on solid theoretical foundations, while being able to model commonsense reasoning in an arguably satisfactory way. The availability of ef�cient solvers has furthermore stimulated its use in practical applications in recent years. This development had quite some implications on ASP research. For example, increasingly large applications require features for modular programming. Another requirement is the fact that in applications, ASP code is often generated automatically by so-called frontends, calling for optimization methods which remove redundancies, as also found in database query optimizers. For these purposes the rather recently suggested notion of strong equivalence for ASP [Lifschitz et al., 2001; Turner, 2003] can be used. Indeed, if two ASP programs are strongly equivalent, they can be used interchangeably in

∗The �rst author was partially supported by the EC under project IST-2002-33570 (INFOMIX). The second author was partially supported by the German Science Foundation (DFG) under grant SCHA 550/6-4, TP C. Both authors were partially supported by the EC under project IST-2001-37004WASP.

† Funded by APART of the Austrian Academy of Sciences.

Kathrin Konczak

PF 900327, D-14439 Potsdam, Germany

Institut f¤ur Informatik Universit¤at Potsdam

Email: konczak@cs.uni-potsdam.de

any context. This gives a handle on showing the equivalence of ASP modules. If a program is strongly equivalent to a subprogram of itself, then one can always use the subprogram instead of the original program, a technique which serves as an effective optimization method.

On a different line of ASP research, many extensions of the basic formalism have been proposed. Perhaps the most intensively studied one is the modeling of preferences in ASP, cf. [Delgrande et al., 2004]. Strongly rooted in the research of nonmonotonic formalisms, the ability to specify preferences is acknowledged to be particularly bene�cial to ASP, since they constitute a very natural and effective way of resolving indeterminate solutions. For example, preferences have been successfully used for timetabling, auctioning, con�guration, and other domains. A sophisticated application for information site selection has been described in [Eiter et al., 2002]. The emergence of such applications thus also calls for optimization methods, as for standard ASP.

In this paper we tackle this issue and generalize the notion of strong equivalence to ASP with preferences. Since a plethora of formalisms and semantics has been introduced for extending ASP by preferences, we have to limit ourselves in this paper to a few concrete approaches. A basic classi�cation of preference handling is (i) over which elements the preference is de�ned and (ii) the way how preferences are interpreted, and in particular how they are aggregated. In this work we focus on ordered programs, where preferences are de�ned among rules, which semantically act as �lters over answer sets. In particular, we consider the three semantics de�ned in [Delgrande et al., 2003; Wang et al., 2000; Brewka and Eiter, 1999], referred to as D-, W-, and Bsemantics, respectively. The reason for this choice is that these semantics seem to be widely accepted and their properties and interrelationships are fairly well-understood.

The contributions of this work are as follows. We de�ne the notion of strong equivalence for ordered programs. It turns out that the de�nition for standard ASP cannot be straightforwardly extended for two main reasons: (1) the �union� of ordered programs needs to be de�ned properly, and (2) not any �union� of ordered programs yields a valid ordered program. To overcome these problems, we de�ne the notion of admissible extension, which provides a general method for de�ning strong equivalence for arbitrary structures. We show several properties of strong order equivalence, providing necessary and suf�cient conditions for programs to be strongly order equivalent. We also explore the relationship of strong order equivalence between the three semantics studied in this paper, and the relationship to strong equivalence of standard logic programs. Based on these results, we study the applicability of program simpli�cation rules, known from standard ASP, in the presence of preferences. We obtain that most of these simpli�cations can be applied only in particular contexts. The main results of this work are that the relationship between the three preference semantics is changing under strong equivalence and that preferences cannot be �compiled away� in a modular fashion. We omit all proofs due to the page limit. 1

2 Background

Answer Sets. A logic program (LP) is a �nite set of rules such as p0 ← p1, . . . , pm, not pm+1, . . . , not pn, where n ≥ m ≥ 0, and each pi (0 ≤ i ≤ n) is an atom. For such a rule r, we let head(r) denote the head, p0, of r and body(r) the body, {p1, . . . , pm, not pm+1, . . . , not pn}, of r. Let body +(r) = {p1, . . . , pm} and body -(r) = {pm+1, . . . , pn}. For a set of rules Π, we write head(Π) = {head(r) | r ∈ Π}. A program is basic if body -(r) = ∅ for all its rules. The reduct, ΠX , of a program Π relative to a set X of atoms is de�ned by ΠX = {head(r) ← body +(r) | r ∈ Π, body -(r) ∩ X = ∅}. A set of atoms X is closed under a basic program Π if for any r ∈ Π, head(r) ∈ X if body +(r) ⊆ X. The smallest set of atoms being closed under a basic program Π is denoted by Cn(Π). Then, a set X of atoms is an answer set of a program Π if Cn(ΠX ) = X. We use AS(Π) for denoting the set of all answer sets of Π. In what follows, an important concept is that of the generating rules of an answer set. Given a set X of atoms from Π, de�ne RΠ(X) = {r ∈ Π | body +(r) ⊆ X, body -(r) ∩ X = ∅}.

Strong Equivalence. Under the answer set semantics, two LPs Π1 and Π2 are regarded as equivalent, denoted Π1 ≡ Π2, iff AS(Π1) = AS(Π2). Two LPs Π1 and Π2 are strongly equivalent, denoted Π1 ≡s Π2, iff, for any LP Π, the programs Π1 ∪ Π and Π2 ∪ Π are equivalent, i.e. Π1 ∪ Π ≡ Π2 ∪ Π. As shown in [Lifschitz et al., 2001], strong equivalence is closely related to the non-classical logic of hereand-there, which was adapted to logic-programming terms by Turner [Turner, 2003]: Let Π be an LP, and let X, Y ⊆ A such that X ⊆ Y . The pair (X, Y ) is an SE-model of Π (over A), if Y |= Π and X |= ΠY . By SEA(Π) we denote the set of all SE-models over A of Π. Usually the set A is left implicit and one just writes SE(Π). Then, for any LPs Π1 and Π2, Π1 ≡s Π2 iff SE(Π1) = SE(Π2) [Turner, 2003].

Preferences. A logic program Π is said to be ordered if we have a set N of terms serving as names for rules and a preference relation <⊆ N × N as a strict partial order among rules, where we write s < t for the names s, t ∈ N of rules in Π. Furthermore, we assume a bijective function n(.) assigning to each each rule r ∈ Π a name n(r) ∈ N. To simplify our notation, we usually write ri instead of n(ri) for some ri ∈ Π. Given ri, rj ∈ Π, ri < rj states that rj has higher priority than ri. Formally, an ordered (logic) program (OLP) can be understood as a quadruple (Π, N , n, <), where Π is a logic program, n is a bijective function between Π and the set of names N, and < is a set of preference relations over Π. Whenever possible, we leave N and n implicit and just write (Π,<) for OLPs. Moreover, we write <= ∅ if no partial order is given that is (Π, ∅) denotes a logic program. The interpretation that one rule has higher priority than an other rule can be made precise in different ways. In what follows, we consider three such interpretations: D� [Delgrande et al., 2003], B� [Brewka and Eiter, 1999], and W� preference [Schaub and Wang, 2003]. Given (Π,<), all of them use < for selecting preferred answer sets among the standard answer sets of Π. We now recall the de�nitions of these semantics. 2

1 A version of the paper including proofs can be found at http: //www.wfaber.com/research/#publications

De�nition 2.1 Let (Π, <) be an OLP and X be an answer set of Π. Then, X is <D �preserving, if an enumeration 〈ri〉i∈I of Π exists s.t. for every i, j ∈ I we have

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

Cond.1 stipulates that the enumeration of Π is compatible with <. Cond.2 makes the property of supportedness explicit. Although any answer set is generated by a supported sequence of rules, in D�preferences, rules cannot be supported by lower-ranked ones. Cond.3a separates the handling of unsupported rules from preference handling. Cond.3b guarantees that rules can never be blocked by lower-ranked ones.

De�nition 2.2 Let (Π, <) be an OLP and X be an answer set of Π. Then, X is <W �preserving, if an enumeration 〈ri〉i∈I of Π exists s.t. for every i, j ∈ I we have

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

For W�preference, the concept of order preservation from D�preferences is weakened in Condition 2 and 3 for suspending both conditions, whenever the head of a preferred rule is derivable in an alternative way.

De�nition 2.3 Let (Π, <) be an OLP and X be an answer set of Π. Then, X is <B �preserving, if an enumeration 〈ri〉i∈I of Π exists s.t. for every i, j ∈ I we have

1. if ri < rj, then j < i, and

2 In the following, I is an index set I = {1, . . . , n} for |Π| = n.

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

B�preference drops Cond.2; thus decoupling preference handling from the order induced by consecutive rule applications.

For σ ∈ {D,W,B}, we de�ne AS σ ((Π,<)) as the set of all <σ -preserving answer sets of OLP (Π,<). As shown in [Schaub and Wang, 2003], the three strategies yield an increasing number of preferred answer sets. That is, D� preference is stronger than W�preference, which is stronger than B�preference, which is stronger than no preference. More precisely, we have AS D ((Π,<)) ⊆ ASW ((Π,<)) ⊆ ASB ((Π,<)) ⊆ AS(Π) and, in addition, AS σ ((Π, ∅)) = AS(Π) for σ ∈ {D,W, B}.

3 Strong Order Equivalence

In this section we de�ne variants of equivalences for OLPs. De�ning �standard� equivalence (two programs permit precisely the same answer sets) is straightforward by considering the respective preferred answer sets.

However, concerning the notion of strong equivalence, there are some caveats. For standard programs, strong equivalence for Π1 and Π2 holds if for any program Π, Π1 ∪ Π and Π2 ∪ Π are equivalent. If we now take preferences into account, for any (Π,<), (Π1,<1) and (Π2,<2) would be strongly equivalent if (Π1 ∪ Π,<1 ∪ <) and (Π2 ∪ Π,<2 ∪ <) are equivalent. The problem is that (Π1 ∪ Π, <1 ∪ <) is not necessarily an OLP, because of two issues: 1. Rule label clashes, and 2. partial order clashes.

Rule label clashes, i.e. two different rules have the same name or one rule has two different names, can be resolved by a renaming. We say that (Π,N ∗ , n∗ ,<∗ ) is a renaming of (Π,N, n,<) if N ∗ is a new set of names of rules, n∗ (.) is a bijective function assigning each rule of Π an unique name of N ∗ , and n∗ (r) <∗ n∗ (r′ ) holds iff n(r) < n(r′ ), for all r, r′ ∈ Π. The union of two OLPs is then de�ned as follows.

De�nition 3.1 Let (Π,N, n,<) and (Π′ ,N ′ , n′ ,<′ ) be OLPs where N,N ′ are disjoint sets of rule names.

We de�ne the union of (Π,N, n,<) and (Π′ ,N ′ , n′ ,<′ ) as (Π∗ , N ∗ , n∗ , <∗ ), where

• Π∗ = Π∪Π′
• N ∗ as new set of names of rules,
• n∗ (r) for r ∈ Π ∪ Π′ as a bijective function assigning each rule of Π ∪ Π′ an unique name of N ∗ , and
• <∗ as < ∪ <′ , where for r, r′ ∈ Π ∪ Π′ , n∗ (r) <∗ n∗ (r′ ) holds whenever n(r) < n(r′ ) or n′ (r) <′ n′ (r′ ) holds.

Again, we usually leave N ∗ and n∗ implicit. Sometimes we write (Π∪Π′ ,< ∪ <′ ) for the union of (Π,<) and (Π′ ,<′ ).

We next observe that the union of OLPs is not necessarily an OLP. For this, consider

Then, we have

where <∗ is not a strict partial order. Hence, (Π∗ ,<∗ ) is not an OLP. To avoid this, we de�ne the notion of admissible extensions of an OLP.

Π′ , < ∪ <′ ) is an OLP.

We remark that the notion of compatibility for orderings, as de�ned in [Brewka and Eiter, 1999], is similar in spirit to admissible extensions, but concerns only the order relation and not the rules in the program.

Analogously to (normal) logic programs, we can de�ne the notion of equivalence of OLPs.

De�nition 3.3 (Order equivalence) Let (Π1,<1) and (Π2,<2) be OLPs and σ ∈ {D,B,W}. Then, (Π1,<1) and (Π2, <2) are <σ -equivalent, denoted (Π1, <1) ≡σ (Π2, <2), iff ASσ ((Π1, <1)) = ASσ ((Π2, <2)).

Since the de�nition of strong equivalence for logic programs can be interpreted as having the same answer sets in any extension, we employ the notion of admissible extensions for de�ning the analogon for OLPs.

De�nition 3.4 (Strong order equivalence) Let (Π1,<1) and (Π2, <2) be OLPs and σ ∈ {D, B, W}.

Then, (Π1,<1) and (Π2,<2) are strongly <σ -equivalent iff for all admissible extensions (Π,<) of (Π1,<1) and (Π2,<2) it holds that (Π1 ∪ Π,<1 ∪ <) and (Π2 ∪ Π,<2 ∪ <) are <σ - equivalent.

Abbreviatory, we write ≡σs whenever two OLPs are strongly <σ -equivalent.

4 Properties and Relationships

Next, we want to characterize which conditions two OLPs must ful�ll s.t. they are strongly order equivalent.

The next theorem states that strong order equivalence implies strong equivalence of the underlying logic programs.

Intuitively, if the logic programs are not strongly equivalent, one extension of them admits an answer set A, which is no answer set of the extension of the other program. If the corresponding ordered extensions have the same answer sets, this means that A is inhibited by the preferences. But then one can always construct a further extension, which regenerates A for one program, but not for the other. For example, programs

have both the preferred answer set {a}, whereas Π2 has additionally the answer set {b}. Taking (Π, ∅) = {r4 : b ← y, r5 : y ←} yields {a, b, y} as preferred answer set of (Π1∪Π, ∅), but {b, y} as preferred answer set of (Π2∪Π, <2).

Note that one can create such a �compensating� program for any answer set which is inhibited by the preference relation. For this, we use new symbols and new rules, which are not involved in the preference relation, to �repair� this answer set. Therefore strong equivalence is a necessary condition for strong order equivalence.

Next, we turn our attention to the set of generation rules. For this, consider the following OLPs:

We observe that Π1 ≡s Π2, but taking

yields {a, b} ∈ AS σ ((Π1 ∪Π∗ , <∗ )) but ASσ ((Π2 ∪Π∗ , <∗ )) = ∅ for σ ∈ {D,W,B}. They are not strongly order equivalent because they do not coincide on their set of generating rules. (Π1, ∅) contains r3 and (Π2, ∅) rule r2 to derive the atom b. Adding r4 and the preference that r4 is higher preferred to r2 entails that (Π2∪Π∗ , <∗ ) has no preferred answer set since r4 is blocked by the lower preferred rule r2, while (Π1 ∪ Π∗ ,<∗ ) has a preferred answer set since r3 allows to block r4 in an alternative way. This allows us to suppose that strong order equivalence enforces that the OLPs must coincide on all rules which can become applicable. For this, we say that a rule r ∈ Π contributes to an answer set X, if there exists an Π∗ such that X ∈ AS(Π∪Π∗ ) and r ∈ RΠ∪Π∗ (X). Rules which are not contributing to answer sets, are never applicable, e.g. body +(r) ∩ body -(r) ̸= ∅. For B�preferences, we obtain that two strongly order equivalent programs must coincide on their rules contributing to answer sets.

Theorem 4.2 Let (Π1,<1) and (Π2,<2) be OLPs. If (Π1,<1) ≡Bs (Π2,<2), then for all Π and for all X ∈ AS(Π1 ∪ Π) = AS(Π2 ∪ Π) we have RΠ1∪Π(X) = RΠ2∪Π(X).

Interestingly, for D� and W�preferences, these conditions have to be weakened.

Theorem 4.3 Let (Π1,<1) and (Π2,<2) be OLPs and σ ∈ {D,W}. If (Π1,<1) ≡σs (Π2,<2), then for all Π and for all X ∈ AS(Π1 ∪Π) = AS(Π2 ∪Π) we have RΠ1∪Π(X) \{r ∈ Π1∪Π | head(r) ∈ body +(r)} = RΠ2∪Π(X)\{r ∈ Π2∪Π | head(r) ∈ body +(r)}.

Since D- and W- preferences couple rule application with preference handling, answer sets can be inhibited by preferences because applied rules are not enumerable in an order preserving way (see Condition 2 in De�nition 2.1 and 2.2). But one can always �nd an extension such that those answer sets are regenerated. For applied �loop� rules, i.e. head(r) ∈ body +(r), another rule must always exist which derives the head in an order preserving way. Hence, such loop rules are redundant wrt. D- and W- preferences as long as they are not involved in the preference relations. In contrast, B- preferences decouple preference handling from rule application and hence, one can always �nd an extension, where those loop rules regenerate a non-preferred answer set to a preferred one in one program but not in the other one. For example,

are not strongly <B - equivalent. Taking

yields AS B ((Π1 ∪ Π,<)) = ∅ but AS B ((Π2 ∪ Π,<)) = {a}. Here, rule r2 can be used to block r3. For D- and Wpreferences, however, r2 has to be ordered after r1, hence it can not be used to block r3.

In the following we will concentrate on the preference relations. For this consider the program

and the preference relation r1 > r2. We obtain that (Π, ∅) ≡σ (Π,<) holds for all σ ∈ {D,W,B} and (Π, ∅) and (Π,<) coincide on their set of rules. For (Π, ∅), rule r1 must be considered before rule r2 in D- and W-preference, since the derivation of the positive body of r2 depends from r1. Thus, adding the preference relation r1 > r2 to (Π, ∅) has no effect on <D - and W- preferred answer sets. Surprisingly, this does not hold when considering strong order equivalence. Taking

yields AS σ ((Π ∪ Π′ , <′ )) = {{a, b, x, z}} while AS σ ((Π ∪ Π′ , < ∪ <′ )) = ∅. For (Π, <)∪(Π′ , <′ ) we get the transitive preference r4 > r3, implying that r4 is blocked by a lower preferred rule, which we don't obtain for (Π, ∅) ∪ (Π′ ,<′ ). Since one can always construct such a program (observe that the relevant rules contain new symbols), it follows that two OLPs can never be strongly equivalent if the preference relations do not coincide.

Theorem 4.4 Let (Π1,<1) and (Π2,<2) be OLPs and σ ∈ {D,W,B}. If (Π1,<1) ≡σs (Π2,<2) then <1=<2.

As a special case we obtain that (Π, ∅) ̸≡σs (Π,<) holds for any program Π, any non-empty preference relation on Π, and any σ ∈ {D,W,B}. Moreover, for every OLP (Π,<),≮= ∅, there exists no strongly order equivalent program (Π′ , ∅).

Corollary 4.5 Let (Π,<) be an OLP such that ≮= ∅ and σ ∈ {D,W,B}. Then, there exists no logic programΠ′ such that (Π,<) ≡σs (Π′ , ∅).

Interestingly, this tells us that no transformation from an OLP with a non-empty preference relation to a logic program exists such that the transformed program is strongly order equivalent to the original one. The results given above are suf�cient for characterizing strong order equivalence.

Theorem 4.6 Let (Π1,<1) and (Π2,<2) be OLPs. If Π1 ≡s Π2, <1=<2, and for all Π and for all X ∈ AS(Π1 ∪ Π) = AS(Π2 ∪ Π) we have RΠ1∪Π(X) = RΠ2∪Π(X), then (Π1,<1) ≡Bs (Π2,<2).

Theorem 4.7 Let (Π1,<1) and (Π2,<2) be OLPs and σ ∈ {D,W}. If Π1 ≡s Π2, <1=<2, and for all Π and for all X ∈ AS(Π1 ∪Π) = AS(Π2 ∪Π) we have RΠ1∪Π(X) \{r ∈ Π1∪Π | head(r) ∈ body +(r)} = RΠ2∪Π(X)\{r ∈ Π2∪Π | head(r) ∈ body +(r)}, then (Π1,<1) ≡σs (Π2,<2).

For example,

are strongly order equivalent in all three semantics, whereas

are only strongly <D - (and <W -) equivalent, but not strongly <B - equivalent. With these results we can formalize the following characterization of strong order equivalence.

Corollary 4.8 Let (Π1,<1) and (Π2,<2) be OLPs. Then, (Π1,<1) ≡Bs (Π2,<2) iff Π1 ≡s Π2, <1=<2, and for all Π and for all X ∈ AS(Π1 ∪ Π) = AS(Π2 ∪ Π) we have RΠ1∪Π(X) = RΠ2∪Π(X).

Corollary 4.9 Let (Π1,<1) and (Π2,<2) be OLPs and σ ∈ {D,W}. Then, (Π1,<1) ≡σs (Π2,<2), iff Π1 ≡s Π2, <1=<2, and for all Π and for all X ∈ AS(Π1 ∪ Π) = AS(Π2 ∪Π) we have RΠ1∪Π(X) \ {r ∈ Π1 ∪Π | head(r) ∈ body +(r)} = RΠ2∪Π(X) \ {r ∈ Π2 ∪ Π | head(r) ∈ body +(r)}.

Regarding preferred answer sets, the different strategies for preference handling yield an increasing number of preferred answer sets. Interestingly, the above given theorems show that there is no difference in the behavior of D� and W� preferences when considering strong order equivalence. In contrast, fewer programs are strongly order equivalent in the B�semantics, since preference handling is decoupled from rule application.

Theorem 4.10 Let (Π1,<1) and (Π2,<2) be OLPs. Then (a) if (Π1,<1) ≡Bs (Π2,<2) then (Π1,<1) ≡Ws (Π2,<2), (b) (Π1,<1) ≡Ws (Π2,<2) iff (Π1,<1) ≡Ds (Π2,<2).

Considering answer sets, each <D -preferred answer set is <W -preferred and each <W -preferred is <B -preferred. Interestingly, regarding strong order equivalence we obtain that ≡Ds iff ≡Ws , so the differences between the D- and W- semantics can be compensated by extending the program in a suitable way. Moreover, since ≡Bs implies ≡Ws and ≡Bs implies ≡Ds , the B-semantics imposes a strictly stronger criterion for programs to be strongly order equivalent. The reason for this is that B-preference decouples preference handling from rule application, and in addition, these differences cannot be compensated by adding suitable extensions.

5 Program Simpli�cations

Corollaries 4.9 and 4.8 show that two OLPs which are strongly order equivalent, differ in rules which are not involved in the preference relation and which are never applicable. Additionally, for D- and W- semantics, strongly order equivalent logic programs may differ in loop rules, in which the head is contained in the positive body. These results allow us to formalize the following results concerning transformations on OLPs. In the following, we say that a rule r is involved in a preference relation < if there exists an r ′ such that r < r′ or r′ < r holds.

Corollary 5.1 Let (Π,<) be an OLP such that for r ∈ Π, which is not involved in <, for all Π′ and X ∈ AS(Π∪Π′ ) we have r ̸∈ RΠ∪Π′ (X). Then, (Π, <) ≡σs (Π\{r}, <) holds for σ ∈ {D, W, B}.

This corollary expresses that a rule, which is never applicable and not involved in <, is redundant regarding strong order equivalence. The next corollary concentrates on loop rules.

Corollary 5.2 Let (Π, <) be an OLP and σ ∈ {D, W}. Furthermore, let r ∈ Π s.t. head(r) ∈ body +(r) and r is not involved in <. Then, (Π,<) ≡σs (Π \ {r},<).

In [Eiter et al., 2004; Osorio et al., 2001] transformations on logic programs are reported, which can be used for simplifying a program. For those modular transformations a program must be strongly equivalent to the transformed one. Considering OLPs, we observe that these transformations in general do not guarantee strong order equivalence. Transformation TAUT expresses that for all logic programs Π and all r ∈ Π where head(r) ∈ body +(r) we have Π ≡s Π \ {r}. Corollary 5.2 implies that the analogon for OLPs only holds for the D- and W- semantics as long as r is not involved in <. Transformation RED- expresses that for a logic program Π and for rules r1, r2, where head(r2) ∈ body -(r1) and body(r2) = ∅, we have Π ≡s Π \ {r1}. Since r2 is always a generating rule, regardless which rules we add to Π, r1 never contributes to an answer set. Hence, RED- is feasible for OLPs unless r1 is involved in <. For r ∈ Π, where body +(r) ∩ body -(r) ̸= ∅ we have that Π ≡s Π \ {r} (transformation CONTRA). Since such a rule is never applicable, this result can be carried over to OLPs whenever this rule is not involved in <. Transformation NONMIN states that for r1, r2 ∈ Π, where head(r2) = head(r1) and body(r2) ⊆ body(r1), we have that Π ≡s Π \ {r1} holds. Since there is no information whether r1 can become applicable or not, this transformation can only be made on OLPs whenever r1 is not involved in < and never becomes applicable. For example, consider the program:

Here we have that head(r3) = head(r4) and body(r3) ⊆ body(r4), hence, Π1 ≡s Π1\{r4}. Since r4 is applicable, the simpli�ed program is not strongly order equivalent. Taking

yields {a, b, c} ∈ AS σ ((Π1 ∪ Π∗ ,<∗ )) but ASσ (((Π1 \ {r4})∪Π∗ , <∗ )) = ∅, for σ ∈ {D,W, B}. Thus, (Π1, ∅) ̸≡σs (Π1 \ {r4}, ∅). Similar considerations apply for the transformation S-IMP, where for all r, r′ ∈ Π such that there exists an A ⊆ body -(r′ ) such that head(r) ∈ head(r′ ) ∪ A, body -(r) ⊆ body -(r′ ) \ A and body +(r) ⊆ body +(r′ ) we have Π ≡s Π \ {r′ }. This transformation can only be carried over to OLPs whenever r′ is not involved in < and never becomes applicable. For example, taking

and A = {c} yields Π ≡s {r}, where r′ is applicable wrt {a, b} ∈ AS(Π ∪ {b ←}). But (Π, ∅) ̸≡σs ({r}, ∅), since for

we get {a, b} ∈ AS σ ((Π ∪ Π∗ ,<∗ )) but ∅ = AS σ (({r} ∪ Π∗ , <∗ )) for σ ∈ {D, W, B}. Transformation WGPPE states for a rule r1 ∈ Π, where a ∈ body +(r1), Ga = {r2 ∈ Π |

head(r2) = a} and Ga ̸= ∅ that Π ≡s Π ∪ G′a holds where G′a = {head(r1) ← (body +(r1) \ {a}) ∪ not body -(r1) ∪ body(r2) | r2 ∈ Ga}. As with the other transformations obtained for strong equivalence, this one is transferable to strong order equivalence if the rules fromGa become never applicable and are not involved in the preference relation. E.g., for

we have that Π ≡s Π ∪ {b ←} holds. By taking

we obtain (Π, ∅) ̸≡σs (Π ∪ {b ←}, ∅) since (Π ∪ Π∗ , <∗ ) has no <σ � preferred answer set while (Π∪{b ←}∪Π∗ , <∗ ) has <σ � preferred answer set {a, b}, for σ ∈ {D,W, B}.

6 Conclusions and FutureWork

We have presented the notion of strong order equivalence for ASP with preferences. We have provided an extensive analysis of this novel notion, and studied the relationship between different preference semantics for it. We have also analyzed the conditions for certain simpli�cation methods to guarantee strong order equivalence (hence applicability to modules).

We could show in Corollaries 4.8 and 4.9 that two programs are strongly W- and D-equivalent, if (and only if) the preference relation is equal, their standard ASP programs are strongly equivalent, and their �non-looping� generating rules are identical for all answer sets of any extension of them. For B-preference, also the �looping� generating rules must be identical in any answer set.

¿From Theorem 4.10 we obtain that exactly the same pairs of programs are strongly <D - and <W - equivalent, while not all of them are strongly <B - equivalent. That is, the semantical differences between D- and W- preference have no longer any effect when considering strong order equivalence. On the contrary, for B- semantics the differences to D- and Wpreferences are strengthened under strong order equivalence, since it decouples preference handling from rule application, which can not be compensated by suitable extensions.

We have furthermore studied possibilities to simplify ordered programs. In Corollaries 5.1 and 5.2 we have given abstract conditions for simpli�cations, and have assessed under which circumstances simpli�cation rules from standard ASP can be applied on ASP modules with preferences.

The reader may have noted that we did not de�ne a notion which would correspond to SE-models in standard ASP strong equivalence. Indeed there seem to be considerable dif�culties: SE-models can only express statements on atoms, and not directly on rules. However, as demonstrated e.g. in Theorem 4.3, strong order equivalence depends heavily on the rules involved in the program. We therefore conjecture that �SE-models� for D-, W-, and B- preferred answer sets must include a means for stating relationships among rules, and leave this topic for future work.

Another way of analyzing strong order equivalence could be offered by a compilation of the programs, as done e.g. in the plp-System [Delgrande et al., 2003; plp, 2002]. There, ordered programs are compiled into logic programs such that their answer sets directly correspond to the preferred answer sets of the original ordered program. Since the compilation is a logic program, one could suppose that two ordered programs are strongly order equivalent if the compilation of them possess the same SE-models. However, the compilation introduces additional symbols. Hence, the answer sets of two compiled programs, which represent the same preferred answer set, are in general incomparable because of these additional symbols. One would therefore have to consider strong equivalence under a projection of the answer sets. Furthermore, for an exact notion one would also have to take into account that compiled programs have a particular, rather than arbitrary, structure. Such a notion of strong equivalence has (to the best of our knowledge) not been studied so far. Therefore, we leave this kind of analysis for future work.

Corollary 4.5 shows that no transformation from an ordered program (Π,<) into a logic program Π′ exists such that (Π, <) is strongly order equivalent to Π′ . Also, Corollaries 4.8 and 4.9 describe rigorous conditions on ordered programs being strongly order equivalent under the considered preference semantics. Hence, further work could be to de�ne and study weaker notions of order equivalence.