Incremental Computation of Deterministic Extensions for Dynamic Argumentation Frameworks

Abstract

We address the problem of efficiently recomputing the extensions of abstract argumentation frameworks (AFs) which are updated by adding/deleting arguments or attacks. In particular, after identifying some properties that hold for updates of AFs under several well-known semantics, we focus on the two most popular ‘deterministic’ semantics (namely, grounded and ideal) and present two algorithms for their incremental computation, well-suited to dynamic applications where updates to an initial AF are frequently performed to take into account new available knowledge. We experimentally validated the proposed approach.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Abstract argumentation has emerged as a central field in Artificial Intelligence [3, 10, 27, 39, 41, 42]. Although the underlying idea is very simple and intuitive, most of the semantics proposed so far suffer from a high computational complexity [22, 24–26, 29–33]. Complexity bounds and evaluation algorithms for argumentation frameworks (AFs) have been deeply studied in the literature, but this research focused on ‘static’ frameworks, whereas, in practice, AFs are not static systems [4, 5, 19, 28, 37]. Typically an AF represents a temporary situation as new arguments and attacks continuously can be added/removed to take into account new available knowledge. This may change significantly the conclusions that can be derived. For instance, when a new attack is added to an AF, existing attacks may cease to apply and new attacks become applicable. 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 can greatly improve performance. Sometimes changes to the AF can make small changes to the set of conclusions, and recomputing the whole semantics from scratch can be avoided. For instance, consider the situation shown in Fig. 1: the initial AF ${\mathcal {A}}_0$, where h is not attacked by any other argument, is updated to AF ${\mathcal {A}}$ by adding attack (g, h). According to the most popular argumentation semantics, i.e. grounded, complete, ideal, preferred, stable, and semi-stable [15, 20, 21], the initial AF ${\mathcal {A}}_0$ admits the extension $E_0=\{a,h,g,e,l,m,o\}$, whereas the extension for the updated framework ${\mathcal {A}}$ becomes $E=\{a,c,g,e,l,m,o\}$. As it will be shown later, for the grounded and ideal semantics, which are deterministic, the extension E can be efficiently computed incrementally by looking only at a small part of the AF, which is “influenced by” the update operation. This part is just $\{h,c\}$ in our example, and we will show that the membership of the other arguments to E does not depend on the update operation, and thus we do not need to compute them again after performing update $+(g,h)$.

Fig. 1.

AFs ${\mathcal {A}}_0$ and ${\mathcal {A}}=+(g,h)({\mathcal {A}}_0)$

Contributions. The main contributions are as follows:

• We introduce the concept of influenced set consisting of the arguments whose status could change after an update. The influenced set refines the previously proposed set of affected arguments [4, 37] and is used to compute extensions more efficiently.

• We present an incremental algorithm for recomputing the grounded extension. It is very efficient as it (iteratively) computes the status of influenced arguments only.

• We show that an argument a belongs to the ideal extension if and only if there is a coherent winning strategy for it and there is no coherent winning strategy for all arguments which attack (even indirectly) a.

• We present an incremental algorithm for the efficient recomputation of the ideal extensions which is based on the previously mentioned result and takes advantage of both the set of influenced arguments and the incremental algorithm for computing the grounded extensions.

• We report on experiments showing the effectiveness of our approach on both real and synthetic AFs.

2 Related Work

There have been several efforts coping with dynamics aspects of abstract argumentation. In [12, 13] the principles according to which the extension does not change when the set of arguments/attacks are changed have been studied. However, this work does not consider how the extensions of an AF evolve when new arguments are added or some of the old ones are removed. [17, 18] 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. However, they focus on adding only one argument interacting with one initial argument (i.e. an argument which is not attacked by any other argument). The work in [17, 18] has been extended in [11], where the evolution of the set of extensions after performing a change operation (addition/removal of arguments/interaction) is studied. Dynamic argumentation has been applied to decision-making of an autonomous agent in [1], where it is studied how the acceptability of arguments evolves when a new argument is added to the decision system. However, they do not compute the whole extensions and also focused on the case where only one argument is added to the system.

The division-based method, proposed in [37] and refined in [4], divides the updated framework into two parts: affected and unaffected, where only the status of affected arguments is recomputed after updates. However, the set of affected arguments consists of those that are reachable from the updated arguments, which is often larger than the set that actually needs to be considered when recomputing the extension. For the AF of Fig. 1, all the arguments in the chains originated by h turn out to be ‘affected’. But we only need to recompute the status of h and c after the update. Recently, [45] introduced a matrix representation of AFs and proposed a matrix reduction that when applied to dynamic AFs resembles the division-based method proposed in [37]. In [5, 9] an approach exploiting the concept of splitting of logic programs [38] was adopted to deal with dynamic argumentation. However, the technique considers weak expansions of the initial AF, where added arguments never attack previous ones. Recently, [16] studied the relationship between argumentation and logic programming [14, 34, 35].

[8] investigated whether and how it is possible to modify a given AF in such a way that a desired set of arguments becomes an extension, whereas [40] studied equivalence between two AFs when further information (another AF) is added to both simultaneously. [6] focused on specific expansions where new arguments and attacks may be added but the attacks among the old arguments remain unchanged, while [7] characterized update and deletion equivalence, where adding as well as deleting arguments and attacks is allowed (deletions were not considered in [6, 40]).

To the best of our knowledge, this is the first paper that exploits the initial extension $E_0$ of an AF ${\mathcal {A}}_0$ not only for computing the set ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ of arguments influenced by an update u but also for recomputing the status of the arguments in ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ by applying early termination conditions. A short version of this paper appeared in [36].

3 Preliminaries

We assume the existence of a set Arg whose elements are called arguments. An (abstract) argumentation framework [20] (AF) is a pair $\langle {A}, \varSigma \rangle$, where ${A}\subseteq Arg$ and $\varSigma \subseteq {A}\times {A}$ is a binary relation over ${A}$ whose elements are referred to as attacks. Essentially, an AF is a directed graph in which the arguments are represented by the nodes and the attack relation is represented by the set of directed edges. An argument is an abstract entity whose role is determined by its relationships with other arguments.

Given arguments $a,b\in {A}$, we say that a attacks b iff $(a,b)\in \varSigma$. An argument a attacks a set $S \subseteq {A}$ iff $\exists \, b\in S$ such that a attacks b. We use $S^+=\{b\ |\ \exists a\in S : (a,b)\in \varSigma \}$ and $S^-=\{b\ |\ \exists a\in S : (b,a)\in \varSigma \}$ to denote the sets of all arguments that are attacked by S and attack S, respectively. A set $S\subseteq A$ defends a iff $\forall b\in A$ such that b attacks a, there is $c\in S$ such that c attacks b. S is said to be (i) conflict-free, if there are no $a, b \in S$ such that a attacks b; (ii) admissible, if it is conflict-free and it defends all its arguments.

A semantics specifies the criteria for identifying a set of arguments considered to be “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: (i) $\textit{preferred (}{{\texttt {\textit{pr}}}}{} { {)}}$ iff it is maximal; (ii) $\textit{semi-stable (}{{\texttt {\textit{ss}}}}{} { {)}}$ iff $S\cup S^+$ is maximal; (iii) $\textit{stable (}{{\texttt {\textit{st}}}}{} { {)}}$ iff it attacks each argument in $A\setminus S$; (iv) $\textit{grounded (}{{\texttt {\textit{gr}}}}{} { {)}}$ iff it is minimal; (v) $\textit{ideal (}{{\texttt {\textit{id}}}}{} { {)}}$ iff it is contained in every preferred extension and it is maximal.

Given an AF ${\mathcal {A}}$ and a semantics ${\mathcal {S}}\in \!\{\texttt {co},\! \texttt {pr}, \texttt {ss}, \texttt {st}, \texttt {gr}, \texttt {id}\}$, we use ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}})$ to denote the set of ${\mathcal {S}}$-extensions of ${\mathcal {A}}$. All the above-mentioned semantics except the stable admit at least one extension, and the grounded and ideal admit exactly one extension [15, 20, 21]. Semantics $\texttt {gr}$ and $\texttt {id}$ are called deterministic or unique status as $|{\mathcal {E}}_\texttt {gr}({\mathcal {A}})|=|{\mathcal {E}}_\texttt {id}({\mathcal {A}})|=1$. It is well-known that, for any AF ${\mathcal {A}}$, ${\mathcal {E}}_\texttt {gr}({\mathcal {A}}) \subseteq {\mathcal {E}}_\texttt {co}({\mathcal {A}})$ and ${\mathcal {E}}_\texttt {id}({\mathcal {A}}) \subseteq {\mathcal {E}}_\texttt {co}({\mathcal {A}})$, and ${\mathcal {E}}_\texttt {st}({\mathcal {A}}) \subseteq {\mathcal {E}}_\texttt {ss}({\mathcal {A}}) \subseteq {\mathcal {E}}_\texttt {pr}({\mathcal {A}}) \subseteq {\mathcal {E}}_\texttt {co}({\mathcal {A}})$.

Example 1

Consider the AF ${\mathcal {A}}_0$ shown in Fig. 2. Then, the set of admissible sets is $\{\ \emptyset ,\ \{a\},\ \{d\},\ \{a,d\},\ \{b,d\}\ \}$, and ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ with ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}, \texttt {gr}, \texttt {id}\}$ is as reported in the second column of the table in Fig. 3. $\Box$

Fig. 2.

AF ${\mathcal {A}}_0$ of Example 1.

Fig. 3.

Sets of extensions for the AF of Example 1, and changes in the sets after performing updates $+(b,d)$ and $-(c,b)$.

The argumentation semantics can be also defined in terms of labelling. A labelling for an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ is a total function $L :{A}\rightarrow \{ \textsc {in}, \textsc {out}, \textsc {un}\}$ assigning to each argument a label. $L(a)=\textsc {in}$ means that argument a is accepted, $L(a)=\textsc {out}$ means that a is rejected, while $L(a)=\textsc {un}$ means that a is undecided.

Let $in(L)=\{a\ |\ a\in {A}\wedge L(a)=\textsc {in}\}$, $out(L)=\{a\ |\ a\in {A}\wedge L(a)=\textsc {out}\}$, and $un(L)=\{a\ |\ a\in {A}\wedge L(a)=\textsc {un}\}$. In the following, we also use the triple $\langle in(L), out(L), un(L)\rangle$ to represent L. A labelling L is said to be admissible (or legal) if $\forall a \in in(L) \cup out(L)$ (i) if $L(a)=\textsc {out}$ then $\exists \, b\in {A}$ such that $(b,a)\in \varSigma$ and $L(b)=\textsc {in}$; and (ii) if $L(a)=\textsc {in}$ then $L(b)=\textsc {out}$ for all $b\in {A}$ such that $(b,a)\in \varSigma$. L is a complete labelling iff conditions (i) and (ii) hold for all $a \in {A}$.

Between complete extensions and complete labellings there is a bijective mapping defined as follows: for each extension E there is a unique labelling $L = \langle E, E^+, {A}\setminus (E \cup E^+)\rangle$ and for each labelling L there is a unique extension in(L). We say that L is the labelling corresponding to E.

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 $\textsc {in}$ (resp., $\textsc {out}$, $\textsc {un}$) iff $L(a)=\textsc {in}$ (resp., $L(a)=\textsc {out}$, $L(a)=\textsc {un}$). We will avoid to mention explicitly the labelling (or the extension) whenever it is understood.

Updates. An update u for an AF ${\mathcal {A}}_0$ consists in modifying ${\mathcal {A}}_0$ into an AF ${\mathcal {A}}$ by adding or removing arguments or attacks. As explained below, we can focus on updates consisting of adding/deleting an attack (a, b) between arguments belonging to ${\mathcal {A}}_0$ . We use $+(a,b)$ (resp. $-(a,b)$) to denote the addition (resp. deletion) of (a, b), and $u({\mathcal {A}}_0)$ to denote the application of update $u=\pm (a,b)$ to ${\mathcal {A}}_0$ (with ± meaning either $+$ or −).

Updating an AF implies that its semantics (sets of extensions or labellings) changes.

Example 2

Consider the AF ${\mathcal {A}}_0$ of Example 1. For each semantics ${\mathcal {S}}$, the set ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_1)$ of extensions for ${\mathcal {A}}_1=+(b,d)({\mathcal {A}}_0)$ is reported in the third column in Fig. 3. If update $-(c,b)$ is performed on ${\mathcal {A}}_1$, then ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_2)$ with ${\mathcal {A}}_2=-(c,b)({\mathcal {A}}_1)$ is as shown on the last column in Fig. 3.  $\Box$

Remark (general updates). It is worth noting that focusing on single attack updates of the form $u=\pm (a,b)$ is not a limitation as multiple (attack) updates to be performed simultaneously can be simulated by performing a single attack update to a new AF obtained by suitably modifying the initial AF ${\mathcal {A}}_0$. In fact, performing a set of updates $U=\{+(a_1,b_1),\dots ,+(a_n,b_n),$ $-(a_1',b_1'),$ $\dots ,-(a_m',b_m')\}$ on ${\mathcal {A}}_0$ can be reduced to performing a single update $+(v,w)$ on the AF ${\mathcal {A}}_0^U$ which is obtained from ${\mathcal {A}}_0$ by (i) adding arguments $x_i, y_i$ and the chain of attacks between $a_i$ and $b_i$ as shown in Fig. 4, for each update $+(a_i,b_i)\in U$; (ii) replacing each attack $(a_j',b_j')$ in ${\mathcal {A}}_0$ with the chain of attacks between $a_j'$ and $b_j'$ as shown in Fig. 4, for each update $-(a_j',b_j')\in U$; and (iii) adding the new arguments $v,w,w'$ and the attacks involving them as shown in Fig. 4. For instance, for the AF ${\mathcal {A}}_0$ of Example 1 and the set of updates $U=\{+(b,d),$ $-(c,b)\}$, we obtain the AF ${\mathcal {A}}_0^U$ shown in Fig. 5. The formal definition of the construction above as well as proofs of equivalence (${\mathcal {A}}_0$ and ${\mathcal {A}}_0^U$ have the same extensions under projection to the arguments of ${\mathcal {A}}_0$) will be provided in the extended version of this paper.

Fig. 4.

Simulating multiple updates by a single one.

Fig. 5.

${\mathcal {A}}_0^U$ for U=$\{+(b,d),-(c,b)\}$.

Concerning the addition (resp. deletion) of a set of isolated arguments, it is easy to see that if ${\mathcal {A}}$ is obtained from ${\mathcal {A}}_0$ through the addition (resp. deletion) of a set S of isolated arguments, then, let $E_0$ be an extension for ${\mathcal {A}}_0$, $E = E_0 \cup S$ (resp. $E = E_0 \setminus S$) is an extension for ${\mathcal {A}}$ that can be trivially computed. Of course, if arguments in S are not isolated, we can first delete all attacks involving arguments in S; adding an attack between an argument in ${\mathcal {A}}_0$ and a new argument can be simulated as well. In our experiments we have considered both single and multiple attack updates.

4 Influenced Arguments

In this section, we first identify conditions ensuring that a given ${\mathcal {S}}$-extension continues to be an ${\mathcal {S}}$-extension after an update, and then introduce the influenced set that will be used to limit the set of arguments that needs to be recomputed after an update.

The following two propositions introduce sufficient conditions guaranteeing that a given ${\mathcal {S}}$-extension is still an ${\mathcal {S}}$-extension after performing an update.

Proposition 1

Let ${\mathcal {A}}_0$ be an AF, $u = +(a,b)$ an update, ${\mathcal {S}}$ a semantics, $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under semantics ${\mathcal {S}}$, and $L_0$ the labelling corresponding to $E_0$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if

• ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {st}, \texttt {gr}\}$ and one of the following conditions holds:

  • $L_0(a)\ne \textsc {in}$ and $L_0(b)\ne \textsc {in}$,

  • $L_0(a)=\textsc {in}$ and $L_0(b)=\textsc {out}$;

• ${\mathcal {S}}\in \!\{ \texttt {pr}, \texttt {ss}, \texttt {id} \}$ and $L_0(b)=\textsc {out}$.

Proposition 2

Let ${\mathcal {A}}_0$ be an AF, $u = -(a,b)$, ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}, \texttt {gr}\}$, and $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under ${\mathcal {S}}$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if one of the following conditions holds: 1) $L_0(a)\!=\!\textsc {out}$; 2) $L_0(a)\!=\!\textsc {un}$ and $L_0(b)\!=\!\textsc {out}$.

Example 3

Consider the AFs ${\mathcal {A}}_1\!=\!+(b,d)({\mathcal {A}}_0)$ and ${\mathcal {A}}_2\!=\!-(c,b)({\mathcal {A}}_1)$, where ${\mathcal {A}}_0$ is the AF of Example 2. For ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}\}$, extension $\{a,d\}$ of ${\mathcal {A}}_1$ is still an extension of ${\mathcal {A}}_2$ as $L_0(c)\!=\!\textsc {out}$ (see Fig. 3). The grounded extension $\emptyset$ of ${\mathcal {A}}_1$ is still a grounded extension of ${\mathcal {A}}_2$, whereas the ideal extension $\{a,d\}$ of ${\mathcal {A}}_1$ is not the ideal extension of ${\mathcal {A}}_2$.  $\Box$

Given an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ and an argument $b \in {A}$, we denote as $Reach\!\!_{_{\mathcal {A}}}\!(b)$ the set of arguments that are reachable from b in ${\mathcal {A}}$. We now introduce the influenced set.

Definition 1 (Influenced set)

Let ${\mathcal {A}}= \langle {A}, \varSigma \rangle$ be an AF, $u = \pm (a,b)$ an update, E an extension of ${\mathcal {A}}$ under a given semantics ${\mathcal {S}}$, and let

• ${\mathcal {I}}_0(u,{\mathcal {A}},E)\! = \! { {\left\{ \begin{array}{ll} \emptyset \ \ \text{ if }\ E \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}))\ \ \text{[e.g., } \text{ the } \text{ conditions } \text{ of } \text{ Prop. } \text{1/2 } \text{ hold] } or\ \\ \ \ \ \exists (z,b)\in \varSigma \ s.t.\ z\in E \wedge z\not \in Reach\!\!_{_{\mathcal {A}}}\!(b); \\ \{ b \}\ otherwise; \end{array}\right. }}$

• ${\mathcal {I}}_{i+1}(u,{\mathcal {A}},E) = {\mathcal {I}}_i(u,{\mathcal {A}},E) \cup \{y \ | \ \exists (x,y)\in \varSigma \ s.t.\ x\in {\mathcal {I}}_i(u,{\mathcal {A}},E )\ \wedge \not \exists (z,y)\in \varSigma \ s.t.\ z\in E \wedge z\not \in Reach\!\!_{_{\mathcal {A}}}\!(b) \}$.

The influenced set of u w.r.t. ${\mathcal {A}}$ and E is ${\mathcal {I}}(u,{\mathcal {A}},E) = {\mathcal {I}}_{n}(u,{\mathcal {A}},E)$ such that ${\mathcal {I}}_n(u,{\mathcal {A}},E)$ = ${\mathcal {I}}_{n+1}(u,{\mathcal {A}},E)$. $\Box$

Thus, the set of arguments that are influenced by an update of the status of b are those that can be reached from b without using any intermediate argument y whose status is known to be out because it is determined by an argument $z\in E$ which is not reachable from (and thus not influenced by) b.

Example 4

For the AF ${\mathcal {A}}_0=\langle {A}_0, \varSigma _0 \rangle$ of Fig. 1, whose grounded extension is $E_0=\{a,h,g,e,l,m,o\}$, we have that $Reach\!\!_{{_{\mathcal {A}}}_0}\!(h)\! =\! {A}_0 \setminus \{ a,b\}$, and the influenced set of $u = +(g,h)$ is ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0) = \{h,c\}$. Note that $d\not \in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ since it is attacked by $a\in E_0$. Thus the arguments that can be reached only using d cannot belong to ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ either. For ${\mathcal {A}}=u({\mathcal {A}}_0)$, whose grounded extension is $E=\{a,c,g,e,l,m,o\}$, we have that $S = {\mathcal {I}}(u,{\mathcal {A}},E)$ is still $\{h,c\}$. Therefore, only the status of arguments in S could change and their status can be determined by considering a restricted AF containing only arguments in $S \cup S^-$. $\Box$

Proposition 3

Given an AF ${\mathcal {A}}= \langle {A}, \varSigma \rangle$, an update $u = \pm (a,b)$, and an extension E, the complexity of computing the influenced set of u w.r.t. ${\mathcal {A}}$ and E is $O(|\varSigma |)$.

All the arguments not belonging to the influenced set of an update will still belong to an extension of the updated AF.

Theorem 1

Let ${\mathcal {A}}_0$ be an AF, and ${\mathcal {A}}=u({\mathcal {A}}_0)$ be the AF resulting from performing update $u=\pm (a,b)$ on ${\mathcal {A}}_0$. Let $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ be an extension for ${\mathcal {A}}_0$ under any semantics ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}, \texttt {gr}, \texttt {id}\}$. Let ${{\overline{\mathcal {I}}}}=Arg\setminus {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ be the set of the arguments that are not influenced by u in ${\mathcal {A}}_0$ w.r.t. $E_0$. Then, either ${\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}) = \emptyset$ or there is an extension $E \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}})$ for ${\mathcal {A}}$ such that $(E\cap {\overline{\mathcal {I}}})=(E_0\cap {\overline{\mathcal {I}}})$.

We conclude this section by introducing a refinement of Proposition 1.

Proposition 4

Let ${\mathcal {A}}_0$ be an AF, $u = +(a,b)$, ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}, \texttt {gr}\}$, and $E_0 \in {\mathcal {E}}_{\mathcal {S}}({\mathcal {A}}_0)$ an extension of ${\mathcal {A}}_0$ under ${\mathcal {S}}$. Then $E_0 \in {\mathcal {E}}_{\mathcal {S}}(u({\mathcal {A}}_0))$ if one of the conditions of Proposition 1 holds or all the next three conditions hold: (1) $L_0(a)=\textsc {out}$, (2) $L_0(b) = \textsc {in}$ and (3) either (i) ${\mathcal {S}}\in \{ \texttt {co}, \texttt {st}, \texttt {ss},$ $\texttt {pr} \}$ or (ii) $a \not \in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ and ${\mathcal {S}}=\texttt {gr}$.

Example 5

Consider AFs ${\mathcal {A}}_0$ and ${\mathcal {A}}_1\!\!=\!\!+(b,d)({\mathcal {A}}_0)$ of Examples 1 and 3. For ${\mathcal {S}}\in \!\{\texttt {co}, \texttt {pr}, \texttt {ss}, \texttt {st}\}$, extension $E_0=\{a,d\}$ for ${\mathcal {A}}_0$ is still an extension of the AF ${\mathcal {A}}_1$ as $L_0(b)=\textsc {out}$ and $L_0(d)=\textsc {in}$ (see Fig. 3). However, the grounded extension $E'_0=\{d\}$ for ${\mathcal {A}}_0$ is not guaranteed to be a grounded extension for ${\mathcal {A}}_1$ as neither Proposition 1 nor conditions (1) and 3.(ii) of Proposition 4 hold (b is un and $b \in {\mathcal {I}}(+(b,d),{\mathcal {A}}_0,E'_0)$).

5 Recomputing Unique Status Semantics

Given an AF ${\mathcal {A}}_0$, a deterministic semantics ${\mathcal {S}}\in \!\{\texttt {gr}, \texttt {id}\}$, the extension $E_0$ for ${\mathcal {A}}_0$ under ${\mathcal {S}}$, an update u for ${\mathcal {A}}_0$ yielding ${\mathcal {A}}= u({\mathcal {A}}_0)$, we address the problem of efficiently computing the ${\mathcal {S}}$-extension E of the updated AF ${\mathcal {A}}$ starting from $E_0$.

For any AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$ and set $S \subseteq {A}$ of arguments, we denote with $\varPi (S,{\mathcal {A}}) = \langle S, \varSigma \cap S \times S \rangle$ the subgraph of ${\mathcal {A}}$ induced by the nodes in S. Moreover, given two AFs ${\mathcal {A}}_1 = \langle {A}_1,\varSigma _1\rangle$ and ${\mathcal {A}}_2 = \langle {A}_2,\varSigma _2\rangle$, we denote as ${\mathcal {A}}_1 \sqcup {\mathcal {A}}_2 = \langle {A}_1 \cup {A}_1,\varSigma _1 \cup \varSigma _2\rangle$ the union of the two AFs.

5.1 Grounded Semantics

Our algorithm first identifies the restricted subgraph of the given AF containing the arguments influenced by the update.

Definition 2 (Restricted AF for grounded semantics)

Given an AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$, a grounded extension E for ${\mathcal {A}}$, and an update $u = \pm (a,b)$, the restricted AF of ${\mathcal {A}}$ w.r.t. E and u (denoted as ${\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}},E)$) is as follows.

• ${\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}},E)$ is empty if ${\mathcal {I}}(u,{\mathcal {A}},E)=\emptyset$ or one of the conditions of Proposition 4 holds.

• ${\mathcal {R}}\!_{\texttt {gr}}\!(u,{\mathcal {A}},E)=\varPi ({\mathcal {I}}(u,{\mathcal {A}},E),u({\mathcal {A}}))\sqcup T_1 \sqcup T_2$ where:

  • $T_1$ is the union of the AFs $\langle \{a,b\}, \{ (a,b) \}\rangle$ s.t. (a, b) is an attack of $u({\mathcal {A}})$ and $a \not \in {\mathcal {I}}(u,{\mathcal {A}},E)$, $a \in E$, and $b \in {\mathcal {I}}(u,{\mathcal {A}},E)$;

  • $T_2 = \langle \{ c\, |\, Check(c) \}, \{ (c,c)\, |\, Check(c) \} \rangle$, where Check(c) is true if $\exists (e,c) \in \varSigma$ such that $c \in {\mathcal {I}}(u,{\mathcal {A}},E)$ and $e \not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ and $e \not \in E \cup E^+$. $\Box$

Hence, AF ${\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}},E)$ contains, in addition to the subgraph of $u({\mathcal {A}})$ induced by ${\mathcal {I}}(u,{\mathcal {A}},E)$, 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 ${\mathcal {I}}(u,{\mathcal {A}},E)$. Specifically, if there is in $u({\mathcal {A}})$ an edge from node $a\not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ whose status in $\textsc {in}$ to node $b\in {\mathcal {I}}(u,{\mathcal {A}},E)$, then we add the edge (a, b) so that, as a does not have incoming edges in ${\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}},E)$, its status is confirmed to be $\textsc {in}$. Moreover, if there is in $u({\mathcal {A}})$ an edge from a node $e\not \in {\mathcal {I}}(u,{\mathcal {A}},E)$ to $c\in {\mathcal {I}}(u,{\mathcal {A}},E)$ such that e is $\textsc {un}$, we add edge (c, c) to ${\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}},E)$ so that the status of c cannot be $\textsc {in}$. Using fake arguments/attacks to represent external contexts has been exploited in a similar way in [2], where decomposability properties of argumentation semantics are studied.

Example 6

Continuing Example 4, ${\mathcal {R}}\!_{\texttt {gr}}(+(g,h),{\mathcal {A}}_0,E_0)$ consists of the subgraph induced by ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0) = \{h,c\}$ as well as the edge (g, h) which is an attack towards argument $h\in {\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ coming from argument g outside ${\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ labelled as $\textsc {in}$. Hence, ${\mathcal {R}}\!_{\texttt {gr}}(+(g,h),{\mathcal {A}}_0,E_0) = \langle {A}_d, \varSigma _d\rangle$ with ${A}_d=\{g,h,c\}$ and $\varSigma _d=\{(g,h),(h,c)\}$.

Example 7

Consider the AF ${\mathcal {A}}_0 = \langle \{a,b,c,d,e,f,g\},$ $\{ (a,b), (b,a), (c,d), (d,c), (a,c),$ $(b,c), (f,c), (g,f) \} \rangle$ and the update $u = +(e,d)$. We have that (i) the grounded extension of ${\mathcal {A}}_0$ is $E_0 = \{ g, e \}$ (i.e. arguments a, b, c, d are all labeled as $\textsc {un}$); (ii) the influenced set is ${\mathcal {I}}(u,{\mathcal {A}}_0, E_0) = \{ c, d \}$; and (iii) the restricted AF is ${\mathcal {R}}_\texttt {gr}(u,{\mathcal {A}}_0, E_0) = \langle \{c,d\},\{(c,d),$ $(d,c)\}\rangle \sqcup T_1\sqcup T_2$ where $T_1=\langle \{e,d\},$ $\{(e,d)\}\rangle$ and $T_2=\langle \{c\},\{(c,c)\}\rangle$. That is, ${\mathcal {R}}_\texttt {gr}(u,{\mathcal {A}}_0, E_0)\!\!=\!\!\langle \{ c, d, e \},\ \{ (c,d),$ (d, c),  $(e,d), (c,c) \} \rangle$. $\Box$

Algorithm 1 first checks if the restricted AF (computed w.r.t. update $u=\pm (a,b)$) is empty (Line 3). If this is the case, then $E=E_0$. Otherwise, the status of arguments in $S={\mathcal {I}}(u,{\mathcal {A}}_0,E_0)$ needs to be recomputed and the extension E of $u({\mathcal {A}}_0)$ is constructed at Line 4 by combining the arguments in $E_0$ not belonging to the influenced part and the arguments returned by Function IFP (incremental fixpoint), which is invoked with AF ${\mathcal {A}}_d=\langle {A}_d,\varSigma _d\rangle$ (the restricted graph of ${\mathcal {A}}$) and starting extension $E_0 \cap {A}_d$ (the restriction of $E_0$ to ${A}_d$). Function IFP first computes the initial set of nodes which are labelled $\textsc {in}$ or $\textsc {out}$. If no argument can be labelled $\textsc {in}$, it returns the empty set. Otherwise, it iteratively applies function G that takes as input the set of arguments $S_\textsc {out}$ which have been labeled $\textsc {out}$ so far and the subset $\varDelta _\textsc {out}\subseteq S_\textsc {out}$ of arguments which have been labelled out in the last step, and returns the arguments $b \in \varDelta _\textsc {out}^+$ such that for every attack $(a,b)\in \varSigma$, argument $a \in S_\textsc {out}$ (i.e. a is labelled $\textsc {out}$). Similarly to the characteristic function of an AF [20], function G infers new arguments that can be labelled $\textsc {in}$; but it is more efficient as it only uses arguments labelled in the last step. Function G returns the set $\varDelta _\textsc {in}$ of arguments which are labeled $\textsc {in}$ at Line 5. Arguments labeled $\textsc {out}$ are immediately derived by taking $\varDelta _\textsc {in}^+$, that is the arguments which are attacked by some argument which has been labelled as $\textsc {in}$ (Line 6). Function G is iteratively applied until, in the last step of the repeat loop, all arguments derived are confirmed to be in the extension $E_0$ of the AF ${\mathcal {A}}_0$ being updated (i.e., $\varDelta _\textsc {in}\subseteq E_0$).

Example 8

Consider the AF ${\mathcal {A}}_0$ of Fig. 1 where $E_0=\{a,h,g,e,l,m,o\}$ and ${\mathcal {I}}(u,{\mathcal {A}}_0,$ $E_0) = \{h,c\}$. Algorithm 1 computes the grounded extension E of the AF ${\mathcal {A}}=+(g,h)({\mathcal {A}}_0)$ as follows. The restricted AF ${\mathcal {A}}_d$ = $\langle {A}_d, \varSigma _d\rangle = {\mathcal {R}}\!_{\texttt {gr}}(u,{\mathcal {A}}_0,E_0)$ is computed (at Line 2) obtaining ${A}_d=\{g,h,c\}$ and $\varSigma _d=\{(g,h),(h,c)\}$. As ${A}_d$ is not empty, Function IFP with actual parameters ${\mathcal {A}}_d$ and $E_0 \cap {A}_d = \{g,h\}$ is called at Line 4. Function IFP first computes $S_\textsc {in}=\varDelta _\textsc {in}=\{ g \}$ and $S_\textsc {out}=\varDelta _\textsc {out}=\{ h\}$. Next, at the first iteration of the repeat loop, it is computed $\varDelta _\textsc {in}= G(\{ h\},\{ h\})=\{c\}$ (Line 5) and $\varDelta _\textsc {out}=\emptyset$ (Line 6) as there is no argument attacked by c in ${\mathcal {A}}_d$. The loop is entered a second time, where $\varDelta _\textsc {in}$ stay empty and the until-condition is fulfilled. Then the function returns the set $\{ g,c \}$ and E turns out to be the set $\{a,g,e,l,m,o\} \cup \{g,c\}$.

Theorem 2

For any AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$, the complexity of computing IFP(${\mathcal {A}}, E_0$), with $E_0\subset {A}$, is $O(|{A}| \times \bar{d}\,^2 )$, where $\bar{d}$ is the maximum input degree of a node (i.e., the maximum number of attacks towards an argument in ${A}$).

Theorem 3

For any AF ${\mathcal {A}}_0 = \langle {A}_0,\varSigma _0\rangle$ with grounded extension $E_0$, and $u=\pm (a,b)$, the complexity of Algorithm Incr-Grounded-Sem( ${\mathcal {A}}_0, u, E_0$ ) is $O(|\varSigma _0| + |{\mathcal {I}}(u,{\mathcal {A}}_0,E_0)| \times \bar{d}\,^2 )$, where $\bar{d}$ is the maximum input degree of a node.

Theorem 4

Given an AF ${\mathcal {A}}_0$, an update $u=\pm (a,b)$ for ${\mathcal {A}}_0$ yielding ${\mathcal {A}}$=$u({\mathcal {A}}_0)$, and the grounded extension $E_0$ of ${\mathcal {A}}_0$, Algorithm 1 computes the grounded extension E of ${\mathcal {A}}$.

5.2 Ideal Semantics

Before introducing the restricted AF for ideal semantics, denoted as ${\mathcal {R}}_{id}(u,{\mathcal {A}},E)$, we define the paths, providing the information on the “context” outside the influenced set $S = {\mathcal {I}}(u,{\mathcal {A}},E)$, that need to be added to determine the new status of arguments in S. Given an AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$ with ideal extension E and a set $S \subseteq {A}$, $Node({\mathcal {A}},S,E)$ (resp. $Edge({\mathcal {A}},S,E)$) denotes a set of arguments $x_1,...,x_n$ (resp. attacks $(x_1,x_2), ...,$ $(x_{n-1},x_n)$) in ${\mathcal {A}}$ such that there is a path $x_1 \ldots x_n$ in ${\mathcal {A}}$ with $x_n \in S$, $x_1,\ldots ,x_{n1} \not \in S$ and $x_1,...,x_{n1} \not \in E \cup E^+$ (i.e., $x_1,...,x_{n1}$ are un). Essentially, if S is the influenced set of an update, to determine the status of nodes in S we must also consider all nodes and attacks occurring in paths (of any length) ending in S whose nodes outside S are all labeled as un. The motivation to also consider the paths ending in S is that some of the undecided arguments occurring in these paths could be labelled $\textsc {in}$ or $\textsc {out}$ in some preferred labelling and, therefore, together they could determine a change in the status of nodes in S.

Definition 3 (Restricted AF for ideal semantics)

Given an AF ${\mathcal {A}}= \langle {A},\varSigma \rangle$, an ideal extension E for ${\mathcal {A}}$ and an update $u = \pm (a,b)$, the restricted AF of ${\mathcal {A}}$ w.r.t. E and u (denoted as ${\mathcal {R}}\!_{\texttt {id}}(u,{\mathcal {A}},E)$) is as follows.

• ${\mathcal {R}}\!_{\texttt {id}}(u,{\mathcal {A}},E)$ is empty if ${\mathcal {I}}(u,{\mathcal {A}},E)$ is empty.

• ${\mathcal {R}}\!_{\texttt {id}}\!(u,{\mathcal {A}},E)=\varPi ({\mathcal {I}}(u,{\mathcal {A}},E),u({\mathcal {A}}\!))\sqcup T_1 \sqcup T_2$ where, let $S = {\mathcal {I}}(u,{\mathcal {A}},E)$:

  • $T_1$ is the union of the AFs $\langle \{a,b\}, \{ (a,b) \}\rangle$ s.t. (a, b) is an attack of $u({\mathcal {A}})$ and $a \not \in {\mathcal {I}}(u,{\mathcal {A}},E)$, $a \in E$, and $b \in {\mathcal {I}}(u,{\mathcal {A}},E)$;

  • $T_2$ is the union of the AFs $\langle Node({\mathcal {A}},S,E), Edge({\mathcal {A}},S,E) \rangle$. $\Box$

Example 9

Continuing Example 7 we have that (i) the ideal extension of ${\mathcal {A}}$ is $E'_0 = \{ g, e, d \}$ (i.e. arguments a and b are both labeled as $\textsc {un}$); and (ii) the restricted AF is ${\mathcal {R}}_\texttt {id}(u,{\mathcal {A}}_0, E'_0) \!\!=\!\! \langle \{c,d\},\{(c,d),$ $(d,c)\}\rangle \sqcup T_1\sqcup T_2$ where $T_1\!\!=\!\!\langle \{e,d\},$ $\{(e,d)\}\rangle$ and $T_2\!=\!\langle \{a,b,c\},\{(a,b),(b,c),(b,a),(a,c)\}\rangle$. That is, ${\mathcal {R}}_\texttt {id}(u,{\mathcal {A}}_0, E'_0) = \langle \{a,b,c,d, e\},$ $\{ (a,b),$ $(b,a), (c,d),(d,c),(a,c),(b,c),(e,d)\} \rangle$. $\Box$

Once identified the restricted AF, our algorithm for computing the ideal extension uses the novel concept of coherent winning strategy (CWS) that we introduce below after briefly recalling Two Party Immediate Response Disputes [23, 44].

In a dispute two players, proponent (PRO) and opponent (OPP), move arguments to each other. A dispute for an argument $a_1$ is a sequence of arguments $d=a_1,\dots , a_n$ where $a_1$ is moved by PRO and consecutive arguments $a_i,a_{i+1}$ in d are such that $(a_{i+1},a_i)\in \varSigma$ and are moved by different players. A dispute is legal iff i) OPP never uses the same argument twice, and ii) PRO never uses a self-attacking argument or an argument attacking one previously used by him.

Given an AF ${\mathcal {A}}=\langle {A}, \varSigma \rangle$ and an argument $a \in {A}$, the dispute tree $T(a,{\mathcal {A}})$ for ${\mathcal {A}}$ is the maximal tree whose root is a and whose branches (disputes) are legal disputes for a. For any subtree t of $T(a,{\mathcal {A}})$, we denote by $\textit{PRO}(t)$ (resp. $\textit{OPP}(t)$) the set of arguments moved by PRO (resp., OPP) occurring in t. Moreover, $ST(a,{\mathcal {A}})$ denotes the set of subtrees w derived from $T(a,{\mathcal {A}})$ by pruning branches in such a way that each node in OPP(w) has only one child node (the set of child nodes of any node in PRO(w) remains the same).

Definition 4 (Coherent Winning Strategy (CWS))

Let ${\mathcal {A}}=\langle {A}, \varSigma \rangle$ and $a \in {A}$. A subtree $w \in ST(a,{\mathcal {A}})$ is a winning strategy for a iff all leaf nodes of w belong to $\textit{PRO}(T(a,{\mathcal {A}}))$. w is said to be coherent w.r.t. $E\subseteq {A}$ iff (i) $\textit{PRO}(w) \cap E^+ = \emptyset$ and (ii) $\textit{OPP}(w) \cap E = \emptyset$. The set of CWSs for a in ${\mathcal {A}}$ w.r.t. E is denoted as ${\mathcal {CW\!}}(a,{\mathcal {A}},E)$. $\Box$

Checking whether an argument belongs to the ideal extension of an updated AF can be accomplished using CSWs.

Theorem 5

Let ${\mathcal {A}}_0= \langle {A}_0, \varSigma _0 \rangle$, $E_0$ the ideal extension of ${\mathcal {A}}_0$, $u\!=\!\pm (a,b)$, $S = {\mathcal {I}}(u,{\mathcal {A}}_0,$ $E_0)$, and ${\mathcal {A}}\!=\!u({\mathcal {A}}_0)$. Then, the ideal extension E of ${\mathcal {A}}$ contains argument c iff there is a CWS $w \in {\mathcal {CW\!}}(c,{\mathcal {R}}\!_\texttt {id}(u,{\mathcal {A}}_0,E_0),E_0\setminus S)$ such that $\forall c' \in \textit{OPP}(w)$, $\not \exists$ CWS $w' \in {\mathcal {CW\!}}(c',{\mathcal {R}}\!_\texttt {id}(u,{\mathcal {A}}_0,E_0),E_0\setminus S)$.

A CWS $w \in {\mathcal {CW\!}}(c,{\mathcal {A}},E)$ is successful if it satisfies the condition of Theorem 5.

Corollary 1

Let ${\mathcal {A}}_0= \langle {A}_0, \varSigma _0 \rangle$, $E_0$ the ideal extension of ${\mathcal {A}}_0$, and $u=\pm (a,b)$ an update. Then, $\textit{PRO}(w) \subseteq E$ where E is the ideal extension of ${\mathcal {A}}=u({\mathcal {A}}_0)$ and w is a successful CWS in ${\mathcal {CW\!}}(c,{\mathcal {R}}\!_\texttt {id}(u,{\mathcal {A}}_0,E_0), E_0\setminus {\mathcal {I}}(u,{\mathcal {A}},E_0))$.

Algorithm 2 computes the ideal extension E of an updated AF ${\mathcal {A}}= u({\mathcal {A}}_0)$ using the ideal extension $E_0$ of AF ${\mathcal {A}}_0$. It starts by identifying the set S of arguments whose status need to be recomputed (Line 2) and the starting extension that will be iteratively incremented to obtain the ideal extension (Line 3). It first checks if the influenced set is empty (Line 4); in such a case $E = E_0$ and then it stops. If this is not the case, it iterates to reach a fixpoint. At each step it first computes the grounded semantics (lines 6–9) and next search for a CWS for some unlabelled argument (lines 10–16). More specifically, before computing the grounded semantics (Line 7), the (restricted) AF is computed using ${\mathcal {R}}\!_\texttt {gr}$ (Line 6). Using the result of Function IFP, extension E and the set S of unlabelled arguments are updated at lines 8-9 by including in the current ideal extension E all the arguments belonging to the grounded extension $\varDelta _\textsc {in}$ and removing from S all new arguments that have been decided. Analogously, before searching for a successful CWS (Line 12), the restricted AF is computed using ${\mathcal {R}}\!_\texttt {id}$ (Line 10). Finally, the existence of a successful CWS w is exploited for updating extension E and the set S of unlabelled arguments (lines 14–16).

Theorem 6

Given an AF ${\mathcal {A}}_0$ whose ideal extension is $E_0$, and an update $u=\pm (a,b)$ such that $u({\mathcal {A}}_0) = {\mathcal {A}}$, Algorithm 2 computes the ideal extension E of ${\mathcal {A}}$.

Fig. 6.

Run times (ms) of BaseG and IncrG for 1, 20, and 40 updates over REAL.

6 Experiments

We implemented a prototype for incremental computation of argumentation semantics using the Java argumentation libraries provided by the Tweety project [43].

Datasets. For the experiments on the grounded semantics, we used two datasets provided as benchmarks at ICCMA (http://argumentationcompetition.org): (i) REAL consists of 19 AFs $\langle {A}_0, \varSigma _0\rangle$ with $|{A}_0|\in [5K,100K]$ and $|\varSigma _0|\in [7K,143K]$; (ii) SYN1 consists of 24 AFs $\langle {A}_0, \varSigma _0\rangle$ with $|{A}_0|\in [1K,4K]$ and $|\varSigma _0|\in [14K,172K]$. The AFs in the two datasets have a different structure: on average, $| Reach_{{\mathcal {A}}_0}(a)|$ is around 2200 for arguments a in SYN1, while it is about 10 for REAL; moreover, the average number of attacks per argument for REAL is 1.5 while it is 26 for SYN1.

For the experiments on the ideal semantics, we built dataset SYN2 that consists of AFs whose size is smaller than those in REAL and SYN1 because computing the initial ideal extension for the datasets above is prohibitive due to its exponential complexity (specifically, computing the ideal extension is $FP^{NP}_{||}$-hard [22]). SYN2 consists of 20 AFs for each of the number of arguments in $\{50, 75, \dots ,175\}$. Each AF in SYN2 was obtained by first generating its arguments and then adding for each argument on average 2 attacks toward arguments in the AF being generated. Finally, for each argument not yet connected, an attack from or to this argument from the others was added.

Fig. 7.

Run times (ms) of BaseG and IncrG for 1, 20, and 40 updates over SYN1.

Fig. 8.

Run times (ms) of BaseI and IncrI for 1 and 5 updates over SYN2

Algorithms. For each AF ${\mathcal {A}}_0=\langle {A}_0, \varSigma _0\rangle$ in each dataset, we first computed the grounded (resp. ideal) extension $E_0$. Then, when considering a single update, we randomly selected an update u of the form $+(a,b)$ (with $a,b\in {A}_0$ and $(a,b) \not \in \varSigma _0$) or $-(a,b)$ (with $(a,b)\in \varSigma _0$). For the case of multiple updates, we randomly generated a set U of updates of the above form. Next, we executed the following algorithms:

• BaseG and BaseI which compute, respectively, the grounded and ideal semantics E of the updated AF $u({\mathcal {A}}_0)$ from scratch (these algorithms were also used to compute the initial extension $E_0$ which is taken as input by the incremental algorithms). BaseG finds the fixpoint of the characteristic function of an AF as implemented in the libraries of Tweety [43], while BaseI uses the algorithm implemented by Dung-O-Matic engine (http://www.arg-tech.org/index.php/projects/dung-o-matic).

• Incr-Grounded-Sem and Incr-Ideal-Sem (IncrG and IncrI for short) which incrementally compute the grounded and ideal extension E by implementing Algorithms 1 and 2, respectively.

The construction of Fig. 4 was used for computing extensions of AFs updated by a set U of updates (multiple updates) by the incremental algorithms IncrG and IncrI.

Results. Figures 6 and 7 report the run times (log scale) of BaseG and IncrG for computing the grounded extensions of the updated AFs versus the number of arguments over REAL and SYN1, respectively. The figures also report the run times of IncrG for computing the grounded extensions after performing 20 and 40 updates, where for multiple updates the restricted AF and the starting extension also take into account arguments and attacks added to the construction of Fig. 4. The experiments also showed that, on average, the size of the influenced set w.r.t. that of the input AF for REAL (resp. SYN1) is about $0.01\,\%$ (resp. $1\,\%$) for single update, $0.1\,\%$ (resp. $9\,\%$) for 20 updates, and $0.5\,\%$ (resp. $15\,\%$) for 40 updates. Figure 8 reports the run times (log scale) of BaseI and IncrI for computing the ideal extensions after performing one and five updates versus the number of arguments over SYN2. The experiments showed that the size of the influenced set w.r.t. that of the input AF for SYN2 is $6\,\%$ for single update and $43\,\%$ for 5 updates.

From these results, we can draw the following conclusions:

• The time needed by our algorithms for incrementally computing the grounded and ideal extensions is orders of magnitude better than the time needed to recompute the whole extension from scratch. This holds even in the case of multiple updates where there is an overload due to the construction of Fig. 4.

• While the improvement obtained for the grounded semantics is almost constant w.r.t. the size of the input AFs, the improvement obtained for the ideal semantics increases with the size of the input AFs. In fact, since computing the ideal semantics is exponential in the size of the input AF, the improvement derived from considering the restricted AF is exponential in the size of the restriction (arguments and attacks in the input AF not occurring in the restricted AF).

• The definition of influenced set substantially restricts the portion of the AF to be analysed for recomputing the semantics of an AF after performing an update. It is worth noting that this means that even using any non-incremental algorithm taking as input the restricted AF would result in a performance improvement, since the size of the input data to be processed would be significantly smaller.

The experiments also showed the trade-off between applying a number n of updates by using the construction of Fig. 4 (i.e., multiple updates) and performing a sequence of n single updates by running n times the incremental algorithms: the former approach is preferable for more than 20 (resp., 5) updates for REAL (resp. SYN1) under the grounded semantics, while under the ideal semantics it is preferable for less than 7 updates, on average. In fact, the overhead due to the construction of Fig. 4 is relatively small and turns to be more and more convenient for a sizeable set of updates under the grounded semantics. However, it increases with the size of the input AF and becomes relatively large for (the smaller dataset) SYN2 under the ideal semantics, making the approach based on performing sequence of single updates more suitable in this case.

7 Conclusion and Future Work

We presented two incremental algorithms for computing deterministic extensions of updated AFs. The algorithms exploit the initial extension of an AF for computing the set of arguments influenced by an update, and for detecting early termination conditions during the recomputation of the status of the arguments. Although our presentation focused on adding/removing one attack, our technique can be used in the case of general updates. The experiments, conducted considering also multiple updates, showed that the incremental computation outperforms that of the base (non-incremental) computation. The experiments also showed that our definition of influenced set drastically restricts the portion of the AF to be analysed for recomputing the semantics after an update.

Our current research is concentrated on the application of the techniques developed in this paper to other (multiple status) semantics. In this regard, there are two interesting aspects that deserve more investigation. First, the identification of restricted AFs for these semantics would enable the use of existing (non-incremental) algorithms taking as input a smaller AF for computing extensions. Second, we envisage the definition of incremental algorithms that make use of initial extensions for computing extensions after updates for multiple status semantics where we need to deal with the additional issue that extensions can be split/merged after an update.