Efficient Computation of Extensions for Dynamic Abstract Argumentation Frameworks: An Incremental Approach

1 Introduction

Abstract argumentation has emerged as one of the major fields in Artificial Intelligence [Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009; Baroni et al., 2011; Modgil and Prakken, 2011].In particular, abstract argumentation frameworks (AFs) [Dung, 1995] are a simple, yet powerful formalism for modelling disputes between two or more agents. The formal meaning of an AF is given in terms of argumentation semantics, which intuitively tell us the sets of arguments (called extensions) that can profitably be exploited to support a point of view in a discussion.

Although the idea underlying AFs is very simple and intuitive, most of the argumentation semantics proposed so far suffer from a high computational complexity [Dunne and Wooldridge, 2009]. Complexity bounds and evaluation algorithms for AFs have been deeply investigated in the literature, as also witnessed by the International Competition on Computational Models of Argumentation (ICCMA) 1 whose aim is encouraging research and development of efficient algorithms for computational models of AFs.

However, most research focused on 'static' frameworks, whereas in practice AFs are dynamic systems [Baumann, 2011; Falappa et al., 2011; Liao et al., 2011; Baroni et al., 2014b; Charwat et al., 2015]. In fact, typically an AF represents a temporary situation, and new arguments and attacks can be added/retracted to take into account new available knowledge. For instance, for disputes among users of online social networks [K¨okciyan et al., 2016], arguments/attacks are continuously added/retracted by users to express their point of view in response to the last move made by the adversaries (often disclosing as few arguments/attacks as possible).

Surprisingly, the definition of evaluation algorithms and the analysis of the computational complexity taking into account such dynamic aspects have been mostly neglected, whereas in these situations incremental computation techniques could greatly improve performance. In many cases, especially when few updates at a time are performed, the changes made to an AF can result in small changes to the set of its extensions, and recomputing the whole semantics from scratch can be avoided.

With the aim of identifying the portion of an AF affected by an update, the division-based method, proposed by [Liao et al., 2011] and refined by [Baroni et al., 2014b], divides the updated AF into two parts: affected and unaffected, where only the status of affected arguments needs to be recomputed after updates. Essentially, the set of affected arguments consists of those that are reachable from the updated arguments. Recently, focusing on unique-extension semantics, according to which every AF has exactly one extension, in [Greco and Parisi, 2016a; 2016b] we have introduced the concept of influenced set, where the initial extension of an AF is used to further restrict the portion of the AF affected by an update. However, the technique in [Greco and Parisi, 2016a; 2016b] only works for the grounded and ideal semantics and does not apply to multiple-extensions semantics, which can associate more than one extension to a given AF.

In this paper, we focus on the semantics considered at the last argumentation competition (i.e., the three multipleextensions semantics complete, preferred, and stable, and the unique-extension semantics grounded) and propose a general approach for incrementally solving the following computational task: Given an AF A0, an extension for A0 under semantics S, and an update u, determine an extension of the updated AF u(A0) under S. In other words, we explore the possibility of incrementally solving the ICCMA computational task S-SE: Given an AF, determine some S-extension.

1 http://argumentationcompetition.org

Contributions. We introduce an incremental technique for recomputing an extension of an updated AF under four popular semantics. The algorithm consists of three main steps: (i) identification of a sub-AF, called reduced AF, on the basis of the influenced set and additional information provided by the initial extension (ii) using any non-incremental algorithm to compute an extension of the reduced AF; and (iii) getting the final extension by merging a portion of the initial extension with that computed for the reduced AF.

We performed a thorough experimental analysis showing the effectiveness of our approach for all the semantics considered, even in the case of sets of updates applied simultaneously. Specifically, for each semantics, we compared our technique with the solver that won the ICCMA'15 competition for the computational task S-SE, and show that our technique outperforms the computation from scratch by two orders of magnitude, on average.

2 Preliminaries

We assume the existence of a set Arg of arguments. An (abstract) argumentation framework [Dung, 1995] (AF) is a pair 〈A, Σ〉, where A ⊆ Arg and Σ ⊆ A × A is a binary relation over A whose elements are called attacks. Thus, an AF is a directed graph where nodes correspond to arguments and edges correspond to attacks. An argument is an abstract entity whose role is entirely determined by its relationships with other arguments.

Given an AF 〈A, Σ〉 and arguments a, b ∈ A, we say that a attacks b iff (a, b) ∈ Σ, and that a set S ⊆ A attacks b iff there is a ∈ S attacking b. We use S+ = {b | ∃a ∈ S : (a, b) ∈ Σ} to denote the set of all arguments that are attacked by S.

Moreover, we say that S ⊆ A defends a iff ∀b ∈ A such that b attacks a, there is c ∈ S such that c attacks b.

A set S ⊆ A is said to be (i) conflict-free, if there are no a, b ∈ S such that a attacks b; (ii) admissible, if it is conflictfree 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 complete extension (co) is an admissible set that contains all the arguments that it defends. A complete extension S is said to be: preferred (pr) iff it is maximal (w.r.t. ⊆); stable (st) iff it attacks each argument in A \ S; grounded (gr) iff it is minimal (w.r.t. ⊆).

All the above-mentioned semantics except the stable admit at least one extension, and the grounded admits exactly one extension [Dung, 1995]. It is well-known that, for any AF A, Egr(A) ⊆ Eco(A) and Est(A) ⊆ Epr(A) ⊆ Eco(A).

Given an AF A and a semantics S ∈ {co, pr, st, gr}, we use ES(A) to denote the set of S-extensions for A.

Example 1 The set of admissible sets for the AF A0 shown in Fig.1 (where attack (c, f) does not belong to A0) is

{∅, {b}, {g}, {a, g}, {b, g}, {f, g}, {a, g, f}, {b, g, f}}, and ES(A0) with S ∈ {co, pr, st, gr} is as reported in the second column of Table 1. ✷

The argumentation semantics can be also defined in terms of labelling [Baroni et al., 2011]. A labelling for an AF A = 〈A, Σ〉 is a total function L : A → {IN, OUT, UN} assigning to each argument a label. L(a) = IN means that argument a is accepted, L(a) = OUT means that a is rejected, while L(a) = UN means that a is undecided.

Let in(L) = {a | a ∈ A ∧ L(a) = IN}, out(L) = {a | a ∈ A∧L(a) = OUT}, and un(L) = {a | a ∈ A∧L(a) = UN}. In the following, we also use the triple 〈in(L), out(L), un(L)〉 to represent the labelling L.

Given an AF A = 〈A, Σ〉, a labelling L for A is said to be admissible (or legal) if ∀a ∈ in(L) ∪ out(L) it holds that (i) L(a) = OUT iff ∃ b ∈ A such that (b, a) ∈ Σ and L(b) = IN; and (ii) L(a) = IN iff L(b) = OUT for all b ∈ A such that (b, a) ∈ Σ. Moreover, L is a complete labelling iff conditions (i) and (ii) hold for all a ∈ A.

In the following, we say that the status of an argument a w.r.t. a labelling L (or its corresponding extension in(L)) is IN (resp., OUT, UN) iff L(a) = IN (resp., L(a) = OUT, L(a) = UN). We will avoid to mention explicitly the labelling (or the extension) whenever it is understood.

Between complete extensions and complete labellings there is a bijective mapping defined as follows: for each extension E there is a unique labelling L = 〈E,E+,A \ (E ∪ E+)〉 and for each labelling L there is a unique extension in(L). We say that L is the labelling corresponding to E. For instance, in Example 1, 〈{a, f, g}, {b, d, e, h}, {c}〉 is the labelling corresponding to the extension {a, f, g}, while 〈{b, f, g}, {a, c, d, e, h}, ∅〉 corresponds to {b, f, g}.

Updates. Performing an update on an AF A0 means modifying it into an AF A by adding or removing arguments or attacks. In the following, we will present our results by focusing on updates consisting of adding/deleting one attack between arguments of A0. Then we will show in Section 4.2 that the results for single attack updates extend to the case of multiple updates. In fact, applying a set of updates can be reduced to applying a single update. In our experimental analysis we considered both single and multiple updates.

We use +(a, b), with a, b ∈ A0 and (a, b) ̸∈ Σ0, (resp. -(a, b), with (a, b) ∈ Σ0) 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 implies that its semantics (set of extensions or labellings) changes, as shown by Table 1 which reports the sets of extensions for the AFs of Figure 1

before and after performing the update +(c, f).

Concerning the addition (resp. deletion) of a set of isolated arguments, it is easy to see that if A is obtained from A0 through the addition (resp. deletion) of a set S of isolated argument, then, let E0 be an extension for A0, E = E0 ∪ S (resp. E = E0 \ S) is an extension for A that can be trivially computed. 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 update in the following.

3 Arguments Influenced by an Update

In this section, we first provide some sufficient conditions ensuring that a given S-extension for an AF A continues to be an S-extension for the updated AF u(A). Then, we introduce the influenced set which intuitively consists of the set of arguments whose status may change after performing an update.

Updates preserving a given initial extension. Given an update ±(a, b) and an initial extension E0 corresponding to L0, for each pair of initial statuses L0(a) and L0(b) of the arguments involved in the update, Tables 2 and 3 tell us the semantics for which E0 is still an extension after the update.

Proposition 1 Let A0 be an AF, S a semantics, E0 ∈ ES(A0) an extension of A0 under semantics S, L0 the labelling corresponding to E0, and u an update. If S is in the cell 〈L0(a), L0(b)〉 of Table 2 and u = +(a, b) (resp., of Table 3 and u = -(a, b)), then E0 ∈ ES(u(A0)).

The results in Tables 2 and 3 concerning gr follow from those in [Boella et al., 2009a; 2009b], where the principles according to which the grounded extension does not change when attacks are added/removed have been studied.

In the following, given an AF A0 and an S-extension E0 for it, we say that an update u is irrelevant w.r.t. E0 and S iff the conditions of Proposition 1 hold. Otherwise, u is relevant.

Example 2 Consider A0 of Figure 1 and its sets of extensions listed in the second column of Table 1. E0 = {b, f, g} is an extension according to semantics S ∈ {co,pr,st}. Thus, L0(c) = OUT and L0(f) = IN, and using Proposition 1 it follows that for update u = +(c, f) E0 is still an extension of u(A0) (see the last column of Table 1). Thus +(c, f) is irrelevant w.r.t. E0 and S. However, +(c, f) is relevant w.r.t. E0 = {a, f, g} and all the semantics (in this case L0(c) = UN and L0(f) = IN, and no semantics is listed in the cell 〈UN, IN〉 of Table 2). ✷

It is important to note that Tables 2 and 3 are not meant to be exhaustive, as more conditions can be found for which an S-extension is preserved after an update. For instance, for the grounded semantics, the initial extension is preserved also if L0(a) = OUT and L0(b) = IN and argument a of updated +(a, b) is not reachable from b. Here we provided a simple set of conditions that can be easily checked by just looking at the initial labelling L0. Our technique can be trivially extended by considering a more general set of such conditions.

Influenced set. For irrelevant updates, the influenced set will be empty (in this case, the initial extension will be immediately returned as an extension of the updated AF by our algorithm). If none of the conditions of Proposition 1 holds (i.e., the update is relevant), then the influenced set may turn out to be not empty. In such case, the influenced set will be used to delineate a portion of the argumentation framework, called reduced AF, that we will use to recompute (a portion of) an extension for the updated AF.

Given an AF A = 〈A, Σ〉 and an argument b ∈ A, we use ReachA(b) to denote the set of arguments that are reachable from b in the graph A.

Definition 1 (Influenced set) Let A = 〈A, Σ〉 be an AF, u = ±(a, b), E an extension of A under semantics S, and let

Example 3 Consider the the AF A0 = 〈A0, Σ0〉 of Figure 1 and the update u = +(c, f). We have that ReachA0(f ) = A0 \ {g, h}. The influenced set depends on the initial extension chosen. For the extension {b, f, g} of Example 2, we have that the influenced set is empty as u is irrelevant. For the extension E0 = {a, f, g}, the influenced set is I(u,A0,E0) = {f, e}. Indeed, d ̸∈ I(u,A0,E0) since it is attacked by g ∈ E0 which is not reachable from f. Thus the arguments that can be reached from d do not belong to I(u,A0,E0). If we consider the initial grounded extension {f, g}, then {f, e} turns out to be the influenced set again. ✷

The influenced set of u w.r.t. A and E is I(u,A,E) = In(u,A,E) such that In(u,A,E) = In+1(u,A,E). ✷

4 Incremental Computation of Extensions

Given the influenced set, we define a subgraph, called reduced AF, that will be used to compute the status of the influenced arguments, thus providing an extension that will be combined with that of initial AF to obtain an extension of the updated AF, for every semantics S ∈{co, pr, st, gr}.

For any AF A = 〈A,Σ〉 and set S ⊆ A of arguments, we denote with Π(S,A) = 〈S,Σ ∩ S × S〉 the subgraph of A induced by the nodes in S. Moreover, given two AFs A1 = 〈A1, Σ1〉 and A2 = 〈A2, Σ2〉, we denote as A1 ⊔A2 = 〈A1 ∪ A1, Σ1 ∪ Σ2〉 the union of the two AFs.

Definition 2 (Reduced AF) Let A0 = 〈A0,Σ0〉 be an AF, E0 ∈ ES(A0) an extension for A0 under a semantics S ∈ {co, pr, st, gr}, and u = ±(a, b) an update. Let u(A0) = 〈A,Σ〉 be the AF updated using u. The reduced AF for A0 w.r.t. E0 and u (denoted as R(u, A0, E0)) is as follows.

• R(u,A0,E0) = Π(I(u,A0,E0), u(A0)) ⊔ A1 ⊔ A2 where:
• R(u,A0,E0) is empty if I(u,A0,E0) is empty.
• A1 is the union of the AFs 〈{a, b}, {(a, b)}〉 s.t. (a, b) ∈ Σ, a ̸∈ I(u, A0, E0), a ∈ E0, and b ∈ I(u, A0, E0);

Hence, AF R(u,A0,E0) contains, in addition to the subgraph of u(A0) induced by I(u,A0,E0), additional nodes and edges containing needed information on the "external context", i.e. information about the status of arguments which are attacking some argument in I(u, A0, E0). Using fake arguments/attacks to represent external contexts has been exploited in [Baroni et al., 2014a] where decomposability properties of argumentation semantics are investigated.

• ii) A2 is the union of the AFs 〈{c}, {(c, c)}〉 s.t. there is (e, c) ∈ Σ, e ̸∈ I(u,A0,E0), e ̸∈ (E0 ∪ E+ 0 ), and c ∈ I(u, A0, E0). ✷

Example 4 For our running example, if E0 = {a, f, g} and u = +(c, f), the reduced AF R(+(c, f),A0,E0) consists of the subgraph induced by I(u,A0,E0) = {f, e} plus the edge (f, f) as there is the attack (c, f) in the updated AF from an uninfluenced argument c labelled as UN toward the influenced argument f. Hence, R(+(c, f),A0,E0) = 〈{e, f}, {(f, f), (f, e)}〉. ✷

Theorem 1 Let A0 be an AF, and A = u(A0) be the AF resulting from performing update u = ±(a, b) on A0. Let E0 ∈ ES(A0) be an extension for A0 under a semantics S ∈ {co, pr, st, gr}. Then, if ES(R(u,A0,E0)) is not empty, then there is an extension E ∈ ES(A) for the updated AF A such that E = (E0 \ I(u, A0, E0)) ∪ Ed where Ed is an S-extension for reduced AF R(u, A0, E0) .

Example 5 Continuing our example, for the preferred semantics, let E0 = {a, f, g} and u = +(c, f), we have that I(u,A0,E0) = {f, e}, and R(+(c, f),A0,E0) = 〈{e, f}, {(f, f), (f, e)}〉. Thus, using the theorem, there is an extension E of the updated AF such that E = ({a, f, g}\{f, e})∪ Ed where Ed = ∅ is a preferred extension of the reduced AF. In fact, E = {a, g} ∈ Epr(u(A0)). ✷

It is worth noting that the set of extensions of an AF can be empty only for the stable semantics. Thus, in the case that this happens for the reduced AF (i.e., ES(R(u, A0, E0)) = ∅), the theorem does not give a method to determine an extension of the updated AF, as shown in the following example.

Algorithm 1 Incr-Alg(A0, u, S, E0, SolverS )

Input: AF A0 = 〈A0, Σ0〉, update u = ±(a, b), semantics S ∈{co, pr, st, gr}, extension E0 ∈ ES(A0), function SolverS(A) returning an S-extension for AF A if it exists, ⊥ otherwise; Output: An S-extension E ∈ ES(u(A0)) if it exists, ⊥ otherwise; 1: S = I(u,A0,E0); 2: if (S = ∅) then 3: return E0; 4: Ad =R(u,A0,E0); 5: Let Ed =SolverS(Ad); 6: if (Ed ̸= ⊥) then 7: return E = (E0 \ S) ∪ Ed; 8: else 9: return SolverS(u(A0));

Example 6 Let A0 = 〈{a, b, c, d, e}, {(a, b), (b, c), (b, d), (c, d), (c, e), (e, c)}〉. Its stable extensions are {a, c} and {a, d, e}. For update u = +(d, d), depending on the initial extension, the influenced set is either I(u,A, {a, c}) = ∅ (as u is irrelevant w.r.t. {a, c} and st) or I(u,A, {a, d, e}) = {d}. Thus, starting from the extension {a, c} we directly know {a, c} is a stable extension of the updated AF. However, starting from {a, d, e}, the reduced AF will be R(u,A0, {a, d, e}) = 〈{d}, {(d, d)}〉, which has no stable extension. In this case, the theorem does not provide a stable extension of the updated AF, thought a stable extension exists: that obtained by starting from the initial extension {a, c}.

It is worth noting that, if we consider the preferred semantics, for which the starting extensions are again {a, c} and {a, d, e}, a preferred extension of the updated AF can be obtained no matter what starting extension is chosen. In particular, as the preferred extension for reduced AF 〈{d}, {(d, d)}〉 is the empty set, it follows that ({a, d, e} \ {d}) ∪ ∅ = {a, d} is a preferred extension of the updated AF. ✷

4.1 Incremental Algorithm

Our algorithm for computing an extension of an updated AF is shown in Algorithm 1. Besides taking as input an initial AF A0, an update u, a semantics S ∈{co, pr, st, gr}, and an extension E0 ∈ ES(A0), it also takes as input a function that computes an S-extension for an AF, if any. In particular, function SolverS(A) will be used to compute an extension of the reduced AF, which will be then combined with the portion of the initial extension that does not change in order to obtain an extension for the updated AF (as stated in Theorem 1).

More in detail, Algorithm 1 works as follows. First, the influenced set of A0 w.r.t. update u and the given initial extension E0 is computed (Line 1). If it is empty, then E0 will be still an extension of the updated AF under the given semantics S, and thus it is returned (Line 3). Otherwise, the reduced AF Ad is computed at Line 4, and function SolverS is invoked to compute an S-extension of Ad, if any. If S ∈{co, pr, gr}, then Ad will have an extension Ed, which is combined with E0 \ S at Line 7 to get an extension for the updated AF. For the stable semantics, if Est(R(u,A0,E0)) is not empty, then the algorithm proceeds as for the other semantics (Line 7). Otherwise, function SolverS is invoked to compute a stable extension of the whole updated AF u(A0), if any.

Theorem 2 Let A0 be an AF, u = ±(a, b), and E0 ∈ ES(A0) an extension for A0 under S ∈ {co, pr, st, gr}. If SolverS is sound and complete then Algorithm 1 computes E ∈ ES(u(A0)) if ES(u(A0)) ̸= ∅, otherwise it returns ⊥.

4.2 ApplyingMultiple Updates Simultaneously

We now show how our approach extends to the case of multiple updates. In fact, performing a set of updates U = {+(a1, b1), . . . ,+(an, bn), -(a′1 , b′1 ), . . . ,-(a′m, b′m)} on A0 can be reduced to performing a single update +(v, w) on an AF whose definition depends on both the set of updates U and the initial S-extension E0, as detailed in what follows.

Given a set U of updates for an AF A0, and an S-extension E0 for A0, we use U ∗ to denote the subset of U consisting of the relevant updates (that is, the updates in U for which the conditions of Proposition 1 do not hold).

Definition 3 (AF for applying a set of updates) Let A =

• Σ+ = {(a1, b1), ..., (an, bn)} ⊆ (A × A) \ Σ, and

〈A, Σ〉 be an AF, and E0 an S-extension for A. Let

• Σ- = {(a′1 , b′1 ), ..., (a′m, b′m)} ⊆ Σ
• AU = A ∪ {xi, yi | + (ai, bi) ∈ U ∗ } ∪ {x′j , y′j | -(aj, bj) ∈ U ∗ } ∪ {v,w,w′ }, where all xi, yi, x′j , y′j , w, w′ , and v are new arguments not occurring in A, and

such that Σ+ ∩ Σ- = ∅ be two sets of attacks. Let U = {+(ai, bi) |(ai, bi) ∈ Σ+} ∪ {-(aj, bj) |(aj, bj) ∈ Σ-} be a set of updates, and U ∗ ⊆ U be the set of relevant updates w.r.t. E0 and S. Then, AUE0 = 〈AU ,ΣU 〉 denotes the AF obtained from A as follows:

Theorem 3 Let A0 = 〈A0,Σ0〉 be an AF, and U a set of updates. Let A be the AF obtained from A0 by performing all updates in U on it. Then, for any semantics S ∈ {co, pr, st, gr}, E ∈ ES(A) iff there is EU ∈ ES(+(v, w)(AUE0 )) such that EU ∩ A0 = E.

5 Implementation and Experiments

We implemented a C++ prototype and, for each semantics S, compared the performance of our technique with that of the solver that won the last ICCMA competition for the computational task S-SE: Given an AF, determine some S-extension.

Datasets. We used the ICCMA'15 benchmarks. The benchmark AFs have three different AFs' structures: (i) TestSetGr consists of AFs with a very large grounded extension and many arguments in general; (ii) TestSetSt consists of AFs with many complete/preferred/stable extensions; and (iii) TestSetSCC consists of AFs with a rich structure of strongly connected components. In particular, for each of these test sets, three classes of AFs of different sizes were defined: Small, Medium, and Large. However, TestSetStLarge was removed from the competition as the majority of the solvers could not solve any of those AFs. For space limitations, we presents the results obtained for TestSetGrSmall and TestSetGrLarge, and TestSetStSmall and TestSetStMedium, but similar results were obtained also for the other datasets.

Methodology. For each semantics S, for each AF A0 = 〈A0,Σ0〉 in each dataset, we considered every S-extension E0 of A0 as an initial extension. Then, when considering single updates, we randomly selected an update of the form ±(a, b), while for multiple updates we randomly generated a set U of single updates. Next, we computed an S-extension E for the updated AF u(A0) by calling Algorithm 1, where, for each semantics S, we used as SolverS the solver that won the ICCMA'15 competition for the task SSE: CoQuiAAS [Lagniez et al., 2015] for S=co and S=gr, Cegartix [Dvor´ak et al., 2014] for S = pr, and ASPARTIXD [Gaggl and Manthey, 2015] for S = st. Then, the average run time of our algorithm to compute an S-extension was compared with the average run time of the best ICCMA solver to compute an S-extension for u(A0) from scratch.

All experiments have been carried out on an Intel Core i73770K CPU 3.5GHz with 12GB RAM running Ubuntu 14.04.

Results. Figure 2 reports the average run times (log scale) of the competitors and Incr-Alg for different semantics and datasets. In particular, the graphs also report the run times of Incr-Alg for recomputing the extensions after performing sets S of updates simultaneously, with |S| being a percentage of the number of attacks in the initial AFs. The run times of the competitors for these cases were almost equal to their run times for single updates, and are not shown for the sake of readability of the graphs. Besides the data points, for each series, Figure 2 also shows the (solid) lines obtained by linear regression. However, some datasets consist of clusters of AFs that differ substantially on the number of arguments/attacks, and thus in these cases the linear regression line would just connect the centroids of the clusters, becoming not useful. For this reason, we only show the largest cluster for TestSetStSmall (the other one consists of only 3 data points), and the two clusters of TestSetStMedium separately (the former for S = pr and the latter for S = st).

Moreover, the results obtained for the complete semantics are not shown as they were analogous to those obtained for the grounded semantics. Also, considering updates consisting of adding/removing arguments does not affect the efficiency.

The experiments also showed that, on average, the size of the reduced AF w.r.t. that of the input AF is about 9% for single updates and 52% for multiple updates with about 1% of the attacks updated. Moreover, considering also addition/removal of arguments does not affect the efficiency.

From these results, we can draw the following conclusions:

• Our algorithm significantly outperforms the competitors that compute the extensions from scratch for single updates. In fact, on average, our technique is two orders of magnitude faster than them. Moreover, the harder the computation from scratch is, the larger the improvements are. That is, the results show that the improvements obtained for S ∈ {st, pr} go beyond those for S ∈ {gr, co}.
• Our algorithm remains faster than the competitors even when recomputing an extension after performing a quite

large number of updates simultaneously. In particular, in the graphs we show the threshold percentages of updated attacks up to which the incremental approach for multiple updates is faster than the computation from scratch.

- Finally, our experiments have also shown that for sets of updates regarding a relevant portion of the input AF (on average at least 1% of the attacks for S ∈ {st, pr} and 0, 1% of the attacks for S ∈ {gr, co}) recomputing extensions after applying them simultaneously is faster than recomputing extensions after applying them sequentially. Indeed, the green lines in the graphs are mostly below the (dashed) orange lines representing the run times of recomputing extensions after applying the updates sequentially.

6 RelatedWork

There have been several significant efforts coping with dynamics aspects of abstract argumentation. [Cayrol et al., 2008; 2010] have addressed the problem of revising the set of extensions of an AF, and studied how the extensions can evolve when a new argument is considered. They focus on adding only one argument interacting with one initial argument (i.e. an argument which is not attacked by any other argument). [Bisquert et al., 2013] have studied the evolution of the set of extensions after performing a change operation (addition/removal of arguments/interaction). Dynamic argumentation has been applied to decision-making of an autonomous agent by [Amgoud and Vesic, 2012], where it is studied how the acceptability of arguments evolves when a new argument is added to the decision system.

Other relevant works on dynamic aspects of AF include the following. [Baumann, 2011] have proposed an approach exploiting the concept of splitting of logic programs to deal with dynamic argumentation. The technique considers weak expansions of the initial AF, where added arguments never attack previous ones. [Baumann and Brewka, 2010] have investigated whether and how it is possible to modify a given AF so that a desired set of arguments becomes an extension, whereas [Oikarinen and Woltran, 2011] have studied equivalence between two AFs when further information (another AF) is added to both AFs. [Baumann, 2012] have focused on expansions where new arguments and attacks may be added but the attacks among the old arguments remain unchanged, while [Baumann, 2014] have characterized update and deletion equivalence, where adding/deleting arguments/attacks is allowed (deletions were not considered by [Oikarinen and Woltran, 2011; Baumann, 2012]).

7 Conclusion and FutureWork

We introduced a technique enabling any non-incremental algorithm to be used as an incremental one for computing some extension of dynamic AFs. Our work advanced existing approaches for computing extensions of dynamic AFs from two standpoints: (i) we considered general forms of updates (i.e., not limited forms of updates such as for instance weak expansions [Baumann, 2011]) and (ii) we identified a tighter portion of the updated AF to be examined for recomputing the semantics. For instance, the reduced AF is significantly smaller than the conditioned AF (CAF) in [Liao et al., 2011]. Additional experiments showed that the size of CAF is 91% of the size of the initial AF, while the size of the reduced AF is only 9%. Also, using the reduced AF is more efficient than using CAF: the run time of our technique turned out to be only 1% of the run time of using ICCMA solvers taking as input CAFs, that is, still two orders of magnitude faster.

Future work will be devoted to (i) applying our technique to other argumentation semantics and (ii) extending it to cope with other computational problems, such as enumerating all the extensions and deciding credulous/sceptical acceptance. As regard (i), our technique could be extended to deal with the ideal semantics [Dunne, 2009], for which experiments using ConArg [Bistarelli et al., 2016] as non-incremental solver showed performance improvements. As for (ii), preliminary experiments showed that on average only about 4% of the extensions of the updated AF are lost if we start from the set of all extensions of the initial AF. However, as even the loss of one extension may change the justification status of arguments, we plan to investigate restrictions on the structure of AFs guaranteeing that no extension is lost.