A recurring notion in the abstract argumentation community is that of collective attacks, whereby a set of arguments, rather than a single one, attacks another argument. The resulting frameworks capturing this phenomenon are referred to as SETAFs. Given the possibility of facing an exponential runtime in the size of the framework, techniques have been presented to compute extensions of a given framework incrementally, i.e. restricting the search space to sub-frameworks only, and then combining the obtained results. Existing research has primarily focused on approaches based on SCC-recursiveness, where SETAFs are evaluated along their strongly connected components (SCCs) using generalized semantics and dedicated algorithms. Splitting approaches are more general in this regard, as they do not have to consider SCCs individually and can be used on top of arbitrary argumentation solvers. Splitting techniques have been successfully applied in abstract argumentation but have been neglected for SETAFs so far. Towards lling this gap our work investigates the concept of (modi cation-based) splitting for SETAFs. We show that a splitting-based approach is possible for common semantics (such as admissible, complete, grounded, preferred, and stable), generalizing corresponding results of AFs, which can be seen as a restricted class of SETAFs. Along the way, we point out intricate details that are obvious or trivial for AFs, but help us to understand the underlying ideas in greater detail than before.
Most argumentation problems are intractable in general, which means even the best-known
methods for solving these problems oftentimes cannot avoid exploring the whole exponential
size solution-space. The fewer arguments we have to consider for each problem, the more
e cient an approach can be in general, which is why in the setting of abstract argumentation
(see [
Similar to the structure of Baumann [
In this section, we recall the de nition of argumentation frameworks with collective attacks
(SETAFs) [
The fundamental notions of con ict and defense from Dung-style AFs naturally generalize to SETAFs. These notions are the basis for the semantics we investigate in this paper. De nition 2. Let SF = (A, R) be a SETAF. A set S ✓ A is con icting in SF if S attacks a for some a 2 S. S ✓ A is con ict-free in SF , if S is not con icting inSF , i.e. if T [ { h} 6✓ S for each (T, h) 2 R. cf(SF ) denotes the set of all con ict-free sets inSF . An argument a 2 A is defended (in SF ) by a set S ✓ A if for each B ✓ A, such that B attacks a, also S attacks B in SF . A set T ✓ A is defended (in SF ) by S if each a 2 T is defended by S (in SF ).
The semantics we study in this work are the admissible, complete, grounded, preferred, and
stable semantics, which we will abbreviate by adm, com, grd, pref, and stb, respectively [
The relationship between the semantics has been clari ed in [
stb(SF ) ✓ pref(SF ) ✓ com(SF ) ✓ adm(SF ) ✓ cf(SF )
We now recall Baumann’s splitting approach for AFs [
De nition 4. Let F = (A, R) be an AF, F1 = (A1, R1) and F2 = (A2, R2) two sub-frameworks of SF s.t. A1 \ A2 = ; , A = A1 [ A2 and R = R1 [ R2 [ R3 with R3 ✓ A1 ⇥ A2. We call the triple (F1, F2, R3) a splitting of F . For such a splitting the (E, R3)-reduct w.r.t. E ✓ A1 is the AF AF 0 = (A0, R0) with A0 = A2 \ ER+3 and R0 = R2 \ (A0 ⇥ A0). The set of undecided arguments w.r.t. E ✓ A1 is de ned asUE = A1 \ ER1 .
We will later generalize the notion of the reduct to be applicable in the context of SETAFs. De nition 5. Let (F1, F2, R3) be a splitting for an AF F and E an extension of F1. Moreover, take F20 = (A02, R20) as the (E, R3)-reduct of F2 and UE as the set of undecided arguments w.r.t. E. The (UE, R3)-modi cation ofF2 is de ned asmodUE,R3 (F20) = (A02, R20 [ { (b, b) | 9 a 2 UE : (a, b) 2 R3}).
It is easy to see that the de nition of the modi cation does not actually rely on the
undecided arguments, but rather uses the arguments as means to obtain the links which stem
from undecided arguments. Later on, we will make use of this fact to simplify the respective
notions. Baumann [
Theorem 6 ([
(F ). (F1) and E \ A2 2 (modUE,R3 (F20)).
In this section, we introduce fundamental ideas for de ning divide and conquer algorithms
based on splitting in the presence of collective attacks. As a starting point, we generalize the
notion of splitting introduced by Baumann [
De nition 7. Let SF = (A, R) be a SETAF, SF1 = (A1, R1) and SF2 = (A2, R2) two sub-frameworks of SF such that A1 \ A2 = ; , A = A1 [ A2 and R = R1 [ R2 [ R3 with R3 ✓ (2A1 \ {;} ) [ 2A2 ⇥ A2. We call a splitting of SF the triple (SF1, SF2, R3). Moreover, we say that R3 is the set of links of the splitting (SF1, SF2, R3).
In a nutshell, we investigate a large SETAF SF that has two sub-frameworks SF1 and SF2 with attacks within themselves, and attacks R3 that stem from A1 (at least in part) and target only arguments in SF2. The general idea is to compute extensions of SF1 and SF2, which combined give us extensions of SF . Due to the links from SF1 to SF2 we have to modify SF2 according to the extension(s) of SF1 to account for the prior accepted and rejected arguments.
We take here into account SETAF splittings where the whole tail of the links is separated from
the respective heads. Notice that, whereas these are indeed straightforward generalizations of
AF splittings [
A1 = {a, b, c, d} R1 = {(a, a), (a, b), (c, d), (d, c), (c, a)} A2 = {e, f, g} R2 = {(e, f ), (f, e), ({e, f }, g)} R3 = {({b, d}, e), (d, f )} One can verify that SF1 has two preferred extensions: E1 = {b, c} and E2 = {d}. Let us rst consider E1. Since d is defeated in SF1 we can argue that the links (i.e., attacks in R3) do not at all a ect the arguments inSF2, and we can just evaluate SF2 “as is” to obtain the extensions E1,1 = {e, g} and E1,2 = {f, g}. We can combine the extensions from SF1 and SF2 to obtain {b, c, e, g} and {b, c, f, g}, which are indeed preferred extensions of SF . Now on the other hand if we consider E2, it is non-trivial how this a ectsSF2: while f is defeated by d, e is targeted by an attack from the accepted argument d and the argument b, which in SF1 is neither accepted nor outright rejected by E2. In the following, we will argue how to properly deal with these cases and introduce a splitting method that correctly characterizes all extensions.
In the example above we can see that the status of the arguments in SF1 w.r.t. the extension of SF1 we investigate determines whether and how the arguments in SF2 are a ected. Indeed, in the AF case the status of the single argument in the tail of a link solely determines whether the head is removed or not from the second sub-framework, or whether a self-attack is added to it (c.f. De nitions 4 and 5). Similarly for SETAFs, it is possible to distinguish three di erent scenarios for the status of the arguments in A1 after evaluating SF1, corresponding to the cases where the argument is accepted (i.e., in an extension E1 2 (SF1)), defeated (in (E1)R+1 ) or undecided (in A1 \ (E1)R1 ). Note however, that while on AFs the status of a link and its one tail argument coincide, for SETAFs links (like any other attack) can have multiple tail arguments. Hence, the status of a link (T , h) 2 R3 of a splitting (SF1, SF2, R3) can be determined after evaluating SF1 as follows: (i) all of the arguments in the tail of a link (that are also in SF1) are accepted (i.e., in an extension E1 2 (SF1)), (ii) at least one argument in the tail of a link is + defeated by E1 (in (E1)R1[ R3 ) or (iii) no argument is defeated but at least one is undecided (in A1 \ ER1 ). In what follows, we consider cases (i)-(iii) separately and show an intuition on how these need to be treated. We start with (i) in the Example 9, depicting a situation where the attack ({x, y}, z) is in. As one can see, in certain circumstances the above de nition of a splitting corresponds to a straightforward generalization of the AF case.
Example 9. Consider the AF F (left), and the SETAF SF (right) with its splitting (SF1, SF2, R3).
a
b
c
v
w
x
y
z
We look at the preferred extensions {a} for the rst part ofF , and see that b in the second part is
defeated. Thus, by the approach of [
Analogously, we have {v, w} as a preferred extension in SF1. Hence, we remove x from SF2 to obtain the modi ed frameworkSF ?. As in the AF case, any outgoing attack from x (no matter if 2 other arguments are in the tail, like y in our case) cannot a ect their targeted argument (z), as z is defended against this attack. Hence, we remove the entire attack and obtain SF2? = ({y, z}, ; ) which trivially yields {y, z} as its preferred extension. As a result, one gets {v, w} [ { y, z} as a preferred extension for SF .
We next discuss case (ii) for the status of a link in Example 10 below.
Example 10. For the SETAF SF below, we identify the preferred extension {w, y} in the rst part (i.e., {w, y} 2 pref(SF1)). Given that w 2 E, we get that x is defeated, which means the link ({x, y}, z) can be seen as out. Intuitively, z needs no more counter-attack for this incoming attack— since x is already defeated. For this reason, such an attack does not a ect the modi cation ofSF2. Hence, the modi edSF2? is as depicted on the right, preserving z as an acceptable argument. Note also that any possible outgoing attacks of z remain untouched. We thus have {w, y} 2 pref(SF1) and {z} 2 pref(SF ?) as preferred extensions of SF1 and SF2?, respectively. It is easy to see that 2 {w, y} [ { z} is a preferred extension of SF .
w x y z w x y
Di erent considerations are due whenever the original SETAF contains a link which is undecided, corresponding to case (iii).
Example 11. Consider the SETAF SF displayed below (left) and E = {y} 2 pref(SF1). x is undecided w.r.t. E, i.e., x 2 A1 \ ER1 . This makes the status of ({x, y}, z) undecided as well, enforcing a modi cation of the right part of the SETAF. Analogous to the approach for AFs, we add a self-attack on z, obtaining SF2? = ({z}, {(z, z)}) (right). Intuitively, this models the fact that z cannot be accepted in SF2?, since there is at least one attack that z is not defended against. On the other hand, z is not rejected, i.e., if z were to attack other arguments in SF2 they need defence against z. Hence, we cannot outright remove z as in case (ii). In this situation, one gets ; 2 pref(SF2?). Hence, {y} [ ; is a preferred extension of SF .
x y z x y z z
Examples 9, 10, and 11 above display only a special case of splitting for SETAFs, where the whole tail of an attack is separated from its target. Hence, as of now performing splittingbased techniques in the presence of collective attacks represents an easy and straightforward generalization of its AF counterpart. This stems from the fact that modi cation is only slightly impacted by the presence of multiple arguments in the tail of a link. Consequently, minor adjustments are needed to handle such situations. However, due to their rich syntax, SETAFs allow for another possible way to separate an attack via splitting. In the following, we consider SETAF splittings in full generality.
The enriched syntax of SETAFs allows us to take into account splittings that separate arguments taking part in the same collective attack. In particular, it is possible to split a SETAF in such a way that two parts of the same tail of a link end up being in di erent sub-frameworks. This is captured by the possibility of having R3 ✓ (2A1 \ {;} ) [ 2A2 ⇥ A2 as for our De nition 7. We investigate such scenarios in connection with the cases (i)-(iii) as before. Note however that we need to consider the cases more carefully, as we now also consider links (T , h) 2 R3 where the tail T is spread over both A1 and A2. More formally we call a link (T , h) 2 R3:
ER+1[ R3 and 8 a 2 T \ A1, a 2
ER+1[ R3 or
E, ER+1[ R3 and 9 a 2 T \ A1 s.t. a 2
A \ ER1 .
We again give the necessary intuitions for each case, starting with (i).
Example 12. For the below SETAF SF (left), we consider {x} 2 adm(SF1). Therefore, intuitively it is the remaining part of the attack stemming from y that is decisive for the status of the target argument z. Since x is accepted, it su ces for the success of the attack ({x, y}, z) to consider the status of y alone. Therefore, one can solely consider the remaining part of the attack in SF2. Resulting from this, we obtain SF2? = ({y, z}, {(y, z)}) (right). Given that {y} 2 adm(SF2?), we retrieve {x} [ { y} as an admissible set of SF .
x y z x y z
More generally, given a set of arguments E which is accepted in SF1, the success of any link (T , h) 2 R3 where T \ A1 ✓ E is dependent only on the status of T \ E in SF2. Opposite considerations can be made when arguments in the links’ tails are defeated (case (ii)). Example 13. Consider the following SETAF SF (left) with E = {w} 2 adm(SF1). As in Example 10, the argument w 2 E attacks part of the link’s tail (i.e. x), thereby neutralizing the collective attack ({x, y}, z). As a result, w is compatible with both y and z. More formally, the rightmost part of SF is modi ed to obtainSF2? = ({y, z}, ; ) (middle). Indeed, their setunion {w} [ { y, z} is an admissible set of SF . Note that this case (ii) can also occur via a link. Consider the splitting for the SETAF SF † (right) where {a, b} is a preferred extension in the left sub-framework. Since a defeats c, the link ({b, c}, d)) has to be deleted in the modi ed framework, even though all tail-arguments of the link within A1 (i.e., in our case b) are accepted. w x y z w x y z a b c d
As before, we can directly exploit (ii) in order to guide the modi cation of SF2 to get extensions for the whole SETAF. It is however less straightforward to nd a correct modi cation for case (iii), where a link is undecided due to what happens in SF1.
Example 14. For SF (left), we have E = ; 2 adm(SF1) which means x 2 A1 \ ER1 , i.e., the link ({x, y}, z) is undecided. By naively applying the same technique as in the AF case (see Example 11), we make z self-attacking. However, it is not immediately clear whether one should modify SF2 to include (y, z) 2 R2? or not. It turns out that both options, i.e., (a) including (y, z), and (b) not including (y, z) both lead to an undesired result.
We see that {v} is admissible in both case (a) and (b). However, the additional self-loop (z, z) resulting from modi cation makesz not acceptable in both cases. This is in contrast with the fact that ; [ { v, z} is indeed an admissible extension of SF . x y z v w x y z
v (a) w x y z
v (b) w
We see that a naive generalization of the AF approach, where we blindly make those arguments that are attacked by an undecided attack self-attacking, does not work as intended. In contrast to the AF case, these attacks can still be counter-attacked if in the second part of the framework an argument of the tail is attacked—as is the case in Example 14 where y is defeated by v. In this situation, z should remain acceptable. In particular, we have to ensure that (1) {z} is con ict-free in the modi ed SF2?, and (2) z can only be accepted if the remaining part of the attack ({x, y}, z) is counter-attacked (e.g., in Example 14, if y is attacked). In fact, being out, the attack (y, z) is too weak and gets overwritten by the undec self-loop over z, thereby letting the status of z be entirely dependent on that of x. This is in opposition to what happens in the original SETAF, where the acceptance of z depends on the fact that y is defeated.
In order to present a splitting-based algorithm that works in a truly incremental and modular
fashion, we consider a possible modi cation that is intermediate between adding an attack
or not. For this, we have to make sure that the remaining part of the link is not “powerful”
enough to actually defeat z—while at the same time indicating a need for z to defend against
the remaining part of the attack. In the SCC-recursive schema for SETAFS [
Example 15. Contrary to the idea of mitigated attacks discussed before, we do not need labeling for attacks in this scenario. Instead, we add a dummy argument ⇤ for the undecided attack ({x, y}, z) such that ⇤ is self-attacking and attacks z together with y (via the attack ({⇤ , y}, z)). x y z w x y z ⇤ w Modifying the second part of the framework in this way successfully neutralizes the acceptance of w, which is now faced by an undecided attack. Notably, the second part of the framework is identical to the whole SETAF prior to modi cation.
Such an addition can result in augmenting the number of arguments and attacks in the rightmost part of the framework. More importantly, such an unwanted outcome can be easily avoided. In fact, we can employ the very same target argument to do the job that was previously done by the dummy argument. As a consequence, the dummy argument becomes obsolete, and the modi ed attack collapses onto one singular (set)-self-attack on the target, as the next example illustrates.
Example 16. As a nal strategy we introduce a more concise and elegant modi cation of the second part of the framework at hand. Instead of using a dummy argument to make the attack towards z undecided, we choose to use z itself. This way, we obtain the expected result without creating a duplicate of x in the second part of the framework. This means, to account for the attack ({x, y}, z) with the undecided argument x in the original framework (left), we introduce in the modi cation the attack({y, z}, z) which is a “set-self-attack” (right). Note that z is not a classic “self-attacker” as in the AF-case, since we do not introduce an attack (z, z).
x y z w x
w y z In the modi cation (right), the attack({z, y}, z) can never defeat its head z (since its con icting tail {y, z} would have to be accepted). Since z is not defeated, it is undecided, which carries over to w via the unaltered attack (z, w). This yields the admissible set ; [ { y} as desired.
As a sanity check, note that this is indeed a generalization of the AF modi cation. In fact, for attacks (T, h) with |T | = 1, e.g. for (T, h) = ({t}, h), we have T \ {t} = ; . Thus, we add the self-attack (; [ { t}, t) which is the attack (t, t).
In this section, we introduce the formal de nitions that are needed to prove the correctness of
our proposed splitting-based algorithm. Following Baumann [
Hence, after computing an extension E1 in SF1, we obtain the reduct of SF2 w.r.t. E1 (i.e., SF20) as follows:
+ which are defeated by E1, together with their in1. We remove the arguments a 2 (E1)R3 and outgoing attacks, which we realize by only keeping those attacks from R2 which are completely within the new set of arguments A02 (as in the original approach of Baumann), 2. we add the remaining part T \ A02 of a link (T, h) 2 R3 if the tail arguments in T \ A1 are all in E1 and no tail argument t 2 T is defeated via R3 (as showcased in Example 12), given that there are any tail-arguments left in SF2 (i.e., T \ A02 6= ; ).
This allows us to retain all the information concerning defeated arguments and in attacks of SF1. Formally this translates to the following notion of reduct (which we illustrate in Example 20): De nition 17 (Reduct). Let (SF1, SF2, R3) be a splitting for a SETAF SF . We de ne the (E1, R3)-reduct (or simply reduct) of SF2 for some extension E1 of SF1 as the SETAF SF20 = + (A02, R20) where, A02 = {a 2 A2 | a 2 / (E1)R3 } and
R20 ={(T, h) 2 R2 | T ✓ A02, h 2 A02} [
{(T \ A02, h) | (T, h) 2 R3, T \ A02 6= ; , h 2 A02, T \ A1 ✓ E1, T \ (E1)R+3 = ;} We have argued throughout this paper that in fact, when dealing with undecidedness, what guided our intuition towards a certain modi cation is not the status of the arguments in SF1, but rather the status of the links (corresponding to cases (i)-(iii)). In fact, if we closely examine De nition 5 we can see that even in the AF case we add self-attacks to those arguments that are targeted by an undecided link—the set UE of undecided arguments is merely a tool to formally obtain those links. In the context of SETAFs, where an attack is not associated to exactly one attacker, this becomes even more evident. Hence, we decide to slightly tweak the de nition to omit such detour, and base our notion solely on the undecided links.
De nition 18 (Undecided Links). Given a splitting (SF1, SF2, R3) for a SETAF SF and an extension E1 2 SF1 we de ne theset of undecided links w.r.t. E1 as:
URE31 = {(T, h) 2 R3 | T \ (E1)R1[ R3 = ; and 9 t 2 T : t 2 A1 \ (E1)R1 }
+
In what follows, we de ne the modi cation, which is applied on the reduct, and accounts for the e ects of the undecided links. In particular, for each undecided link, we add to the targeted argument a (set-)self-attack incorporating the remaining part of the link (as intuitively explained in Example 16).
De nition 19 (Modi cation). Let (SF1, SF2, R3) be a splitting for a SETAF SF and E1 an extension of SF1. Take SF20 as the (E1, R3)-reduct of SF2 and URE31 as the set of undecided links w.r.t. E1. We denote with modER13 (SF20) the URE31 -modi cation (or simply modi cation) ofSF20 s.t.: modER13 (SF20) = (A02, R20 [ { ((T \ A02) [ { h}, h) | (T, h) 2 URE31 , h 2 A02})
Before we present the main result of this paper we want to illustrate De nitions 17–19 in the following example, while covering many interesting cases at once.
Example 20. In (a) we have a new SETAF SF with a splitting that separates the arguments A1 = {a, b, c, d} from A2 = {v, w, x, y, z}. We see that E1 = {c} is admissible in the left part of the splitting. In (b) we see the reduct w.r.t. the set {c}, where a and d are defeated by c (as {c}R+1 = {a, d}) and b is undecided. This reduct contains from the right part all arguments except z, which is defeated by c (as {c}R+3 = {z}). We see that most attacks are removed from the right part, but (x, w) persists (since it is in R2 and all involved arguments remain), and the attack ({c, y}, x) is changed to (y, x). The attack ({b, z}, y) is removed since z is defeated. The attack ({b, w}, v) is also removed, as b is undecided (i.e., {b, w} \ A1 * E1). However, in (c) we see that the latter case is important for the modi cation: the attack({b, w}, v) is an undecided link, which means in the modi cation we introduce the attack({v, w}, v). For the right part of the splitting we see that {y, w} is admissible, and obtain {c, y, w} as an admissible set for SF . a c b d
v x y w z a c b d
v x y w z a c b d
v x y w z (a) SETAF SF (b) ({c}, R3)-reduct (c) UR{c3}-modi cation Note that in the rst step, for the left part of the splitting, instead of the set{c} we could also investigate the admissible sets ; , {a}, or {a, d}, which result in di erent reducts and modi cations.
Having these notions at hand, we now establish the adequacy of our splitting technique for SETAFs. We start by establishing that (a) con ict-freeness of the sub-frameworks SF1 and SF2 carries over to the whole SETAF SF , and (b) con ict-free sets of SF induce con ict-free subsets in SF1 and SF20.
Proposition 21. Let (SF1, SF2, R3) be a splitting for a SETAF SF = (A, R) with SF1 = (A1, R1) and SF2 = (A2, R2). Let SF2? = modER13 (SF20).
1. If E1 2 cf(SF1) and E2 2 cf(SF2?), then E1 [ E2 2 cf(SF ).
2. If E 2 cf(SF ), then E \ A1 2 cf(SF1) and E \ A2 2 cf(SF20).
Proof. (1.) We need to show for each (T, h) 2 R1 [ R2 [ R3 that T [ { h} * E = E1 [ E2. Let SF20 = (A02, R20) and SF2? = (A?2, R2?). If (T, h) 2 R1 we immediately get T [ { h} * E, since we know E1 is con ict-free in SF1. For (T, h) 2 R2 there are two cases: either (a) the attack is removed when we construct the reduct or (b) the attack remains, i.e., (T, h) in SF2?. + Case (a) happens if some a 2 T [ { h} is attacked by E1, i.e., (T [ { h}) \ (E1)R1[ R3 6= ; . Then at least one argument a 2 T [ { h} of the attack does not occur in the modi cation (i.e., (T [ { h}) * A?2), and since we assume E2 2 cf(SF2?) we know E2 ✓ A?2. Hence we obtain T [ { h} * E. For case (b) we get from E2 2 cf(SF ?) that at least one argument a 2 T [ { h} is not in E2, which also means T [ { h} * E. Finally, for (T, h) 2 R3 we again consider two cases: (a) T \ A1 ✓ E1, and (b) T \ A1 * E1. For case (a) we either have T ✓ A1 in which case h 2 (E1)R+3 and we obtain h 2 / E (since then h 2 / A02 while we know E2 ✓ A02), or if T * A1 we get an attack (T \ A02, h) 2 R2? (if otherwise T \ A02 = ; this means we removed some a 2 T \ A2 when constructing the reduct, which means a 2 / E2 and consequently a 2 / E), which since E2 2 cf(SF2?) either means T \ A02 * E2 or h 2 / E20, both give us T [ { h} * E. For case (b) we have T \ A1 * E1, which means T [ { h} * E.
(2.) Suppose now that E 2 cf(SF ). From this we derive that E \ A1 2 cf(SF1) because every subset of a con ict-free set is also con ict-free. We now show that E \ A2 2 cf(SF20). Given that E 2 cf(SF ), then for all T ✓ E \ A1 and a 2 E \ A2, we have (T, a) 2 / R3. Hence, no argument in E is deleted going from SF2 to the reduct SF20. Thus, we conclude that E \ A2 ✓ A02. Moreover, by E 2 cf(SF ) we know for each (T, h) 2 R2 that T [ { h} * E which carries over to SF20, since the attacks in R2 may be removed, but are never changed. Finally, whenever for a link (T, h) 2 R3 with T \ A1 ✓ E we add an attack (T \ A02, h) 2 R20 when constructing the reduct, we also obtain (T \ A02) [ { h} * E since otherwise T [ { h} ✓ E. Therefore, E \ A2 2 cf(SF20) concluding the proof.
Finally, we are ready to characterize the splitting algorithm by proving the main theorem
of this paper for the standard Dung semantics. In particular, we show that 1. if one computes
an extension E1 in SF1, then applies the previously discussed reduct and modi cation, and
obtains an extension E2 of the remaining sub-framework, the set-union of the two indeed make
for an extension of the whole framework SF . This characterizes the incremental computation
of the extension E by evaluating the two sub-frameworks. Conversely, we show that 2. if
we project an arbitrary extension E of the whole framework SF to the sub-frameworks, we
obtain extensions E1 for SF1 and E2 for the (w.r.t. E1)-modi ed version of SF2. This result
generalizes the corresponding result of AFs [
Due to space constraints we present proof details only for admissible semantics, which are
prototypical for the other semantics. Details for the remaining semantics can be found in [
Proof. (admissible). (1.) Since admissibility implies con ict-freeness, we know from Proposition 21 that E = E1 [ E2 2 cf(SF ). We need to show that E defends itself in SF , i.e. for all a 2 E, if (T, a) 2 R1 [ R2 [ R3, then (T 0, t) 2 R1 [ R2 [ R3 for T 0 ✓ E and t 2 T . Consider an argument a 2 E1. E1 defends a from each attack in R1 towards a since E1 2 adm(SF1). Therefore, E1 2 adm(SF ). Consider now an argument a 2 E2 and an arbitrary attack (T, a) 2 R2 [ R3 towards a. If T \ (E1)R+1[ R3 6= ; we know a is defended (in SF ) by E1 + against (T, a) and we are done, hence, we proceed with the assumption T \ (E1)R1[ R3 = ; . This means that either (T \ A02, a) 2 R2? (via the reduct) or ((T \ A02) [ { a}, a) 2 R2? (via the modi cation). Since a 2 E2 and E2 2 adm(SF2?) we know there is a counter-attack in R2? which defends a. Even in case ((T \ A02) [ { a}, a) 2 R2? this counter-attack cannot be against a since this violates con ict-freeness of E2 in SF2?. Hence, there is some (S, t) 2 R2? s.t. S ✓ E2 and t 2 T \ A02 with t 2 / S. Hence, either (a) (S, t) 2 R2 in which case a is defended by E in SF or (b) there is some (S0, t) 2 R3 with S0 S s.t. S0 \ A1 ✓ E1, in which case a is defended (in SF ) by E via the attack (S0, t) since then S0 ✓ E1 [ E2. In any case we showed that a is defended in SF by E, i.e., E 2 adm(SF ).
(2.) By Proposition 21 we get E1 = E \ A1 2 cf(SF1) and E2 = E \ A2 2 cf(SF20). Since E is defends itself in SF we get E \ A1 2 adm(SF1) because (SF1, SF2, R3) is a splitting of SF , i.e. no argument in E \ A1 is attacked by a subset of A2 or defended by E \ A2. That is, in SF1 every attack towards an argument in E \ A1 is countered by E \ A1. It remains to show that E \ A2 2 adm(SF2?). Consider now an argument a 2 E2 and an arbitrary attack (T, a) 2 R2? against a. This attack (T, a) either corresponds to an attack (T, a) 2 R2 or (T 0, a) 2 R3 with T 0 T \ {a} (which accounts for both the case of addition in the reduct and the modi cation).
+ + In both cases we have that T \ (E1)R1[ R3 = ; (or T 0 \ (E1)R1[ R3 = ; , resp.) as otherwise (T, a) would not be in R2?. However, since a is defended by E in SF , there is a counter-attack (S, t) 2 R2 [ R3 s.t. S ✓ E and t 2 (T \ {a}) (or t 2 (T 0 \ {a}), resp.). If (S, t) 2 R2 then from S ✓ E and E2 ✓ A02 (which we get from E2 2 cf(SF20) via Proposition 21) and the fact that then (S, t) 2 R20 since S [ { t} ✓ A02 we get that E2 defends a via (S, t) against (T, a) in SF2?. If (S, t) 2 R3 since S ✓ E we have S \ A1 ✓ E1, and hence we get an attack (S \ A02, t) 2 R20 which again defends a against (T, a) in SF2?. Hence, in every case a is defended in SF2?, i.e., E2 2 adm(SF2?).
To further establish the adequacy of our splitting approach for SETAFs, we want to highlight
that we retain the close connection to the directionality principle [
We are now able to generalize the following result regarding directionality from AFs [4, Theorem 4.13].
Theorem 24. Let be a semantics s.t. | (SF )| 1 for each SETAF SF . If allows splitting (i.e., Theorem 22 holds for ) then satis es directionality.
Proof. Assume towards contradiction this is not the case, i.e., for some SETAF SF = (A, R) and some U 2 US(SF ) it holds (SF#U ) 6= {E \ U | E 2 (SF )}. Observe that (SF#U , SF2, R3) is a splitting of SF , where SF2 = (A \ U, R \ (2A\U ⇥ (A \ U ))) and R3 contains exactly those attacks of SF that are neither in SF#U nor SF2.
(✓6 ): This means there is some E1 2 (SF #U ) s.t. E1 6= {E \ U } for any E 2 (SF ). By Theorem 22 and since | (SF2?)| 1 we get E2 2 (SF2?), where SF2? = modER13 (SF20) and SF20 is the (E1, R3)-reduct of SF2. Then by Theorem 22 we get E1 [ E2 2 (SF ), a contradiction to the assumption that there is no E 2 (SF ) s.t. E1 = E \ U .
(◆6 ): This means there is some E 2 (SF ) s.t. there is no E1 2 (SF#U ) with E1 = {E \ U }, directly contradicting Theorem 22.
In this paper, we introduced a modi cation-based splitting approach for SETAFs, and showed
that it generalizes the important key features of its AF counterpart. In the following, we clarify
the relation of our splitting approach to SCC-recursiveness (as due to [
ADFs [
In summary, we showed how the splitting technique can be applied in the context of collective attacks, where in contrast to the AF case also intricate situations like “diagonal splitting” can occur. We furthermore showed that the splitting theorem holds in the setting of SETAFs, and established that we retain the strong link to directionality which is known for AFs.
Our result can serve as a starting point for more general splitting ideas like parameterized
splitting (cf. [
This work has been supported by the European Union’s Horizon 2020 research and innovation programme (under grant agreement 101034440). Moreover, this research has been supported by the Vienna Science and Technology Fund (WWTF) through project ICT19-065, and through the Austrian Science Fund (FWF) through projects 10.557766/COE12 and P32380.