added/retracted by users to express their point of view in response to the last moves made by the adversaries.
Recently, the definition of evaluation algorithms taking into account such dynamic
aspects has received an increasing attention, as in these situations incremental
computation techniques could greatly improve performance [
In this paper, we discuss the recently proposed algorithm SPA [
Contributions We present SPA [
There has been an extensive body of work on managing changes in
argumentation [
Given an AF hA; S i and arguments a; b 2 A, we say that a attacks b iff (a; b) 2 S , and that a set S A attacks b iff there is a 2 S attacking b. We use S+ = fb j 9a 2 S : (a; b) 2 S g to denote the set of arguments attacked by S. Moreover, we say that S A defends a iff 8b 2 A such that b attacks a, there is c 2 S such that c attacks b. A set S A of arguments is said to be: (i) conflict-free if there are no a; b 2 S such that a attacks b; (ii) admissible if it is conflict-free and it defends all its arguments.
An argumentation semantics specifies the criteria for identifying a set of arguments
that can be considered “reasonable” together, called extension. A preferred extension of
an AF A is a maximal (w.r.t. ) admissible set of A . The ideal extension of A is the
biggest (w.r.t. ) admissible set of A which is contained in every preferred extension of
A . It is well-known that every AF admits exactly one ideal extension which is contained
in the intersection of the preferred extensions, which are at least one [
Given an AF A = hA; S i and an argument g 2 A, we say that g is skeptically accepted w.r.t. A under the preferred semantics iff for each preferred extension E of A it holds that g 2 E. In the following, we use SAA (g) to denote the skeptical acceptance (either true or false) of g w.r.t. AF A .
Example 1. Figure 1(a) shows the graph of the AF AF0 = hA0; 0i where A0 = fa; b; c; : : : ; lg and 0 includes, among others, attacks (a; b), (b; a), and (c; d). The preferred extensions of AF0 are Epr = fa; d; f; h; j; lg and E0pr = fb; d; f; h; kg, while the ideal extension of AF0 is Eid = fd; f; hg. Thus, SAAF0 (d) is true, and so is for SAAF0 (f) and SAAF0 (h), while for any other argument x, SAAF0 (x) =false.
Fact 1 Let A be an AF, E the ideal extension of A , and g an argument of A . If g 2 E then SAA (g) =true. On the other hand, if g 2 E+ then SAA (g) =false. Updates Performing an update on an AF A0 means modifying it into an AF A by adding or removing arguments or attacks. We use +(a; b), with a; b 2 A0 and (a; b) 62 S0, (resp. (a; b), with (a; b) 2 S0) to denote the addition (resp. deletion) of an attack (a; b), and u(A0) to denote the application of update u = (a; b) to AF A0 (where means either + or ). Applying an update u to an AF A0 implies that the extensions prescribed by a given semantics, as well as the arguments that are skeptical accepted, may change. Example 2. Continuing with our running example, let u = +(h; d). The ideal extension of u(AF0) is ff; hg, while the preferred extensions are fa; f; h; j; lg and fb; f; h; kg. Thus, only f and h are skeptically accepted w.r.t. u(AF0).
As for the addition (resp. deletion) of a set of isolated arguments (i.e., arguments not adjacent to any other argument in the graph), it is easy to see that if A is obtained from A0 through the addition (resp. deletion) of a set S of isolated arguments, then every argument in S is trivially skeptically accepted (resp., not accepted) w.r.t. A . Indeed, if E0 is an extension for A0, then E = E0 [ S (resp. E = E0 n S) is an extension for A containing every (resp., none) argument in S. Of course, if arguments in S are not isolated, for addition we can first add isolated arguments and then add attacks involving these arguments, while for deletion we can first delete all attacks involving arguments in S. Thus we do not consider these kinds of updates in the following, and focus on the addition and deletions of attacks.
Notation for reachability and other useful concepts Given an AF A = hA; S i and an argument x, we use ReachA (x) to denote the set of arguments that are reachable from x in the AF A . Moreover, we use ReachA1(x) to denote the set of arguments from which x is reachable in A . For instance, for the AF AF0 = hA0; 0i of our running example (see Figure 1(a)), we have that ReachAF0 (d) = fd; c; g; h; ig, and ReachAF10 (h) = A0 n fi; j; k; lg. We write ReachA (x) = 0/ and ReachA1(x) = 0/ if x is not in A .
We use H(A ; u) to denote the larger AF between A and u(A ), that is, H(A ; u) is (i) the updated AF u(A ) if u is an addition update (it includes the attack added through u), (ii) the original AF A if u is a deletion (the removed attack is still considered in H(A ; u)). For instance, if u = +(h; d) then H(AF0; u) = hA0; 0 [ f(h; d)gi, while H(AF0; u) = AF0 for any deletion update u.
We use P (S; A ) to denote the restriction of AF A = hA; S i to a subset S A of
its arguments [
Finally, given A1 = hA1; S1i and A2 = hA2; S2i, we denote as A1 t A2 = hA1 [ A2; S1 [ S2i the union of the two AFs. 3
In this section, we introduce the concept of supporting set which intuitively consists of the set of arguments that needs to be taken into account in order to determine the skeptical acceptance of an argument of interest after performing an update. We provide a parametric definition of supporting set that will enable the characterization of different portions of a given AF, called context-based AFs, that will be used for two different purposes: (i) recompute the skeptical acceptance of a goal w.r.t. the updated AF, and (ii) recompute the ideal extension of the updated AF.
Before defining the supporting set, we introduce the auxiliary notion of steadiness of an argument. Given an AF A = hA; S i, the ideal extension E of A , and an update u = (a; b), we first define E(u) as the subset of E consisting of the arguments which are not reachable from b in A , i.e., E(u) = fz j z 2 E; z 62 ReachA (b)g. Intuitively, the acceptance status of the arguments in E(u) is not affected by u as they are not reachable from it. Then, the set of steady arguments for u = (a; b) w.r.t. A is defined as StdA (u) = (E(u))+ n fbg, i.e., the arguments attacked by E(u) in A and that will be still attacked by E(u) in u(A ). Argument b is not included in StdA (u) as it may be no longer attacked by a 2 E(u) after performing u = (a; b); however, it will be considered for positive updates in Definition 1. For the AF AF0 of our example, where Eid = fd; f; hg, if u = +(h; d) then Eid (u) = ffg and StdAF0 (u) = fe; gg Ei+d = fc; e; g; ig. Definition 1 (Supporting set). Let A = hA; S i be an AF, u = ideal extension of A , and g an argument in A. Let (a; b) an update, E the – Sup0(u; A ; E; g) = >:fbg otherwise: 80/ if u = +(a; b) ^ b 2 (E(u))+; > <
0/ if b 62 ReachH(1A ;u)(g); y 2 ReachH(1A ;u)(g) ^ y 62 StdA (u)g.
– Supi+1(u; A ; E; g)= Supi(u; A ; E; g) [ fy j 9(x; y) 2 S s:t: x 2 Supi(u; A ; E; g) ^ Let n be the natural number such that Supn(u; A ; E; g) = Supn+1(u; A ; E; g). The supporting set Sup(u; A ; E; g) is:
Sup(u; A ; E; g) = Supn(u; A ; E; g) \ ReachG1(g) (1) where G=P (Supn(u; A ; E; g); H(A ; u)) is the restriction of H(A ; u) to Supn(u; A ; E; g).
Finally, when g is not specified, the supporting set, denoted as Sup(u; A ; E; ?), is defined as Sup(u; A ; E; g) except that all the checks concerning Reach 1 are omitted.
Intuitively, Sup(u; A ; E; g) consists of the arguments whose status may change after performing an update u and such that their change can imply a change of the status of g. More in detail, Sup(u; A ; E; g) for u = (a; b) and g consists of the arguments that (i) can be reached from b without using any steady argument y; and (ii) allow to reach g in H(A ; u) by using only the arguments in Supn(u; A ; E; g). In fact, Equation (1) entails that an argument of Supn(u; A ; E; g) will be in Sup(u; A ; E; g) only if it can reach g in the restriction of H(A ; u) to Supn(u; A ; E; g)—the other arguments in Supn(u; A ; E; g) are not needed to determine the acceptance status of g, and thus they are pruned by Equation (1).
When no argument g is specified, the set Sup(u; A ; E; ?) is built by ignoring condition (ii) above. It is easy to see that, for any argument g, Sup(u; A ; E; g) Sup(u; A ; E; ?) ReachA (b), where b is the argument in the update u = (a; b). Moreover, Sup(u; A ; E; g) may be empty even if g 2 ReachA (b). Finally, if Sup(u; A ; E; g) 6= 0/ then the arguments of at least one path from b to g belong to Sup(u; A ; E; g).
Example 3. For the goal c, we have that Sup0(u; AF0; Eid ; c) = fdg, Sup1(u; AF0; Eid ; c) = fc; dg, and Sup2(u; AF0; Eid ; c) = fc; dg (the latter does not contain g since g 2 StdAF0 (u)).
Thus, Sup(u; AF0; Eid ; c) = fc; dg as both c and d allow to reach c in the restriction of the updated AF to fc; dg. Analogously, we have that Sup(u; AF0; Eid ; ?) = fc; dg.
Consider now the goal h. Again Sup0(u; AF0; Eid ; h) = fdg, and Sup1(u; AF0; Eid ; h) = Sup2(u; AF0; Eid ; h) = fc; dg. However, Sup(u; AF0; Eid ; h) = 0/ as fc; dg\ReachG1(h) = 0/ , where G = P (fc; dg; u(AF0)). Finally, for the goal a, Sup(u; AF0; Eid ; a) = 0/ . Theorem 1. Let A0 = hA0; S0i be an AF, E0 the ideal extension of A0, u = (a; b) an update, A = u(A0) the updated AF, and x an argument in A0. Therefore, if Sup(u; A0; E0; x) = 0/ then SAA (x) = SAA0 (x).
Example 4. Since Sup(u; AF0; Eid ; h) = 0/ we can conclude that SAu(AF0)(h) = SAAF0 (h) = true. Similarly, since Sup(u; AF0; Eid ; a) = 0/ then SAu(AF0) (a) = SAAF0 (a) =false. 4
The supporting set has been used so far to determine whether the status of the goal does not need to be recomputed. In this section, starting from the supporting set, we define a restriction of the AF which will be used to compute the status of the goal after an update. Specifically, given the set Sup(u; A ; E; g) (resp. Sup(u; A ; E; ?)), we define the contextbased AF CBAF(u; A ; E; g) (resp. CBAF(u; A ; E; ?)). While CBAF(u; A ; E; ?) will be used to incrementally compute the ideal extension of the updated AF (with the aim of checking if one of the conditions of Fact 1 holds), CBAF(u; A ; E; g) will be used to compute the skeptical acceptance SAu(A )(g) w.r.t. the updated AF.
Given an AF A = hA; S i, its ideal extension E, and a set S A, we use Nodes(A ; S;
E) to denote the set of the nodes x 2 A such that there are a node y 2 S and a path from
x to y in A such that all nodes in the path except y do not belong to E [ E+ (i.e., they
are undecided [
Example 5. For AF0, where Eid = fd; f; hg, and u = +(h; d), we have seen in Example 3 that Sup(u; AF0; Eid ; c) = fc; dg. Thus CBAF(u; AF0; Eid ; c) = hfc; dg; f(c; d); (d; c)git T1 t T2 where: T1 = hfh; dg; f(h; d)gi since h 2 Eid does not belong to Sup(u; AF0; Eid ; c) while d 2 Sup(u; AF0; Eid ; c); and T2 = hfa; b; cg; f(a; b); (b; a); (a; c); (b; c)gi since there are paths starting from the undecided arguments a and b (fa; bg 6 (Eid [ Ei+d )) and ending in c 2 Sup(u; AF0; Eid ; c). Thus, CBAF(u; AF0; Eid ; c) is the AF shown in Figure 1(b). Also, CBAF(u; AF0; Eid ; ?) = CBAF(u; AF0; Eid ; c).
Theorem 2. Let A0 = hA0; S0i be an AF, E0 the ideal extension of A0, u = (a; b) an update, A = u(A0) the updated AF, and x an argument in A0. Thus, if Sup(u; A0; E0; x) 6= 0/ then x is skeptically accepted w.r.t. A iff it is skeptically accepted w.r.t. the contextbased AF CBAF(u; A0; E0; x).
Example 6. Continuing from Example 5, we can conclude that argument c is not skeptically accepted w.r.t. the updated AF u(AF0) because it is not skeptically accepted w.r.t. the context-based AF CBAF(u; AF0; Eid ; c) of Figure 1(b) whose preferred extensions are fa; hg and fb; hg (only h is sceptically accepted w.r.t. the context-based AF). Theorem 3. Let A0 = hA0; S0i be an AF, E0 the ideal extension of A0, u = (a; b) an update, and A = u(A0) the updated AF. Then, the ideal extension E of A is such that E = (E0 n Sup(u; A0; E0; ?)) [ E0, where E0 is the ideal extension of the context-based AF CBAF(u; A0; E0; ?).
Example 7. Continuing from Example 5, the ideal extension ff; hg of u(AF0) is equal to (fd; f; hg n fc; dg) [ fhg where fhg is the ideal extension of CBAF(u; AF0; Eid ; ?).
The results of Theorems 1 and 2, along with those of Theorem 3 and Fact 1, allow us to define SPA (see Algorithm 1) to decide the skeptical acceptance of a goal g w.r.t. an AF A0 updated by u = (a; b). Algorithm SPA works as follows. First, the supporting set S? = Sup(u; A0; E0; ?) is computed at Line 1, and using Theorem 3 the ideal extension E of the updated AF is computed by invoking an external solver ID-Solver(Aid ), 01 5 01 7 01 6 01 5 ● ● ●● ●● 0101 43 ● ● ● ●● ● 010101 120 ●● ●● ●● ●●●●● ● ● ●● 01 − 1
ASP ● A−basePS ● ●●● ● ●●●● ● ● ● ●● ● ● ●●●● ● ● ● ● ●
● ● ● ●● ● ●●● ● ●●●● ●●● ●● ● ● ● ● ● ● ● ● ● ● ● 01 2 10 3 .N of ksAtac computing the ideal extension of the context-based AF CBAF(u; A0; E0; ?) (Line 3). Then, using Fact 1, if g belongs to E, then g is skeptically accepted and the algorithm returns true along with the ideal extension of the updated AF (Line 5). Similarly, if g belongs to the set of arguments attacked by an argument in E, then g is not skeptically accepted and the algorithm returns false along with E (Line 7). Otherwise, the set Sg = Sup(u; A0; E0; g) is built (it can be efficiently done by starting from S?), and it is checked if it is empty. If this is the case, using Theorem 1, we can conclude that the acceptance status of g does not change after the update (Line 10). Otherwise, the context-based AF is built at Line 11 and, using Theorem 2, the skeptical acceptance of g is recomputed by invoking an external solver SA-Solver(Asa; g) which tells us if g is skeptically accepted w.r.t. the context-based AF CBAF(u; A0; E0; g) (Line 12). SPA-base: A version of SPA not using the ideal extension SPA-base is obtained from SPA by skipping lines 1–7 of Algorithm 1 and assuming E0 = 0/ at lines 8 and 11 to compute Sg and Asa respectively. Also, no ideal extension is returned (i.e., E = ?). Notice that, similarly to SPA-base, SPA does not use the information provided by the initial ideal extension when E0 = 0/ , though SPA always incrementally computes the ideal extension of the updated AF. 6
We have implemented a C++ prototype and compared our incremental technique with
ArgSemSAT [
As for the datasets, we used benchmarks from the DS-pr track of ICCMA’17, that
is, the dataset A2 consisting of 50 AFs with a number of arguments jAj 2 [61; 20K] and
a number of attacks jS j 2 [97; 358K], and the dataset A3 consisting of 100 AFs with
jAj 2 [39; 100K] and jS j 2 [72; 1:26M]. For each AF A0 in the dataset, we randomly
selected an update u and an argument g. Then, we computed SAu(A0)(g) by using 1)
SPA, that is Algorithm 1 where ID-Solver is pyglaf [
For AF A0, update u, and argument g, let tA and tB be the amount of time required by SPA and SPA-base, respectively, to compute SAu(A0)(g). Let tS be the time required by ArgSemSAT to compute SAu(A0)(g) from scratch. Then, the improvements of SPA and SPA-base over ArgSemSAT are defined as ttS and ttS , respectively. Thus, an imA B provement equal to x means that the incremental computation is x times faster than the computation from scratch.
Figure 2 reports the improvement (log scale) of SPA and SPA-base over
ArgSemSAT on datasets A2 (left-hand side) and A3 (right-hand side) for single updates
versus the size of the AFs, i.e., the number of attacks (solid lines are obtained by linear
regression). Both SPA and SPA-base significantly outperform the computation from
scratch, though the improvement decreases as the number of attacks increases—this
behavior is in line with that of algorithms for computing argumentation semantics in the
static setting [
Considering the averages of the improvements, SPA and SPA-base turn out to be 5 and 4 orders of magnitude faster than ArgSemSAT, respectively. However, as this can be skewed by extremely large values of improvements (e.g. 106), we also considered the medians of improvements for SPA (32 on A2, 134 on A3) and SPA-base (27 on A2, 40 on A3) (see dashed line in Figure 2), which confirm the significance of the gain in efficiency. In brief, both SPA and SPA-base generally outperform the computation from scratch, and SPA is generally faster than SPA-base except for a few AFs whose initial ideal extension is empty—future work will focus on devising heuristics to take advantages of both algorithms.