A General Notion of Equivalence for Abstract Argumentation

1 Introduction

Argumentation has become one of the major fields within AI over the last two decades [Rahwan and Simari, 2009; Bench-Capon and Dunne, 2007]. In particular, Dung's argumentation frameworks [Dung, 1995], AFs for short, are widely used and act as integral concepts in several advanced argumentation formalisms. They focus entirely on conflict resolution among arguments, treating the latter as abstract items without logical structure. Hence, the only information available in AFs is the so-called attack-relation that determines whether an argument is in a certain conflict with another one. As already outlined by Dung, AFs provide a formally simple basis to capture the essence of different nonmonotonic formalisms. Therefore, several so-called semantics are typically considered for AFs, see also [Baroni et al., 2011]. A semantics delivers several sets of arguments (called extensions) that can be jointly accepted in order to satisfy certain properties. One such property is given by admissible sets which consist of arguments that do not attack each other and attack each argument attacking the set itself.

Bearing the nonmonotonic nature of AFs in mind, it is evident that the standard notion of equivalence (i.e., do two AFs possess the same sets of extensions?) is a rather weak concept. In particular, it is not the case that replacing an AF by an equivalent one is a faithful manipulation. As an example consider the AFs Fabc = ({a, b, c}, {(a, b), (b, c), (c, a)}) and Fab = ({a, b}, {(a, a), (a, b)}), which are equivalent for

∗This research has been supported by DFG: BR 1817/7-2 and FWF: I2854.

Wolfgang Dvoˇr ´ak

TU Wien, Austria dvorak@dbai.tuwien.ac.at

Stefan Woltran

most semantics, including admissible sets. However, replacing Fabc by Fab in a larger AF G might not be an equivalencepreserving action. Suppose G expands Fabc via an attack from some argument d to b. Then, the mentioned replacement would change each admissible set S ∪ {d, c} into S ∪ {d}. On the other hand, if Fabc is embedded in G only via an attack (d, a) - see Figure 1 - the replacement is faithful. More formally, we then have that the admissible sets of G and G[Fabc/Fab] are the same (a formal definition of replacements G[·/·] is given in Section 6).

Observations of this kind gave rise to more restricted notions of equivalence [Oikarinen and Woltran, 2011; Baumann, 2012; Baumann and Woltran, 2016]. Strong equivalence (also called expansion equivalence) between two AFs F and F ′ holds (w.r.t. a semantics σ) iff for all AFs H the expanded AFs F ∪ H and F ′ ∪ H have the same σ-extensions. By definition, this notion of equivalence guarantees that F can be replaced by a strongly equivalent (w.r.t. σ) AF F ′ in any framework G without changing the σ-extensions of G. Interestingly, the characterization results for strong equivalence are surprisingly simple and can be given via so-called kernels, syntactic modifications of the involved AFs. From a theoretical perspective, it is thus open how this conceptual difference between standard and strong equivalence can be captured via a uniform formal characterization which has these two notions as corner cases.

From a computational point of view, strong equivalence (and related versions) seem to be an appealing notion, since checks for replacements, and thus also for simplifications in AFs, would become easy. However, strong equivalence is too restricted for practical purposes. Even obvious simplifications are not captured: an example are isolated self-loops, which can be safely removed from AFs for many standard semantics. However, AF F = ({a}, {(a, a)}) is not strongly equivalent to the empty AF F ′ = (∅, ∅) for admissible semantics; just take H = ({a}, ∅). Then, {a} is admissible for F ′ ∪H but not for F ∪H. This indicates that a suitable equivalence notion for replacement needs a particular treatment for those arguments which are directly involved in the change.

Hence, what we require is an equivalence notion that compares two AFs such that

1. the relations between core arguments are fixed, while
2. the remaining arguments are allowed to interact arbitrarily with possible expansions of the compared AFs.

Our proposal is to define, given a set of core arguments C and a semantics σ, C-relativized equivalence between two AFs F and F ′ w.r.t. σ (in symbols, F ≡σC F ′ ) to hold, if F ∪ H and F ′ ∪ H have the same σ extensions, for each AF H not containing arguments fromC. Observe that this notion indeed captures strong equivalence (set C = ∅) and standard equivalence (set C to be the universe of all arguments).

Coming back to our example with Fabc and Fab, the idea is to set C = {a, b, c} and compare the two AFs plus their interaction with the AF G where Fabc occurs in. In our case, we compare F G abc = ({a, b, c, d}, {(a, b), (b, c), (c, a), (d, a)}) and F G ab = ({a, b, d}, {(a, a), (a, b), (d, a)}). Then, F G abc ≡σC F G ab implies that G and G[Fabc/Fab] are equivalent under σ, i.e., replacing Fabc by Fab in G is safe for semantics σ.

Our main contributions are as follows:

• We first define restrictions for the main semantics of stable, admissible, preferred, complete and grounded extensions. These identify extensions of an AF F that are acceptable in some expansion F ∪H and are integral for equivalence characterizations.
• We give exact characterizations of C-relativized equivalence for the five semantics mentioned above; in addition we also show results for conflict-free and naive sets.
• We provide a complexity analysis for deciding Crelativized equivalence; as corollaries we also obtain insight to the complexity of standard equivalence.
• Finally, we give a formal notion of replacement in AFs and illustrate how our equivalence notion can be employed for local simplifications within AFs.

Some proofs are only sketched or omitted due to space constraints. Full proofs are available in [Baumann et al., 2017].

2 Preliminaries

In this section, we introduce argumentation frameworks [Dung, 1995] and recall the semantics we study (for an overview, see [Baroni et al., 2011]). We fix U as countably infinite domain of arguments.

Definition 2.1. An argumentation framework (AF) is a pair F = (A,R) where A ⊆ U is a finite set of arguments and R ⊆ A × A is the attack relation. The pair (a, b) ∈ R means that a attacks b. We use A(F ) to refer to A and R(F ) to refer to R. We say that an AF is given over a set B if A(F) ⊆ B.

Given an AF F and S ⊆ U, we define S+ F = {x | ∃y ∈ S : (y, x) ∈ R(F)}, SF = {x | ∃y ∈ S : (x, y) ∈ R(F)}, and the range of S in F as S⊕ F = (S ∩ A(F )) ∪ S+ F .

Given F = (A,R), argument a ∈ A is defended (in F) by a set S ⊆ U if {a}-F ⊆ S+ F . The characteristic function FF : 2A → 2A of F is defined as FF (S) = {a ∈ A | a is defended by S in F}.

Given AFs F = (A,R), F ′ = (A′ ,R′ ), and S ⊆ U, we denote the union of AFs as F ∪ F ′ = (A ∪ A′ ,R ∪ R′ ), and define F \ S = (A \ S, R ∩ ((A \ S) × (A \ S))) and F ∩ S = (A ∩ S, R ∩ ((A ∩ S) × (A ∩ S))).

Semantics for argumentation frameworks are defined as functions σ which assign to each AF F a set σ(F ) ⊆ 2A(F ) of extensions. We consider for σ the functions naive, grd, stb, adm, com, and prf , which stand for naive, grounded, stable, admissible, complete, and preferred extensions, respectively.

Definition 2.2. Let F = (A,R) be an AF. A set S ⊆ A is conflict-free (in F), if there are no a, b ∈ S, such that (a, b) ∈ R. cf (F) denotes the collection of conflict-free sets of F. For a conflict-free set S ∈ cf (F), it holds that

• S ∈ naive(F), if there is no T ∈ cf (F) with T ⊃ S;
• S ∈ stb(F), if S⊕ F = A;
• S ∈ adm(F), if S ⊆ FF (S);
• S ∈ com(F), if S = FF (S);
• S ∈ grd(F), if S ∈ com(F) and ∄T⊂S s.t. T∈com(F);
• S ∈ prf (F), if S ∈ adm(F) and ∄T⊃S s.t. T∈adm(F).

We recall that for each AF F, the grounded semantics yields a unique extension, which is the least fixed-point F ∞ F (∅) of the characteristic function FF .

3 Notions of Equivalence

We first review two equivalence notions for AFs from the literature, namely standard and strong equivalence.

Definition 3.1. Given a semantics σ. Two AFs F and G are (standard) equivalent w.r.t. σ (F ≡σ G) iff σ(F) = σ(G).

Definition 3.2. Given a semantics σ. Two AFs F and G over U are strongly equivalent w.r.t. σ (F ≡σS G) iff F ∪ H ≡σ G ∪ H holds for each AF H over U.

In this work we introduce the new notion of C-relativized equivalence, which is parametrized by the set C of core arguments which will not be directly touched by the possible expansions (i.e., AFs H added to the compared AFs are not arbitrary anymore).

Definition 3.3. Given a semantics σ and C ⊆ U. Two AFs F and G are C-relativized equivalent w.r.t. σ (F ≡σC G) iff F ∪ H ≡σ G ∪ H holds for each AF H over U \ C.

Notice that (i) for C=∅ the C-relativized equivalence coincides with strong equivalence and (ii) when C = U then Crelativized equivalence is just standard equivalence (the only AF over U\C=∅ is (∅, ∅) and F∪(∅, ∅)=F for all AFs F).

The following observation expresses the fact that Crelativized equivalence survives if we extend the core C with further untouchable arguments. Since in general standard equivalence (C = U) does not imply strong equivalence (C = ∅) the assertion does not hold for shrinking the core.

Observation 3.4. For any two AFs F,G, any two sets C,D ⊆ U and any semantics σ, if C ⊆ D and F ≡σC G, then F ≡σD G.

An immediate consequence of the observation above is that strong (standard) equivalence is more (less) demanding than relativized equivalence, no matter which core C is considered. This is simply due to the fact that for any core C, ∅ ⊆ C ⊆ U. The next proposition gives more refined conditions for the coincidence between C-relativized equivalence and strong or standard equivalence, respectively. Since we consider finite AFs only we restrict our considerations to finite cores too.

Proposition 3.5. Let F, G be AFs, C ⊆ U a finite core, σ ∈ {stb, adm, com, grd , prf }, and B = C∩(A(F ) ∪ A(G)).

1. If B = ∅, then F ≡σC G iff F ≡σS G.

2. If B = A(F) ∪ A(G), then F ≡σC G iff F ≡σ G.

4 Characterization Results

In what follows, we aim for giving characterizations for deciding F ≡σC G with finite C ⊂ U, such that an explicit consideration of all possible expansions is avoided. In other words, we need semantical concepts that are solely defined on the AFs F and G, but take the core C into account. To this end, we start with the concept of C-restricted semantics. Our main result for exactly characterizing F ≡σC G then requires that the C-restricted extensions coincide for the compared AFs. As we will see in Section 4.2, some further semantics-dependent conditions must be met.

4.1 C-restricted Semantics

For C-restricted semantics, we restrict the relevant properties of the original semantics to the core arguments.

Definition 4.1. Let F be an AF, C ⊆ U and E ⊆ A(F).

• E ∈ stbC(F) if E ∈ cf (F) and A(F) ∩ C ⊆ E⊕ F .
• E ∈ admC(F) if E ∈ cf (F) and EF ∩C ⊆ E+ F .
• E ∈ prf C(F) if E ∈ admC(F) and for all D ∈ admC(F) with E \ C = D \ C, E+ F \ C ⊆ D+ F \ C, and EF \ E+ F ⊇DF \D+ F we have E ∩ C ̸⊂ D ∩ C.

Example 4.2. For AF F G abc from the introduction and C = {a, b, c}, we have stbC(F G abc ) = {{d, b}}, admC(F G abc ) = {∅, {d}, {d, b}}. In this particular case, standard extensions and restricted ones coincide. Let us thus extend F G abc to the AF F as depicted below.

We observe that stbC(F) = stbC(F G abc ) although stb(F) = ∅; likewise admC(F) = admC(F G abc ) but adm(F) = {∅}. Finally, we have prf C(F G abc ) = prf C(F) = {∅, {d, b}}. ♦

In order to define the C-restricted complete and grounded semantics we need the concept of the C-restricted characteristic function FF,C,E(S) for AF F and E, S⊆A(F).

Definition 4.3. Let F be an AF, C ⊆ U and E ⊆ A(F).

• E ∈ comC(F) if E ∈ cf (F) and E = FF,C,E(E).
• E ∈ grdC(F) if E ∈ cf (F) and E = F ∞ F,C,E (∅).

Notice that in case A(F) ⊆ C, C-restricted semantics as given in Defs. 4.1 and 4.3 reduce to the original semantics, i.e., σC(F) = σ(F) for any C with A(F) ⊆ C.

Another crucial feature of C-restricted semantics is that σC(F) returns all the argument sets that are projections of σ-extensions in some F ∪ H with H defined over U \ C.

Proposition 4.4. Let F be an AF, σ ∈ {stb, adm, com, grd, prf }, and C ⊆ U. E ∈ σC(F) iff there exists an AF H over U \ C and T ∈ σ(F ∪ H) such that T ∩ A(F ) = E.

Proof Sketch (stable/admissible). ⇒: Let B = (A(F ) \ (E ∪ C)) and consider the AF H = ({t} ∪ B, {(t, b) | b ∈ B}) with t ∈ U \ C a fresh argument (not occurring in F). Then H is given over U \ C and E ∪ {t} ∈ σ(F ∪ H), for σ ∈ {stb, adm}. ⇐: Let σ ∈ {stb, adm} and suppose T ∈ σ(F ∪ H) for some H over U \ C. For E = T ∩ A(F), we clearly have E ∈ cf (F). As all attacks on c ∈ C are already present in F, for σ = stb we have that A(F) ∩ C ⊆ E+ F and thus E ∈ stbC(F). Likewise for σ=adm, since each c ∈ EF ∩C is already attacked by E in F , E ∈ admC(F ).

The proposition above establishes a close relationship with the enforcing problem [Baumann and Brewka, 2010]. More precisely, the C-restricted σ-extensions E are exactly the sets enforceable without touching the core arguments.

Example 4.5. Recall F from Example 4.2. For C = {a, b, c} we had {b, d} ∈ stbC(F) and {b, d} ∈ admC(F). The construction in the proof of Prop. 4.4 just adds an argument t attacking e (note that t and e are not from C). For the resulting AF it is easily checked that {t, b, d} is among its admissible sets, resp. is its only stable extension. ♦

Next we consider properties that will appear in the Crelativized equivalence characterizations of all semantics σ ∈ {stb, adm, com, grd , prf }.

Proof Sketch (stable). If stbC(F) = ∅, stb(F ∪H) = ∅ for all H over U \ C (by Prop. 4.4), and thus also stbC(G) = ∅.

Now suppose stbC(F) ̸= ∅ and A(F) \ C ̸= A(G) \ C. W.l.o.g. there is an a ∈ A(F) \ C and a /∈ A(G). Suppose there is E ∈ stbC(F) with a ∈ E. By Prop. 4.4, we can give an H such that there is a T ∈ stb(F ∪ H) with T ∩ A(F) = E. Notice that H does not contain arguments from E. Thus a /∈ A(G∪H) and hence T /∈ stb(G∪H), a contradiction to F ≡stb C G. Thus there is no E ∈ stbC(F) with a ∈ E.

Let E ∈ stbC(G). By Prop. 4.4, there is an AF H such that there is a T ∈ stb(G ∪ H) with T ∩ A(G) = E and we can build this H with a /∈ A(H). Let now H′ = H∪({a}, ∅) and observe that H′ is still given over U \C. Then, T ∪{a} ∈ stb(G∪H′ ) but it cannot be that T ∪ {a} ∈ stb(F ∪H′ ) as this, by Prop. 4.4, would give rise to an E ∈ stbC(F) with a ∈ E. But this is in contradiction to F ≡stb C G.

Proof. σC(F) ⊆ σC(G): By Prop. 4.4, for each E ∈ σC(F) there is an H over U \ C and T ∈ σ(F ∪ H), such that T ∩ A(F) = E. By assumption, T ∈ σ(G ∪ H) and, by Prop. 4.4, E′ = T ∩ A(G) ∈ σC(G). As A(H) ∩ C = ∅, we have that T ∩ C = E ∩ C = E′ ∩ C, and, by Lem. 4.6, A(F)\C = A(G)\C and thus E\C = E′ \C. Hence, E = E′ and E ∈ σC(G). σC(F) ⊇ σC(G) is by symmetry.

4.2 Characterizations

In the following we give the characterizations for all semantics under consideration. We already have that two AFs can only be C-relativized equivalent w.r.t. σ if A(F) \ C = A(G) \ C (or σC(F) = ∅) and σC(F) = σC(G). Now depending on the concrete semantics we have to appoint additional conditions for the sets E ∈ σC(F) to ensure that they appear in the same expansions of F and G.

Stable Semantics. For stb semantics we require for each E ∈ stbC(F) that the range of E coincides on F \ C and G \ C. That is, the arguments that have to be attacked by H to make E stable in F ∪ H coincide with the arguments that have to be attacked by H to make E stable in G ∪ H.

Theorem 4.8. Let F, G be AFs and C ⊆ U. Then, F ≡stb C G iff the following conditions jointly hold:

1. if stbC(F) ̸= ∅, A(F) \ C = A(G) \ C;
2. stbC(F) = stbC(G); and
3. for all E ∈ stbC(F), E+ F \ C = E+ G \ C.

Proof Sketch. ⇒: The conditions (1) and (2) are immediate by Lem. 4.6 and Lem. 4.7. Now let stbC(F) = stbC(G) ̸= ∅ and A(F) \ C = A(G) \ C, and assume there is an E ∈ stbC(F) s.t. E+ F \C ̸= E+ G \ C. W.l.o.g. let a ∈ A(F) \ E⊕ F and a /∈ A(G) \ E⊕ G . We observe that a /∈ E and a /∈ C and thus a ∈ E+ G . Let H = ({t}∪A(G)\E⊕ G , {(t, b) | b ∈ A(G)\ E⊕ G }) where t is fresh argument from U \C. Observe that H does not contain arguments from C since E ∈ stbC(G) and thus each a ∈ C occurring in G is attacked by E. We have E ∪ {t} ∈ stb(G ∪ H), while E ∪ {t} /∈ stb(F ∪ H), a contradiction to F ≡stb C G.

⇐: Suppose F ̸≡stb C G. W.l.o.g. there is an AF H over U \C and a set S such that S ∈ stb(F ∪H) but S ̸∈ stb(G∪ H). By Prop. 4.4, E = S ∩ A(F) ∈ stbC(F). If now E /∈ stbC(G) or A(F )\C ̸= A(G)\C, we are done, i.e., condition (1) or (2) is already violated. So suppose E ∈ stbC(G), and A(F ) \ C = A(G) \ C. We have to show E+ F \C ̸= E+ G \C. Recall that S /∈ stb(G ∪ H). Since E ∈ stbC(G) there exists an a ∈ A(G ∪ H) \ C not attacked by S in G ∪ H, thus in particular a /∈ E+ G . Since S does not attack a via H and S ∈ stb(F ∪ H) we conclude that either a ∈ E+ F or a /∈ A(F). However, since a /∈ C and A(F)\C = A(G)\C, it follows that a ∈ E+ F , thus violating (3).

Example 4.9. Recall F from Example 4.2 and let F ′ = F G ab ∪({a, d, e}, {(a, e), (e, e), (e, d)}), i.e. instead of the cycle through a, b, c, we have just two arguments a, b where a attacks itself and b. For C = {a, b, c}, it is easily checked that F and F ′ satisfy all three conditions, i.e., we have F ≡stb C F ′ . In fact, even for the AF F ′′ = ({a, b, d, e}, {(a, a), (a, e), (e, e), (e, d)}), i.e., F ′ without the attack from a to b, F ≡stb C F ′′ holds.

If we had C = {a, b}, condition (1) would be violated; indeed F ̸≡stb C F ′ is then witnessed by adding H = ({c, e, t}, {(t, e)}), as stb(F∪H) = {{t, d, b}} and stb(F ′∪H) = {{t, d, b, c}}. On the other hand, for C = {a, b, c}, the role of b and c is indeed different: if we use in F ′ argument c instead of b, we have stbC(F ′ ) = {{d, c}}; thus condition (2) would be violated. Finally, consider F ′′′ given by F ′ plus an additional attack (b, e). Note that we still have stbC(F ′′′ ) = {{d, b}}, but now E+ F \ C ̸= E+ F ′′′ \ C, hence condition (3) is violated here. Even without expanding the AFs, we obtain different stable extensions, i.e., stb(F) = ∅ while stb(F ′′′ ) = {{d, b}}. ♦

When considering C = ∅ the above characterization boils down to (1) A(F) = A(G), (2) cf (F) = cf (G) and (3) for all E ∈ cf (F), E+ F = E+ G . That is, the two AFs F and G have to coincide except for attacks from self-attacking arguments, i.e., we end up with the concept of stable kernels from [Oikarinen and Woltran, 2011], which characterize strong equivalence for stb. For C = A(F ∪ G), only condition (2) remains which is equivalent to stb(F) = stb(G). Similar observations can be made for the forthcoming results.

Admissible Semantics. For adm semanticswe have the additional condition that for each E ∈ admC(F) the attackers of E that are not already attacked by E coincide in F and G.

Theorem 4.10. Let F, G be AFs and C ⊆ U. Then, F ≡adm C G iff the following conditions jointly hold: (1) A(F) \ C = A(G) \ C; (2) admC(F) = admC(G); and (3) for all E ∈ admC(F), (3a) E+ F \ C = E+ G \ C and (3b) EF \ E+ F = EG \ E+ G .

Example 4.11. Let us first consider F, F ′ , and F ′′ from Example 4.9, again with C = {a, b, c}. It can be shown that all three conditions then hold, i.e., F ≡adm C F ′ . However, F ′′ is a too drastic simplification for admissible semantics, since {b} ∈ admC(F ′′ ) but {b} /∈ admC(F).

To show the role of condition (3b), consider the AFs F1 = F ∪ ({g}, {(g, g)}) and F2 = F ∪ ({g, b}, {(g, g), (g, b)}); conditions (1), (2), and (3a) are fulfilled. However, for E = {d, b} ∈ admC(F1), we have EF1 \E+ F1 = {e}, while EF2 \ E+ F2 = {e, g}. Hence condition (3b) is violated, witnessed by the expansion H = ({t, e}, {(t, e)}), which yields {t, d, b} ∈ adm(F1 ∪H), but {t, d, b} /∈ adm(F2 ∪H). ♦

Preferred Semantics. The characterization for prf is very much like for adm, the only difference being that one considers prf C(·) instead of admC(·). This similarity reflects the fact that F ≡prf C Gwhenever F ≡adm C G.

Theorem 4.12. Let F, G be AFs and C ⊆ U. Then, F ≡prf C G iff the following conditions jointly hold: (1) A(F) \ C = A(G) \ C; (2) prf C(F) = prf C(G); and (3) for all E ∈ prf C(F), (3a) E+ F \ C = E+ G \ C and (3b) EF \ E+ F = EG \ E+ G .

Table 1: Complexity of C-relativized Equivalence.

Complete Semantics. For com semantics we have all the conditions we had for adm, but also the additional condition (3c) that ensures that the same arguments are defended in F ∪ H and G ∪ H, for all AFs H over U \ C.

Theorem 4.13. Let F, G be AFs and C ⊆ U. Then, F ≡com C G iff the following conditions jointly hold: (1) A(F) \ C = A(G) \ C; (2) comC(F) = comC(G); and (3) for all E ∈ comC(F), (3a) E+ F \C = E+ G \C, (3b) EF \E+ F = EG \E+ G , and (3c) for all S with EF \ E+ F ⊆ S ⊆ A(F) \ (C ∪ E), if FF\S(E) ∩ C = E ∩ C or FG\S(E) ∩ C = E ∩ C then FF\S(E) = FG\S(E).

Grounded Semantics. For the characterization of grd we make use of the following variant of the characteristic function, FF,E (S) = {a∈E | S defends a in F} for E ⊆ A(F).

Theorem 4.14. Let F,G be AFs and C ⊆ U. Then, F ≡grd C G iff the following holds: (1) A(F)\C = A(G)\C; (2) grdC(F) = grdC(G); and (3) for all E ∈ grdC(F) and all S ⊆ A(F)\(C∪E) (3a) F ∞ F\S,E∪C (∅) = F ∞ G\S,E∪C (∅), (3b) if F ∞ F\S,E∪C (∅) = E then E+ F \(C∪S) = E+ G \(C ∪S), and (3c) if F ∞ F\S,E∪C (∅) = E then FF\S(E) = FG\S(E).

Conflict-free and Naive Semantics. Notice that two AFs possess the same conflict-free sets iff they possess the same naive extensions and thus ≡cf C and ≡naive C coincide. Moreover, the C-restricted semantics of cf is just cf itself.

Theorem 4.15. Let F,G be AFs and C ⊆ U. Then, F ≡cf C G (F ≡naive C G) iff the following conditions jointly hold: (1) cf (F ) = cf (G) and (2) A(F ) \ C = A(G) \ C.

5 Computational Properties

While strong equivalence can be efficiently decided (cf. [Oikarinen and Woltran, 2011]), testing standard equivalence is coNP-hard for σ ∈ {stb, adm, prf , com} as it generalizes the problem of deciding whether an AF has a (non-empty) extension [Dunne and Wooldridge, 2009]. These hardness results extend to C-relativized equivalence. Upper bounds are given by the characterizations presented in Section 4.2. Our complexity results are summarized in Table 1 (C-c. stands for C-complete). Grounded semantics has a special behavior: while both standard and strong equivalence are tractable, Crelativized equivalence is coNP-complete as we show next.

Proof. The membership in coNP is due the characterization in Thm. 4.14. coNP-hardness is by a reduction from deciding whether two CNF formulas are equivalent. Let ϕ and ψ be two CNF formulas over atoms X and let Cϕ, Cψ be the sets of clauses. Moreover, we can assume that ϕ and ψ do not have partial models. For a CNF formula φ with clauses Cφ we define the AF Fφ = (A, R) with A = X ∪ ¯X ∪ Cφ ∪ {t} and R = {(c, t), (c, c) | c ∈ Cφ}∪{(x, ¯x), (¯x, x) | x ∈ X} ∪ {(x, c) | x ∈ c ∈ Cφ} ∪ {(¯x, c) | ¬x ∈ c ∈ Cφ}. We now have that ϕ ≡ ψ iff Fϕ ≡grd C Fψ for C = Cϕ∪Cψ∪{t}.

It remains to show ΠP2 -hardness of F ≡prf C G. We prove the result for F ≡prf G by reduction from the ΠP2 -complete problem of deciding whether an AF F is coherent [Dunne and Bench-Capon, 2002], i.e., whether stb(F) = prf (F).

Proof. Membership in ΠP2 follows from Thm. 4.12. We show hardness for testing F ≡prf G (a corner case of F ≡prf C G) by a reduction from the problem of testing whether an AF F is coherent, where we can assume that ∅ /∈prf (F). We transform F to an AF F ′ = (A′ , R′ ) with A′ = A(F) ∪ {t} and R′ = R(F) ∪{(t, a), (a, t) | a ∈ A(F)}, yielding stb(F ′ ) = stb(F) ∪ {{t}} and prf (F ′ ) = prf (F) ∪ {{t}}. That is, F ′ is coherent iff F is coherent but we have stb(F ′ ) ̸=∅. Now we can apply Translation 4 from [Dvoˇr´ak and Woltran, 2011] which maps F ′ to an AF G such that stb(F ′ ) = prf (G) (given that stb(F ′ ) ̸= ∅) and can be efficiently computed. Hence stb(F) = prf (F) iff prf (F ′ ) = prf (G).

Recall that for C = ∅, testing ≡σC equivalence is computationally easy, while it is hard in the general case. Thus, one promising approach towards practical feasible algorithms is to consider characterizations whose performance depends on the set C. In other words, given AFs F and G to be compared under ≡σC , we aim to restrict the comparison of the C-restricted extensions (which is indeed the most expensive test in all characterizations). We give a first result into that direction for stable semantics. Let F be an AF and B, E ⊆ U. We define the stable reduct of F w.r.t. E and B as the AF F ∗B,E = (A(F) \ E⊕ F ,R∗ ) with R∗ = {(a, b) ∈ R(F) | a, b ∈ A(F ) \ E⊕ F } ∪ {(a, a) | a ∈ (A(F ) ∩ B) \ E⊕ F }.

Theorem 5.3. Let F,G be AFs, C ⊆ A(F ∪ G), and B = C ⊕ F∪G ∪ C - F∪G. Then, F ≡stb C G iff the following conditions jointly hold: (1) if stbC(F ∩B) ̸= ∅, A(F) \C = A(G) \C; (2) stbC(F ∩ B) = stbC(G ∩ B); and (3) for all E ∈ stbC(F ∩ B), F ∗B,E ≡stb S G∗B,E .

In the above characterization the number of C-restricted sets we have to consider in (1) and (2) does not depend on the number of total arguments but only on the number of arguments that are either in C ∩ A(F ∪G) or neighbors of such arguments. Moreover, the strong equivalence in (3) can be tested in polynomial time.

6 Simplifications

We come back to the issue of simplification raised in the introduction. We begin by defining the notion of replacement.

Definition 6.1. Given AFs F, F ′ ,G such that A(F ′ ) ⊆ A(F) ∪ (U \ A(G)) and F is a sub-AF of G (i.e., A(F) ⊆ A(G) and R(F ) = R(G)∩(A(F )×A(F ))), let A = (A(G)\ A(F)) ∪A(F ′ ). The replacement of F by F ′ in G is defined as G[F/F ′ ] = (A, ((R(G) \ R(F )) ∩ (A × A)) ∪ R(F ′ )).

As it turns out, faithfulness of the replacement of a sub-AF by another within a larger AF G follows from C-relativized equivalence of the the sub-AFs conjoined with their immediate neighborhood in G.

Proposition 6.2. For AFs F, F ′ ,G and C ⊆ U such that A(F )∪A(F ′ ) ⊆ C, (A(G)\A(F ))∩C = ∅, and F a sub-AF of G, let B = (A(F))⊕G ∪ (A(F))-G and F G = (B, R(G) ∩ (B×B)). Then, F G ≡σC F G[F/F ′ ] implies G ≡σ G[F/F ′ ].

A key feature of Def. 6.1 is that the attacks connecting the AFs F and F ′ to G are not changed, unless the involved argument in F is removed in F ′ (then the attack is also removed). Therefore the condition for C-relativized equivalence boils down to stbC(F G) = stbC(F G[F/F ′ ]), since the other conditions from Thm. 4.8 are trivially satisfied (similar observations can be given for the other semantics).

Example 6.3. Recalling the introductory example, faithfulness of replacing Fabc by Fab in an arbitrary larger AF G being connected to Fabc by an attack (d, a) (cf. Figure 1), is then verified by stbC(F G abc ) = {{d, b}} = stbC(F G ab ). In other words we have that cycles of length 3 can be simplified under the stable semantics to two arguments, whenever the cycle has exactly one incoming attack. This kind of simplification can be generalized to arbitrary odd-length cycles in C, allowing for potential deletion of several arguments. ♦

The replacement of sub-AFs with fixed connections to the rest-AF is a particular application of the results of Section 4.2. The notion of C-relativized equivalence is, however, more general and gives rise to simplifications of the following kind.

Example 6.4. Consider the AFs G and G′ depicted below.

Note the single strongly connected component in G is split into three (smaller) components in G′ . Let F, F ′ be the subAFs of G, G′ with arguments {a, b, c, d, e}. To prove G ≡stb G′ we show F ≡stb C F ′ for C = {b, c}: (1) A(F) \ C = {a, d, e}=A(F ′ ) \ C, (2) stbC(F)={{a, c}, {b}, {b, d}} = stbC(F ′ ), and (3) {a, c}+F \ C = {d, e} = {a, c}+F ′ \ C, {b}+F \C = ∅ = {b}+F ′ \C, {b, d}+F \C = {e} = {b, d}+F ′ \C. Again, this result can be generalized to arbitrary even-length paths among arguments in C. ♦

7 RelatedWork

Strong equivalence as well as further related notions have been thoroughly studied in the literature (cf. [Baumann, 2014; Baumann and Brewka, 2015; Baumann and Woltran, 2016]). Almost all of these notions are somehow disappointing regarding potential space for simplification. In fact, for most of these notions no arguments are redundant and deletions of attacks rely on the presence of self-loops. In particular, in case of self-loop-free AFs nothing can be simplified.

The concept of restricted admissible and stable semantics has been considered in dynamic programming algorithms based on tree-decompositions [Dvoˇr´ak et al., 2012; Charwat, 2012]. An investigation on the amount of neighborhood (in a graph-theoretical sense) needed to verify acceptability for different semantics is [Baumann et al., 2016].

The issue of local evaluation of AFs was also tackled in the work on input/output AFs [Baroni et al., 2014a; Giacomin et al., 2016]. There the behavior of AFs (with dedicated input- and output-arguments) is described by the possible valuations of the output-arguments for each possible input. For the most prominent semantics it is shown whether having the same I/O behavior is sufficient for replacing one AF by another without affecting the evaluation of the rest of the AF. Our notion of equivalence is stronger as it is w.r.t. the whole AF and not only the part not affected by the replacement. Moreover, our work differs as we do not explicitly model I/O arguments and are more focused on finding exact conditions for the faithfulness of replacements.

The works on splitting [Baumann, 2011; Baroni et al., 2014b] and SCC-recursiveness [Baroni et al., 2005] allow for local evaluations but require that strongly connected components are considered in a specific order. Baumann et al. [2012] relaxed these conditions for stable semantics.

The concept of relativized equivalence was also studied for other nonmonotonic formalisms, in particular for Answer-Set Programming, see e.g. [Eiter et al., 2007]. As well, simplification strategies have been suggested on basis of equivalence notions. Such replacements are typically defined as an exchange of rules in a logic program. This already indicates the main difference to our work, since replacing sub-graphs in AFs provides some subtle issues to be taken into consideration (cf. Section 6). This also might explain why in abstract argumentation the relation between equivalence notions and simplifications has been underexplored so far.

8 Discussion

In this paper, we introduced a general notion of equivalence for AFs and studied their characterizations and complexity. There are several ways to pursue the presented research. First, an inclusion of other extension-based and labellingbased semantics is an immediate objective. Another direction to consider are weaker versions of C-relativized equivalence, for instance in analogy to normal expansion equivalence [Baumann, 2012], altering Def. 3.3 such that attacks between the original arguments of F and G cannot be changed. This situation is typical in the instantiation-based context (where AFs are constructed from an underlying knowledge base) since usually one can decide whether there is a conflict between arguments by solely considering these arguments.

On the practical side, we plan to employ our notion of equivalence for a systematic investigation of possible simplifications and to implement these findings in a preprocessing tool for abstract argumentation systems.

Finally, we plan to study restricted equivalence in the general setting of graph problems (as it was already done for strong equivalence by Lonc and Truszczy´nski [2011]) which might yield results that go beyond the field of argumentation.