A meta-argumentation approach for the efficient computation of stable and preferred extensions in dynamic bipolar argumentation frameworks

Abstract

Bipolar argumentation frameworks (BAFs) extend Dung’s argumentation frameworks to explicitly represent the notion of support between arguments, in addition to that of attack. BAFs can be profitably used to model disputes between two or more agents, with the aim of deciding the sets of arguments that should be accepted to support a point of view in a discussion. However, since new arguments, attacks, and supports are often introduced to take into account new available knowledge, BAFs as well as the set of accepted arguments (under a given semantics) change over the time.

In this paper we first tackle the problem of efficiently recomputing sets of accepted arguments of dynamic BAFs (under the preferred and stable semantics). Focusing on a deductive interpretation of the support relation, we introduce an incremental approach that, given an initial BAF, an initial extension for it, and an update, computes an extension of the updated BAF. This is achieved by introducing a meta-argumentation transformation according to which an initial BAF, as well as its extension and an update, are transformed into a plain argumentation framework (AF) with a suitable initial extension and update. Thanks to the use of the meta-argumentation intermediate level, our approach is able to incorporate existing AF-solvers and an incremental technique for plain AFs in order to compute an extension of the updated BAF. Moreover, our approach can be seamlessly applied to a more general form of BAFs, namely Extended Bipolar Argumentation Frameworks (EAFs), where defeasible supports and defeats are modelled by means of second-order attacks (i.e., attacks toward elements of the support or attack relation).

We experimentally validated our approach on both BAFs and EAFs. The experiments showed that, on average, our technique is almost 100 times faster than computing extensions of updated BAFs or EAFs from scratch.

1 Introduction

Argumentation has emerged as one of the central fields in Artificial Intelligence [12 , 55]. In particular, Dung’s abstract argumentation framework [33] is a simple, yet powerful formalism for modelling disputes between two or more agents. The formal meaning of an argumentation framework is given in terms of argumentation semantics, which intuitively tell us the sets of arguments (called extensions) that should be accepted to support a point of view in a discussion.

Bipolar argumentation frameworks (BAFs) are an interesting extension of the Dung’s frameworks, which allow two kinds of interactions between arguments to be modeled: the attack relation (as in Dung’s argumentation frameworks) and the support relation. Several interpretations of the notion of support have been proposed in the literature [9 , 60] (see [32] for a comprehensive survey). In this paper, we focus on deductive support [21, 60] which is intended to capture the following intuition: if argument a supports argument b then the acceptance of a implies the acceptance of b, and thus the non-acceptance of b implies the non-acceptance of a.

Although most research in argumentation focused on static frameworks (i.e., frameworks not changing over the time), argumentation frameworks (e.g. BAFs) are often used to model dynamic systems [14 , 48]. In fact, usually a BAF represents a temporary situation, and new arguments, attacks, and supports can be added/retracted to take into account new available knowledge. For instance, for disputes among users of online social networks [7, 47], arguments, attacks, and supports 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).

However, the definition of evaluation algorithms for dynamic BAFs 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. Recently, focusing on Dung’s AFs, in [3] we have proposed a technique for incrementally computing extensions for dynamic AFs. That is, given an AF, an initial extension for it, and an update, we devised an efficient technique for computing an extension of the updated AF. In this paper, we show that the technique proposed in [3] can be profitably used to compute extensions of dynamic BAFs. Thus, here we address the following problem: given a BAF $B_{0}$ , an initial extension E₀ for it, and an update u, determine an extension E of the updated BAF $u (B_{0})$ , which is obtained from $B_{0}$ by applying update u. In particular, we make the following contributions:

We identify early-termination conditions for checking whether a given extension for an initial BAF is still an extension for the updated BAF. When these conditions hold, we do not need to recompute an extension of the updated BAF.

We build on the meta-argumentation approach proposed in [21] to define a reduction of the problem of determining an extension of an updated BAF to that of determining an extension of a corresponding updated Dung’s argumentation framework.

We define an incremental algorithm for computing extensions of dynamic BAFs by leveraging on the incremental technique proposed in [3].

We show that our approach for BAFs, and in particular each of the steps 1)–3), can be seamlessly extended to deal with Extended Bipolar Argumentation Frameworks [21] (EAFs) which allow us to model defeasible support as well as attacks toward the attack relation [13, 51].

We performed an experimental analysis showing that our incremental approach for BAFs, as well as for EAFs, outperforms by two orders of magnitude the computation from scratch, where the fastest solvers from the last edition of the International Competition on Computational Models of Argumentation (ICCMA) 1 taking as input the Dung’s argumentation frameworks resulting from the transformation at step 2) are used.

Plan of the paper. After reviewing basic concepts of Bipolar Argumentation Frameworks (BAFs) in Section 2, we discuss updates in Section 3. Then, we gradually introduce our approach by first addressing the case of BAFs (Section 4) and then extending the approach to Extended Bipolar Argumentation Frameworks (EAFs) in Section 5. Specifically, after formalizing the basic steps of our approach for BAFs in Section 4, we introduce early-termination conditions (Section 4.1) as well as the meta-argumentation framework (Section 4.2) enabling algorithm Incr-BAF given in Section 4.3. Then, we move to EAFs in Section 5 where, following the scheme given in Section 4, we discuss additional early-termination conditions (Section 5.1) and a revised meta-argumentation framework (Section 5.2) needed to formalize the incremental computation for EAFs—algorithm Incr-EAF is discussed in Section 5.3. The technique proposed is experimentally evaluated in Section 6. Finally, we discuss related work in Section 7, and draw conclusions and outline directions for future work in Section 8.

This paper extends [2] in the following respects. We revise and improve the incremental computation technique for BAFs proposed in [2] by introducing the notion of compact meta-AF (Section 4.2)—this yields a significant improvement in efficiency over the original approach as we discuss in Section 7. Moreover, we generalize the (revised) approach proposed for BAFs to deal with EAFs, and perform a thorough experimental analysis for both BAFs and EAFs using solvers and benchmarks from the last edition of the ICCMA argumentation competition.

2 Bipolar argumentation framework

We assume the existence of a set Arg of arguments. An abstract bipolar argumentation framework (BAF for short) [9] is a triple 〈A, Σ, Π〉, where (i) A ⊆ Arg is a (finite) set whose elements are referred to as arguments, (ii) Σ ⊆ A × A is a binary relation over A whose elements are called attacks, (iii) Π ⊆ A × A is a binary relation over A whose elements are called supports, and (iv) Σ∩ Π = ∅. Thus, a Dung’s argumentation framework (AF) [33] is a BAF of the form 〈A, Σ, ∅ 〉.

An argument is an abstract entity whose role is entirely determined by its relationships with other arguments. A BAF can be viewed as a directed graph where each node corresponds to an argument and each edge in the graph corresponds to either an attacks or a support. Given a BAF $B$ , the bipolar interaction graph for $B$ (denoted as $G_{B}$ ) has two kinds of edges: one for the attack relation (→) and another one for the support relation (⇒), as shown in the following example.

Example 1 (Running example). Consider a BAF $B_{0} = 〈 A_{0}, Σ_{0}, Π_{0} 〉$ where:

A₀ = {a, b, c, d, e, f} is the set of arguments;

Σ₀ = {(a, c) , (c, b) , (b, d) , (d, e) , (e, d) , (e, e) , (e, f)} is the set of attacks;

Π₀ = {(a, b)} is the set of supports;

The bipolar interaction graph

G_{B_{0}}

is shown in Fig. 1.

□

Fig. 1

BAFs $B_{0}$ of Example 1.

Several interpretations of the notion of support have been proposed in the literature [32]. In this paper, we focus on deductive support [21] which is intended to capture the following intuition: if argument a supports argument b then the acceptance of a implies the acceptance of b, and thus the non-acceptance of b implies the non-acceptance of a. Given this interpretation of support, the coexistence of the support and attack relations in BAFs entails that new kinds of “implicit” attacks should be considered, as explained in what follows.

Given a BAF 〈A, Σ, Π〉, a supported attack for an argument b ∈ A by argument a₁ ∈ A is a sequence a₁Πa₂Π … Πa_nΣ b with n ≥ 1. Note that a direct attack a₁Σ b is a supported attack. Thus a supported attack is a (possibly empty) chain of supports followed by an attack. Moreover, we say that there is a mediated attack for argument a₁ by argument b if there is an attack bΣa_n and a sequence of supports a₁Πa₂Π … Πa_n with n ≥ 1. Thus, for a mediated attack the chain of supports ends in a_n which is attacked by b. Supported and mediated attacks are illustrated in Fig. 2, where a chain consisting of only one support is considered. It is easy to see that the BAF of Example 1 contains a supported attack from argument a to d, and a mediated attack from argument c to a. 2

Fig. 2

Supported and mediated attacks.

2.1 Extensions

Given a BAF 〈A, Σ, Π 〉, we say that a set S ⊆ Aset-attacks an argument b ∈ A iff there exists a supported or mediated attack for b by an argument a ∈ S. We use S⁺ to denote the set of arguments set-attacked by S. Moreover, we say that a set S ⊆ Adefends an argument a ∈ A iff for each b ∈ A such that {b} set-attacks a, it is the case that S set-attacks b (i.e., b ∈ S⁺).

Given a BAF 〈A, Σ, Π 〉, a set S ⊆ A is conflict-free iff there are no arguments a, b ∈ S such that {a} set-attacks b. Moreover, a conflict-free set S ⊆ A is said to be admissible iff it defends all of its arguments.

Example 2. Continuing with our example, for the BAF $B_{0}$ of Example 1, it is easy to see that {a} defends argument b (as {a} set-attacks c and {c} set-attacks b). The set {a, b} is conflict-free as neither {a} set-attacks b nor {b} set-attacks a, while {a, d} is not conflict-free as {a} set-attacks d (by means of the supported attack (a, d)). Moreover, S = {c, d, f} is an admissible set as it is conflict-free and S defends all of its arguments: {c} defends itself from a by the mediated attack from c to a; d is defended by {c}, and f is defended by {d}. The set of admissible sets for $B_{0}$ is {{∅} , {a} , {c} , {a, b} , {c, d} , {c, d, f}}. □

Given a BAF 〈A, Σ, Π 〉, a preferred extension (pr) for it is an admissible set which is a maximal (w.r.t ⊆). Furthermore, a conflict-free set S ⊆ A is a stable extension (st), if and only if it set-attacks all the arguments in A \ S. (Note that this implies that S is admissible).

Given a BAF $B$ and a semantics $S \in {$ pr, st}, we use $E_{S} (B)$ to denote the set of extensions for $B$ according to $S$ . For the BAF $B_{0}$ of Example 1, we have that the set of the stable extensions is $E_{st} (B_{0}) = {{c, d, f}}$ , while the set of the preferred extensions is $E_{pr} (B_{0}) = {{a, b}, {c, d, f}}$ . □

2.2 Labelling and status of arguments

Following the approach of [12], where argumentation semantics have been characterized in terms of labelling, we define a labelling function for BAFs. A labelling for a BAF $B = 〈 A, Σ, Π 〉$ is a total function L : A → {IN, OUT, UNDEC} 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) = UNDEC 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) = UNDEC}. In the following, we also use the triple 〈in (L) , out (L) , un (L) 〉 to represent the labelling L.

Given a BAF $B = 〈 A, Σ, Π 〉$ , a labelling L for $B$ 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 a ∈ {b} ⁺ and L (b) = IN; and (ii) L (a) = IN iff L (b) = OUT for all b ∈ A such that a ∈ {b} ⁺. Moreover, L is a complete labelling iff conditions (i) and (ii) hold for all a ∈ A.

Between preferred/stable 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, considering the BAF $B_{0}$ of Example 1, the labelling corresponding to the preferred extension E = {a, b} is L = 〈 {a, b} , {c, d} , {e, f} 〉.

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

2.3 Meta-argumentation framework

The semantics of BAFs can be also given in terms of meta-argumentation frameworks (i.e., Dung’s AFs) where additional (meta-)arguments and attacks are considered to model deductive support. The following construction, introduced in [21], will be used as the basis for defining the meta-argumentation framework of our incremental approach.

Definition 1. (Meta-AF [21] Given a BAF $B = 〈 A, Σ,$ Π〉, the meta-AF for $B$ is $M = 〈 A^{m}, Σ^{m} 〉$ where:

A^m = A ∪ {X_a,b, Y_a,b ∣ (a, b) ∈ Σ} ∪ {Z_a,b ∣ (a, b) ∈ Π}

Σ^m = {(a, X_a,b) , (X_a,b, Y_a,b) , (Y_a,b, b) ∣ (a, b) ∈ Σ} ∪ {(b, Z_a,b) , (Z_a,b, a) ∣ (a, b) ∈ Π}

The meaning of meta-arguments X_a,b, Y_a,b and Z_a,b is as follows. X_a,b represents the fact that the corresponding attack (a, b) is “not active” in $B$ —it belongs to an extension for $M$ iff a does not belong to an extension for $B$ . On the other hand, Y_a,b represents the fact that (a, b) is “active” in $B$ , and it belongs to an extension for $M$ iff argument b does not. Finally, meta-argument Z_a,b represents a support relation between a and b: it does not belong to an extension for $M$ iff the supported argument b is accepted in the deductive model of support. As an example, the (interaction graph of the) meta-AF $M_{0}$ for the BAF $B_{0}$ of Example 1 is shown in Fig. 3.

Fig. 3

Meta-AF $M_{0}$ for the BAF $B_{0}$ of Fig. 1.

The following proposition characterizes the relationship between the extensions of a given BAF and the extensions of the corresponding meta-AF.

Proposition 1. Let $B = 〈 A, Σ, Π 〉$ be a BAF, $M$ the meta-AF for $B_{0}$ , and $S \in {pr, st}$ a semantics. For each extension $E \in E_{S} (B)$ , there is an extension $E^{m} \in E_{S} (M)$ such that E = E^m ∩ A, and vice versa.

Example 3. For the meta-AF $M_{0}$ of the BAF $B_{0}$ in Example 1, a preferred extension is the following: {a, b, Y_a,c, X_c,b, Y_b,d, X_d,e}. The corresponding preferred extension for the BAF $B_{0}$ is {a, b, Y_a,c, X_c,b, Y_b,d, X_d,e} ∩ {a, b, c, d, e, f} = {a, b}.

A stable extension for $M_{0}$ is the following: {c, d, f, X_a,c, Y_c,b, X_b,d, Y_d,e, X_e,d, X_e,e, X_e,f, Z_a,b}, which corresponds to the extension {c, d, f} for $B_{0}$ . □

3 Updates for BAFs

An updateu for a BAF $B_{0}$ allows us to change $B_{0}$ into a BAF $B$ by adding or removing an argument, an attack, or a support. The addition (resp., deletion) of an argument a will be denoted as +a (resp. -a), whereas the addition (resp., deletion) of an attack from a to b will be denoted as +(a → b) (resp., -(a → b)). Moreover, the addition (resp., deletion) of a support from a to b will be denoted as +(a ⇒ b) (resp., -(a ⇒ b)).

We will use $u (B_{0})$ to denote the BAF resulting from the application of update u to the initial BAF $B_{0}$ . For instance, for the BAF $B_{0} = 〈 A_{0}, Σ_{0}, Π_{0} 〉$ of our running example, if u = +(f ⇒ b), we have that $u (B_{0}) = + (f \Rightarrow b) (B_{0}) = 〈 A_{0}, Σ_{0}, Π_{0} \cup {(f, b)} 〉$ ; on the other hand, if u = -(b → d), we have that $u (B_{0}) = 〈 A_{0}, Σ_{0} \ {(b, d)}, Π_{0} 〉$ .

Applying an update u to a BAF implies that its semantics (set of extensions or labellings) may change. Continuing with our running example, for the BAF $B_{0}$ of Example 1 and the update u = +(f ⇒ b), we have that the set of the stable extensions for the updated BAF $B = + (f \Rightarrow b) (B_{0})$ is $E_{st} (B) = {{c, d}}$ , while the set of the preferred extensions is $E_{pr} (B) = {{a, b}, {c, d}}$ . In fact, the addition of the support between f and b entails that additional implicit attacks must be considered: a supported attack between f and d, and a mediated one between c and f.

In the following, for the sake of the presentation, we consider only feasible updates which are defined as follows. Adding an argument as well as removing an attack/support are feasible updates. The deletion of an argument is feasible only if a is isolated, that is there is no argument b attacking/supporting a or being attacked/supported by a, where a is not necessarily distinct from b. The addition of an attack (resp., support) between a and b is feasible only if a and b are arguments of the initial BAF $B_{0}$ and there is no already a support (resp. attack) between a and b in $B_{0}$ .

Clearly, general updates can be simulated by a sequence of feasible updates. For instance, an isolated argument a can be deleted after deleting all attacks and supports involving a (by performing a sequence of feasible updates). Analogously, adding an attack (resp., a support) between an argument a in $B_{0}$ and a fresh argument $b \notin B_{0}$ can be simulated as a sequence of updates of the form +b, +(a → b) (resp., +b, +(a ⇒ b)).

Finally, observe that if a BAF $B$ is obtained from $B_{0}$ through the addition (resp. deletion) of a set S of isolated argument, then, let E₀ be an extension for $B_{0}$ , it is the case that E = E₀ ∪ S (resp. E = E₀ \ S) is an extension for $B$ that can be easily computed. Thus, in the following we do not discuss further updates of the form +a or -a. That is, we will focus on updates of the forms ± (c → d) and ± (e ⇒ f), where ± means either + or -.

4 Computing extensions of updated BAFs

In this section, given a BAF $B_{0}$ , a preferred/stable extension E₀ for $B_{0}$ , and an update u, we address the problem of recomputing a preferred/stable extension E of the updated BAF $u (B_{0})$ .

We start by presenting a baseline approach and then introduce our incremental technique.

Baseline approach. A first approach to compute an extension of an updated BAF is that of computing it from scratch, without using the information provided by the update and the initial status of arguments. Specifically, a baseline approach to compute an extension E for an updated BAF $B$ consists of the following steps:

build the meta-AF $M$ for $B$ of Definition 1;

compute an extension E^m for $M$ by using one of the available solvers for AFs [58, 59]; and

obtain an extension E for $B_{0}$ by using the result of Proposition 1.

This procedure can be made more efficient by using the following compact meta-AF, which is obtained from that of Definition 1 by avoiding to introduce meta-arguments X_a,b and Y_a,b. However, these arguments will turn out to be useful for dealing with second-order attacks in Section 5.

Definition 2 (Compact Meta-AF). Given a BAF $B = 〈 A, Σ, Π 〉$ , the compact meta-AF for $B$ is $M = 〈 A^{m}, Σ^{m} 〉$ where:

A^m = A ∪ {Z_a,b ∣ (a, b) ∈ Π}

Σ^m = Σ ∪ {(b, Z_a,b) , (Z_a,b, a) ∣ (a, b) ∈ Π}

The following proposition straightforwardly follows from Proposition 1.

Proposition 2. Let $B = 〈 A, Σ, Π 〉$ be a BAF, $M$ the compact meta-AF for $B_{0}$ , and § ∈ {pr, st} a semantics. For each $E \in E_{§} (B)$ , there is an extension $E^{m} \in E_{§} (M)$ such that E = E^m ∩ A, and vice versa.

Example 4. Continuing with our running example, the compact meta-AF for the BAF of Example 1 is reported in Fig. 4. {a, b} is the preferred extension for the compact meta-AF, as well as for the BAF, corresponding to the preferred extension given in Example 3. The stable extension for the compact meta-AF is {c, d, f, Z_a,b}, which corresponds to the stable extension {c, d, f} of Example 3. □

Fig. 4

Compact Meta-AF for the BAF of Example 1.

Incremental approach. The baseline approach does not make use of the initial extension E₀ for $B_{0}$ and of the update u to be performed. On the contrary, our incremental approach relies on profitably using this kind of information to improve efficiency and avoid wasted effort during the computation.

Our approach to recompute a preferred/stable extension E of an updated BAF $u (B_{0})$ consists of the following three main steps.

Step 1: Checking for irrelevant updates. We identify conditions ensuring that a given extension E₀ for the initial BAF $B_{0}$ (under the preferred or stable semantic) is still an extension for the updated BAF $u (B_{0})$ . In such case, the update u does not invalidate the initial extension E₀, and it will be immediately returned by our algorithm.

Step 2: Build a suitable (compact) meta-AF. Given a triple $〈 B_{0}, E_{0}, u 〉$ consisting of an initial BAF, an extension, and an update, we transform it into a triple $〈 M_{0}, E_{0}^{m}, u^{m} 〉$ consisting of a (compact) meta-AF $M_{0}$ , an extension $E_{0}^{m}$ , and an update u^m for $M_{0}$ . Our transformation is based on the meta-argumentation approach proposed in [21] (cfr. Definitions 1 and 2), though in our case we need to take into account the initial extension E₀ and the update u.

Step 3: Incremental computation on the meta-AF. Given the AF $M_{0}$ , its extension $E_{0}^{m}$ , and the update u^m for $M_{0}$ , we use the incremental technique proposed in [3] for computing an extension E^m of the updated AF $u^{m} (M_{0})$ w.r.t. $E_{0}^{m}$ . The technique identifies a reduced AF sufficient to compute an extension of the whole AF and use state-of-the-art algorithms to recompute an extension of the reduced AF only. Then from extension E^m of the updated AF $u^{m} (M_{0})$ , we derive an extension E of an updated BAF $u (B_{0})$ .

In the next sections we describe in detail these three steps.

4.1 Checking for irrelevant updates

Given a BAF $B_{0}$ , an initial extension E₀ whose corresponding labelling is L₀, and an update u, for each pair of initial statuses L₀ (a) and L₀ (b) of the arguments involved in the update, Tables 1–4 tell us if E₀ is still an extension after performing the update (under the preferred or stable semantics).

Table 1
Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a → b)

update L₀ (b)

+(a → b) IN UNDEC OUT

L₀ (a) IN pr, st

UNDEC pr

OUT pr,st pr,st

update	L₀ (b)
L₀ (a)	IN		pr, st
	UNDEC		pr
	OUT	pr,st	pr,st

Table 2

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a ⇒ b)

update		L₀ (b)
+(a ⇒ b)		IN	UNDEC	OUT
L₀ (a)	IN	pr,st
	UNDEC
	OUT	pr,st	pr	pr,st

Table 3

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = -(a → b)

update		L₀ (b)
-(a → b)		IN	UNDEC	OUT
L₀ (a)	IN	NA	NA
	UNDEC	NA		pr
	OUT	pr,st	pr	pr,st

Table 4

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = -(a ⇒ b)

update		L₀ (b)
-(a ⇒ b)		IN	UNDEC	OUT
L₀ (a)	IN	pr,st	NA	NA
	UNDEC	pr		NA
	OUT	pr,st	pr

Proposition 3 (Extension preservation). Let $B_{0}$ be a BAF, $S \in {pr, st}$ a semantics, $E_{0} \in E_{S} (B_{0})$ an extension of $B_{0}$ under semantics $S$ , L₀ the labelling corresponding to E₀, and u an update. If $S$ is in the cell 〈L₀ (a) , L₀ (b) 〉 of

Table 1 and u = +(a → b);

Table 2 and u = +(a ⇒ b);

Table 3 and u = -(a → b);

Table 4 and u = -(a ⇒ b);

then $E_{0} \in E_{S} (u (B_{0}))$ , where u is the update specified above.

Thus, if some of the conditions of Proposition 3 hold, then the given initial extension of the initial BAF is still an extension of the updated one, and thus Step 2) and Step 3) of the incremental approach can be skipped — the algorithm just returns the initial extension which is also an extension for the updated BAF. For instance, considering the BAF $B_{0}$ of Example 1, the update u = -(b → d), and preferred extension E₀ = {c, d, f}, since L₀ (b) = OUT and L₀ (d) = IN, Table 3 says that E₀ = {c, d, f} is still an extension of the BAF $u (B_{0})$ . Similarly, considering u = +(c ⇒ f), and again the preferred extension E₀ = {c, d, f}, since L₀ (c) = L₀ (f) = IN, Table 2 tell us that E₀ is still an extension of the updated BAF.

Conditions similar to those of Proposition 3 were identified in [3] for updates for Dung’s AFs, that is, AFs where the support relation is not considered. However, those conditions could be used only at Step 3) when applying the technique of [3] to the meta-AF $M_{0}$ , that is, after performing the transformation of Step 2). Therefore, to avoid to uselessly perform Step 2) and to immediately discover irrelevant updates, we provided Proposition 3 that extends the results of [3] to updates for BAFs and allows us to directly check at Step 1) for cases for which initial extensions for BAFs are preserved.

The results of Proposition 3 follow from their counterparts for updates of Dung’s AFs given in [3]. In fact, since using Step 2—whose details are given in Section 4.2—an update u for BAF $B_{0}$ with initial extension E₀ corresponds to an update u^m for a meta-AF $M_{0}$ with extension $E_{0}^{m}$ , the results of Proposition 3 can be easily obtained by checking whether u^m is irrelevant for $M_{0}$ with respect to $E_{0}^{m}$ .

4.2 The meta-argumentation framework for incremental computation

Given the initial BAF $B_{0}$ and an updated u for it, we define the corresponding meta-argumentation framework as follows.

Definition 3 ((Compact) Meta-AF for Updates). Let $B = 〈 A, Σ, Π 〉$ be a BAF, and u an update for $B$ of the form u = ± (c → d) or u = ± (e ⇒ f). Then, the meta-AF for $B$ w.r.t. u is $C M (B, u) = 〈 A^{m}, Σ^{m} 〉$ where:

A^m = A ∪ {Z_a,b ∣ (a, b) ∈ Π} ∪ {Z_e,f ∣ u = +(e ⇒ f)}

Σ^m = Σ ∪ {(b, Z_a,b) , (Z_a,b, a) ∣ (a, b) ∈ Π} ∪ {(f, Z_e,f) ∣ u = +(e ⇒ f)}

For instance, the meta-AF $C M (B_{0}, + (f \Rightarrow b))$ for the BAF $B_{0}$ of Example 1 w.r.t the update u = +(f ⇒ b) is shown in Fig. 5 where attack (b, Z_f,b) is added. It is worth noting that the meta-AF for negative updates (e.g., $C M (B_{0}, - (a \to c))$ ) coincides with the compact meta-AF of Fig. 4.

Fig. 5

$C M (B_{0}, + (f \Rightarrow b))$ : compact meta-AF for the BAF $B_{0}$ of Fig. 1 w.r.t. update u = +(f ⇒ b).

Our definition of meta-argumentation framework builds on (the compact version of) that proposed in [21] and considers additional meta-arguments (e.g., Z_f,b in Fig. 5) and attacks (e.g., (b, Z_f,b) in Fig. 5) that will allow us to simulate addition updates to be performed on BAF $B_{0}$ by means of updates performed on the corresponding the meta-AF $C M (B_{0}, u)$ , as follows.

Definition 4 (Updates for the (Compact) Meta-AF). Let $B = 〈 A, Σ, Π 〉$ be a BAF, and u an update for $B$ of the form u = ± (c → d) or u = ± (e ⇒ f). The corresponding update u^m for $C M (B, u)$ is as follows: $u^{m} = {\begin{matrix} + (Z_{e, f} \to e) if u = + (e \Rightarrow f) \\ - (Z_{e, f} \to e) if u = - (e \Rightarrow f)) \\ + (c \to d) if u = + (c \to d) \\ - (c \to d)) if u = - (c \to d)) \end{matrix}$

Basically, support updates for the given bipolar framework are translated in attacks updates on the corresponding meta-AF of Definition 2, while attacks updates can be directly performed on the meta-AF. For instance, given the BAF $B_{0}$ of Example 1 and u = +(f ⇒ b), the update for $C M (B_{0}, + (f \Rightarrow b))$ is u^m = +(Z_f,b, f) (see Fig. 5), while update u = -(a → c) for $B_{0}$ simply corresponds to the update u^m = -(a → c) for $C M (B_{0}, - (a \to c))$ .

The last ingredient we need before being ready to apply the incremental technique of [3] is the initial extension $E_{0}^{m}$ for $C M (B_{0}, u)$ . We obtain it from that of initial BAF $B_{0}$ by propagating the labels of the arguments in $B_{0}$ as follows.

Definition 5 (Initial Labelling for the Meta-AF). Given a BAF $B_{0} = 〈 A, Σ, Π 〉$ and its initial labelling L₀, the corresponding initial labelling $L_{0}^{m}$ for the meta-AF $C M (B_{0}, u) = 〈 A^{m}, Σ^{m} 〉$ is as follows:

$\forall a \in A \cap A^{m} : L_{0}^{m} (a) = L_{0} (a)$ ;

∀Z_a,b ∈ A^m: $L_{0}^{m} (Z_{a, b}) = INif L_{0} (b) = OUT$ , $L_{0}^{m} (Z_{a, b}) = OUT if L_{0} (b) = IN$ , $L_{0}^{m} (Z_{a, b}) = UNDEC if L_{0} (b) = UNDEC$ .

For instance, with reference to Fig. 5, and the preferred extension E₀ = {c, d, f} for the BAF $B_{0}$ of Example 1, we have that the labelling corresponding to E₀ is L₀ = 〈 {c, d, f} , {a, b, e} , ∅ 〉, and thus $L_{0}^{m} (Z_{f, b}) = IN$ since $L_{0}^{m} (b) = L_{0} (b) = OUT$ . Similarly, $L_{0}^{m} (Z_{a, b}) = IN$ since $L_{0}^{m} (b) = OUT$ . In turn, we have that, $E_{0}^{m} = {c, d, Z_{a, b}, Z_{f, b}, f}$ .

The following proposition characterizes the relationship between extensions of updated BAFs and extensions of updated meta-AFs.

Proposition 4. Let $B_{0} = 〈 A, Σ, Π 〉$ be a BAF, $S \in {pr, st}$ a semantics, and $E_{0} \in E_{S} (B_{0})$ an extension of $B_{0}$ under $S$ . Let $M_{0} = C M (B_{0}, u)$ be meta-AF for $B_{0}$ w.r.t. u, $E_{0}^{m}$ the initial $S$ -extension for $M_{0}$ corresponding to E₀, and u^m the update for $M_{0}$ corresponding to u. Then, there is $E \in E_{S} (u (B_{0}))$ iff there is $E^{m} \in E_{S} (u^{m} (M_{0}))$ such that E = E^m ∩ A.

Algorithm 1 Incr-BAF( $B_{0}, u, E_{0}, S$ , ${Solver}_{S}$ )

Input: BAF

B_{0} = 〈 A_{0}, Σ_{0} Π_{0} 〉

update u of the form u = ± (a ⇒ b) or u = ± (a → b),

an initial

S

-extension E₀ for

B_{0}

semantics

S \in {pr, st}

function Solver_§(

A

) returning an

S

-extension

for AF

A

if it exists, ⊥ otherwise;

Output: An

S

-extension E for

u (B_{0})

if it exists, ⊥ otherwise;

1: if

checkProp (B_{0}, u, E_{0}, S)

then

2: return E₀;

3: Let

M_{0} = C M (B_{0}, u)

: be the meta-AF for

B_{0}

w.r.t. u (cf. Definition 3);

4: Let u^m be the update for

M_{0}

corresponding to u (cf. Definition 4);

5: Let

E_{0}^{m}

be the initial

S

-extension for

M_{0}

corresponding to E₀ (cf. Definition 5);

6: Let E^m = Incr-Alg(

M_{0}, u^{m}, S, E_{0}^{m}

{Solver}_{S}

);

7: if (E^m≠ ⊥) then

8: returnE = (E^m ∩ A₀);

9: else

10: return ⊥;

4.3 Incremental algorithm

Given a BAF $B_{0}$ , a semantics $S \in {$ pr, st}, an extension $E_{0} \in E_{S} (B_{0})$ , and an update u of the form u = ± (a ⇒ b) or u = ± (a → b), we define an incremental algorithm (Algorithm 1) for computing an extension E of the updated BAF $u (B_{0})$ , if it exists. 3

Algorithm 1 works as follows. It first checks if the initial extension E₀ is still an extension of the updated BAF at Line 1, where $checkProp (B_{0}, u, E_{0}, S)$ is a function returning true iff some of the conditions of Proposition 3 hold. If this is the case, it immediately returns the initial extension. Otherwise, it computes the (meta) AF $M_{0}$ (Line 3), the update u^m for $M_{0}$ (Line 4), and the initial $S$ -extension $E_{0}^{m}$ for $M_{0}$ (Line 5). Next, it invokes function Incr-Alg which encodes the incremental algorithm proposed in [3] for Dung’s AFs. Incr-Alg takes as input the parameters $M_{0}, u^{m}, S, E_{0}^{m}$ , and ${Solver}_{S}$ , where ${Solver}_{S}$ is an external solver that can compute an $S$ -extension for the input AF—we describe function Incr-Alg in more detail below. Finally, the extension of the updated BAF (if any) is obtained by projecting out the extension E^m returned by Incr-Alg over the set of arguments A₀ of the initial BAF (Line 8).

Function Incr-Alg. It efficiently computes an extension of an updated Dung’s AF by identifying a suitable sub-graph of the updated AF, computing an extension on this part only, and finally merging it with an initial extension to get an extension of the updated AF. More in detail, it consists of the following three steps [3]:

First, a sub-AF, called reduced AF, is identified on the basis of the set of arguments influenced by an update [44 –46] and additional information provided by the initial extension. In our running example, given the meta-AF $M_{0}$ of Fig. 5, the update u^m = +(Z_f,b, f), and the extension $E_{0}^{m} = {c, d, Z_{a, b}, Z_{f, b}, f}$ corresponding to the preferred extension E₀ = {c, d, f}, the influenced set consists of argument f only. The reduced AF is built by adding to the subgraph induced by the influenced set, additional arguments and attacks containing needed information on the “external context”, i.e. information about the status of arguments which are attacking some argument in the influenced set. Continuing with our example, the reduced AF consists of the two arguments Z_f,b and f and the attack (Z_f,b, f) between them.

Second, a non-incremental algorithm (e.g., Arg- SemSAT [30] for $S = pr$ , go DIAMOND [57] for $S = st$ ) is used to compute an extension of the reduced AF — this is done by calling ${Solver}_{S}$ . In our example the external solver returns the preferred extension E^r = {Z_f,b} for the reduced AF.

Finally, the final extension E_m of the whole (meta) AF is obtained by merging a portion of its initial extension with that computed for the reduced AF (i.e., E^r = {Z_f,b} in our example) by the external solver ${Solver}_{S}$ . The result of the merging operation in our example will be E_m = {c, d, Z_a,b, Z_f,b}.

Continuing with the example above, after calling Incr-Alg, the extension of the updated BAF is obtained at Line 8 of Algorithm 1 as E = {c, d} = E^m ∩ A₀.

In the next section, we introduce a variant of Algorithm 1 taking as input an extended BAF where second-order attacks are considered.

5 Dealing with second order attacks

In this section, we show how to extend our technique to consider second-order attacks [21] for BAFs, that is, (i) attacks from an argument to another attack, and (ii) attacks from an argument to a support. This allows the representation of both attacks towards the attack relation [13, 51] and a kind of defeasible support where the support itself can be attacked. 4

In the following, after presenting the formal definition of BAFs extended with second-order attacks, as well as the formalization of updates for the extended framework, analogously to what done in Section 4.2 we first identify (additional) early termination conditions for checking whether a second-order update is irrelevant. Then, we build on the definition of meta-AF introduced in [21] for encoding second-order attacks, extend it to deal with updates for such kind of BAFs, and finally discuss how to modify Algorithm 1 to enable the computation of extensions of extended BAFs.

An Extended Bipolar Argumentation Framework (EAF for short) [21] is a quadruple 〈A, Σ, Π, Δ〉, where 〈A, Σ, Π〉 is a BAF and Δ is a binary relation over A × (Σ ∪ Π) whose elements are called second-order attacks.

In the following, a second-order attack from an argument a to an attack (b, c) will be denoted as (a↠(b → c)), while an attack from an argument a to a support (b, c) will be denoted as (a↠(b ⇒ c)).

Example 5. $E B_{0} = 〈 A_{0}, Σ_{0}, Π_{0}, Δ_{0} 〉$ is an EAF where Δ₀ = {(a, (b, d))} is the set of second-order attacks. Its graph is shown in Fig. 6, where second-order attacks are drawn using double-headed arrows. □

Fig. 6

EAF $E B_{0}$ of Example 5.

The semantics of an EAF can be given by means of the following meta-AF, which extends that in Definition 1 by taking into account second order attacks [21].

Definition 6 (Meta-AF with Second-Order Attacks). The meta-AF for $E B = 〈 A, Σ, Π, Δ 〉$ is $M = 〈 A^{m}, Σ^{m} 〉$ where: A^m = A ∪ {X_a,b, Y_a,b ∣ (a, b) ∈ Σ} ∪ {Z_a,b ∣ (a, b) ∈ Π} ∪ {X_a,(b,c), Y_a,(b,c) ∣ (a, (b, c)) ∈ Δ, (b, c) ∈ Σ}

Σ^m = {(a, X_a,b) , (X_a,b, Y_a,b) , (Y_a,b, b) ∣ (a, b) ∈ Σ} ∪ {(b, Z_a,b) , (Z_a,b, a) ∣ (a, b) ∈ Π} ∪ {(a, X_a,(b,c)) , (X_a,(b,c), Y_a,(b,c)) , (Y_a,(b,c), Y_b,c) ∣ (a, (b, c)) ∈ Δ, (b, c) ∈ Σ} ∪ {(a, X_a,(b,c)) , (X_a,(b,c), Y_a,(b,c)) , (Y_a,(b,c), Z_b,c) ∣ (a, (b, c)) ∈ Δ, (b, c) ∈ Π}

Thus, an attack of the form (a↠(b → c)) is encoded as an attack towards the meta-argument Y_b,c (that represents the fact that (b, c) is “active”), while an attack of the form (a↠(b ⇒ c)) is encoded as an attack toward the meta-argument Z_b,c. The meta-AF for the EAF of Example 5 is shown in Fig. 7.

Fig. 7

Meta-AF for the EAF of Example 5.

Analogously to what stated in Proposition 1, extensions for an EAF $E B$ are obtained from extensions for its meta-AF: E is an $S$ -extension for $E B$ iff $E^{m} \in E_{S} (M)$ and E = E^m ∩ A. Using this relationship, the notion of labelling can be extended to EAFs as well.

Example 6. For the meta-AF $M$ of Fig. 7, we have the following preferred extension: {a, b, d, f, Y_a,c, X_c,b, Y_d,e, Y_a,(b,d), X_e,e, X_e,d, X_e,f, }, which corresponds to the extension {a, b, d, f} of the EAF of Example 5.

A stable extension for the meta-AF is {c, d, f, X_a,c, Y_c,b, Z_a,b, X_b,d, Y_d,eX_e,e, X_e,d, X_e,f, X_a,(b,d)}. It corresponds to the extension {c, d, f} for the EAF. □

5.1 Second-order updates and early-termination conditions

In addition to the kinds of updates introduced in Section 3, for EAFs we also consider additions and deletions of second-order attacks. Specifically, the addition (resp., deletion) of a second-order attack from an argument a to an attack (b, c) will be denoted as +(a↠(b → c)) (resp., -(a↠(b → c))). Similarly, if (b, c) is a support, then the update will be denoted as +(a↠(b ⇒ c)) (resp., -(a↠(b ⇒ c))).

We use $u (E B_{0})$ to denote the EAF resulting from the application of update u to an initial EAF $E B_{0}$ . For instance, given the EAF $E B_{0}$ of Example 5 and the update u = -(a↠(b → d)), we have that $u (E B_{0})$ is the EAF of Example 1.

The following proposition identifies cases for which a given initial extension of an EAF is preserved after performing an update. It is worth noting that conditions a)–d) identified in Proposition 3 for BAFs still hold for EAFs. The other conditions e)–h) are added to deal with irrelevant second-order updates.

Proposition 5. Let $E B_{0}$ be an EAF, $S \in {pr, st}$ a semantics, $E_{0} \in E_{S} (E B_{0})$ an extension of $E B_{0}$ under semantics $S$ , L₀ the labelling corresponding to E₀, and u an update. If $S$ is in the cell 〈L₀ (a) , L₀ (b) 〉 of

Table 1 and u = +(a → b);

Table 2 and u = +(a ⇒ b);

Table 3 and u = -(a → b);

Table 4 and u = -(a ⇒ b);

Table 5 and u = +(a↠(b → c));

Table 6 and u = +(a↠(b ⇒ c));

Table 7 and u = -(a↠(b → c));

Table 8 and u = -(a↠(b ⇒ c));

then $E_{0} \in E_{S} (u (E B_{0}))$ , where u is the update specified above.

Table 5
Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a↠(b → c))

update L₀ (b)

+(a↠(b → c)) IN UNDEC OUT

L₀ (a) IN pr, st

UNDEC pr

OUT pr,st pr,st

update	L₀ (b)
L₀ (a)	IN		pr, st
	UNDEC		pr
	OUT	pr,st	pr,st

Table 6

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a↠(b ⇒ c))

update		L₀ (c)
+(a↠(b ⇒ c))		IN	UNDEC	OUT
L₀ (a)	IN	pr,st
	UNDEC	pr
	OUT	pr,st		pr,st

Table 7

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = -(a↠(b → c))

update		L₀ (b)
-(a↠(b → c))		IN	UNDEC	OUT
L₀ (a)	IN	NA	NA
	UNDEC	NA		pr
	OUT	pr,st	pr	pr,st

Table 8

Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = -(a↠(b ⇒ c))

update		L₀ (c)
-(a↠(b ⇒ c))		IN	UNDEC	OUT
L₀ (a)	IN		NA	NA
	UNDEC			NA
	OUT	pr,st	pr	pr,st

As done in Algorithm 1 for BAFs, the conditions of Proposition 5 can be used to recognize that an initial extension for an EAF $E B_{0}$ is still valid for the updated EAF $u (E B_{0})$ .

5.2 Enabling the incremental computation with second-order attacks and updates

To deal with second-order updates we need to extend the meta-AF of Definition 3, as well as the notions of update and initial labelling for the meta-AF of Definitions 4 and 5, respectively.

We start by introducing the (compact) meta-AF for dealing with updates in EAFs—it will be used in our variant of Algorithm 1 at Line 3, in place of the meta-AF of Definition 3.

Definition 7 (Meta-AF for Second-Order Updates). Let $E B = 〈 A, Σ, Π, Δ 〉$ be an EAF, and u an update of one of the following forms:

u = ± (e → f)

u = ± (e ⇒ f)

u = ± (e↠(g → h))

u = ± (e↠(g ⇒ h)).

Then, the (compact) meta-AF for

E B

w.r.t. u is

C M (E B, u) = 〈 A^{m}, Σ^{m} 〉

where: A^m = A ∪ {Z_a,b ∣ (a, b) ∈ Π} ∪ {X_c,d, Y_c,d ∣ (e, (c, d)) ∈ Δ, (c, d) ∈ Σ} {Z_e,f ∣ u = +(e ⇒ f)} ∪ {X_g,h, Y_g,h ∣ u = +(e↠(g → h))} Σ^m = Σ∖ {(g, h) ∣ u = +(e↠(g → h))} ∪ {(g, X_g,h) , (X_g,h, Y_g,h) , (Y_g,h, h) ∣ u = +(e↠(g → h))} ∪ {(b, Z_a,b) , (Z_a,b, a) ∣ (a, b) ∈ Π} ∪ {(e, Z_a,b) ∣ (e, (a, b)) ∈ Δ, (a, b) ∈ Π} ∪ {(c, X_c,d) , (X_c,d, Y_c,d) , (Y_c,d, d) , (e, Y_c,d) ∣ (e, (c, d)) ∈ Δ, (c, d) ∈ Σ} ∪ {(f, Z_e,f) ∣ u = +(e ⇒ f)} .

Besides the meta-arguments Z_a,b of Definition 3, and the attacks involving those arguments, the above meta-AF contains meta-arguments X_c,d, Y_c,d for encoding second order attacks in Δ toward attacks (c, d) ∈ Σ. In fact, an attack e↠(a ⇒ b) in Δ toward a support is encoded as an attack from e toward Z_a,b in the meta-AF, while e↠(c → d) in Δ is encoded as an attack from e toward Y_c,d in the meta-AF (which contains also the attacks (c, X_c,d) , (X_c,d, Y_c,d) , (Y_c,d, d)). Moreover, meta-arguments Z_e,f and X_g,h, Y_g,h, are added to the meta-AF for encoding, respectively, the addition of a second order attack toward a support (e, f) ∈ Π or toward an attack (g, h) ∈ Σ. In the latter case, meta-arguments X_g,h and Y_g,h along with the set of attacks {(g, X_g,h) , (X_g,h, Y_g,h) , (Y_g,h, h)} are used to simulate the attack g → h which is attacked by e in the EAF. This enables the definition of simple attacks updates (cf. Definition 8) to simulate second-order attacks updates.

Example 7. The meta-AF for the EAF $E B_{0}$ of Fig. 6 w.r.t. the update u = +(d↠(c → b)) is shown in Fig. 8. Herein, the attacks involving the meta-arguments X_b,d and Y_b,d allow us to simulate the second order attack a↠(b → d). Moreover, the attacks involving the meta-arguments X_c,b and Y_c,b are added to enable the simulation of the second-order update u by a single attack update on the meta-AF. □

Fig. 8

Compact Meta-AF for the EAF $E B_{0}$ of Fig. 6 w.r.t. the update u = +(d↠(c → b)).

The following definition extends Definitions 4 to the case of EAFs and second order updates.

Definition 8 (Updates for the Meta-AF). Let $E B = 〈 A, Σ, Π, Δ 〉$ be an EAF, and u an update for $E B$ . Update u^m for the meta-AF $C M (E B, u) = 〈 A^{m}, Σ^{m} 〉$ is as follows: $u^{m} = {\begin{matrix} + (Z_{e, f} \to e) if u = + (e \Rightarrow f) \\ - (Z_{e, f} \to e) if u = - (e \Rightarrow f)) \\ + (c \to d) if u = + (c \to d) \\ - (c \to d)) if u = - (c \to d)) \\ + (e \to Y_{g, h}) if u = + (e ↠ (g \to h)) \\ - (e \to Y_{g, h}) if u = - (e ↠ (g \to h)) \\ + (e \to Z_{a, b}) if u = + (e ↠ (a \Rightarrow b)) \\ - (e \to Z_{a, b}) if u = - (e ↠ (a \Rightarrow b)) \end{matrix}$

For instance, continuing with Example 7, given the EAF $E B_{0}$ of Fig. 6 and the update u = +(d↠(c → b)), we have that update u^m for the meta-AF $C M (E B_{0}, u)$ shown in Fig. 8 is u^m = +(d → Y_c,b).

Finally, given an initial extension for an EAF and an update, we define the initial labelling for the corresponding meta-AF as follows.

Definition 9 (Initial Labelling for the Meta-AF). Given an EAF $E B_{0} = 〈 A, Σ, Π, Δ 〉$ and a initial labelling L₀, the corresponding initial labelling $L_{0}^{m}$ for the meta-AF $C M (E B_{0}, u) = 〈 A^{m}, Σ^{m} 〉$ is as follows:

$\forall a \in A \cap A^{m} : L_{0}^{m} (a) = L_{0} (a)$ ;

∀ X_a,b ∈ A^m:

$L_{0}^{m} (X_{a, b}) = IN if L_{0} (a) = OUT$

$L_{0}^{m} (X_{a, b}) = OUT if L_{0} (a) = IN$

$L_{0}^{m} (X_{a, b}) = UNDEC if L_{0} (a) = UNDEC$

∀ Y_a,b ∈ A^m:

$L_{0}^{m} (Y_{a, b}) = IN if (i) L_{0}^{m} (X_{a, b}) = OUT and$ (ii) ∀ c ∈ As . t . (c, (a, b)) ∈ Δ, L₀ (c) = OUT

$L_{0}^{m} (Y_{a, b}) = OUT if (i) L_{0}^{m} (X_{a, b}) = IN or$ (ii) ∃ c ∈ A ∣ (c, (a, b)) ∈ Δ and L₀ (c) = IN

$L_{0}^{m} (Y_{a, b}) = UNDEC, otherwise$ .

∀ Z_a,b ∈ A^m:

$L_{0}^{m} (Z_{a, b}) = IN if (i) L_{0} (b) = OUT and$ (ii) ∀ c ∈ As . t . (c, (a, b)) ∈ Δ, L₀ (c) = OUT

$L_{0}^{m} (Z_{a, b}) = OUT if (i) L_{0} (b) = IN or$ (ii) ∃ c ∈ A ∣ (c, (a, b)) ∈ Δ and L₀ (c) = IN

$L_{0}^{m} (Z_{a, b}) = UNDEC, otherwise$ .

For instance, given the initial preferred extension E₀ = {a, b, d, f} for the EAF $E B_{0}$ of Example 5, the initial labelling for the meta-AF $C M (E B_{0}, + (d \to Y_{c, b}))$ of Fig. 8 is such that $L_{0}^{m} (a) = L_{0} (a) = IN$ , $L_{0}^{m} (c) = L_{0} (c) = OUT$ , $L_{0}^{m} (X_{c, b}) = IN$ , and $L_{0}^{m} (Y_{c, b}) = OUT$ . Also, we have that $L_{0}^{m} (b) = L_{0} (b) = IN$ , $L_{0}^{m} (X_{b, d}) = OUT$ , $L_{0}^{m} (Y_{b, d}) = OUT$ since $L_{0}^{m} (a) = L_{0} (a) = IN$ , and $L_{0}^{m} (d) = L_{0} (d) = IN$ .

5.3 Incr-EAF: incremental algorithm for EAFs

We are now ready to define the incremental algorithm for EAFs that we call Incr-EAF. In fact, we just need to slightly modify Algorithm 1 as follows.

Incr-EAF takes as input an EAF $E B_{0}$ , a semantics $S \in {$ pr, st}, an extension $E_{0} \in E_{S} (E B_{0})$ , and an update u of the form u = ± (a ⇒ b), u = ± (a → b), u = ± (e↠(c ⇒ d)), or u = ± (e↠(c → d)). To incrementally compute an extension E of the updated EAF $u (E B_{0})$ , it suffices to

use Proposition 5 instead of Proposition 3 at Line 1 of Algorithm 1 where function checkProp is called.

compute the (meta) AF $M_{0}$ , the update u^m for $M_{0}$ , and the initial $S$ -extension $E_{0}^{m}$ for $M_{0}$ using the new Definitions 7, 8, and 9 for EAFs, respectively, at Lines 3, 4, and 5.

It is worth noting that if the input EAF of Incr-EAF is a BAF, and the update does not concern second-order attacks, then Incr-EAF coincides with Incr-BAF given in Algorithm 1. In fact, in this case, Proposition 5 collapses to Proposition 3 as no second order updates are considered, and the meta-AF of Definition 7, as well as update u^m of Definition 8 and the initial labelling of Definition 9, coincide with their counterparts for BAFs introduced in Definitions 3, 4, and 5, respectively.

6 Empirical evaluation

We implemented a C++ prototype and, for each semantics $S \in {$ pr, st}, we compared the performance of our incremental algorithm with that of the best ICCMA’17 solver for the computational task $S$ -SE, that is the task of determining some $S$ -extension. More in detail, given an EAF $E B_{0}$ , a semantics $S \in {$ pr, st}, an extension $E_{0} \in E_{S} (E B_{0})$ , and an update u for the EAF, we compared the following two strategies for computing an extension $E \in E_{S} (u (E B_{0}))$ of the updated EAF:

Incremental computation, that is, algorithm Incr-EAF with input $E B_{0}, u, E_{0}, S$ , and ${Solver}_{S}$ ;

Computation from scratch, where an extension E of the updated EAF $u (E B_{0})$ is computed by running ${Solver}_{S}$ over the updated (compact) meta-AF.

where

{Solver}_{S}

is ArgSemSAT [30] for

S = pr

and goDIAMOND [57] for

S = st

—these solvers are the winners of the ICCMA’17 competition for the computational task

S

-SE.

Dataset. We generated a set of BAFs and a set of EAFs by starting from AFs used as benchmarks at ICCMA’17 [1] for the tracks SE-pr and SE-st. Specifically, we used the datasets named B1 and B2, both consisting of 50 AFs whose size is as follows:

B1 consists of AFs with a number of arguments |A| ∈ [2, 50K] and a number of attacks |Σ| ∈ [1, 1.6M].

B2 consists of AFs with |A| ∈ [35, 200K] and |Σ| ∈ [73, 4M].

Given the AFs in these datasets, we generated BAFs and EAFs by transforming attacks into supports and then adding second-order attacks as follows.

Given a percentage p of supports, and a percentage s ≤ p of second order attacks (i.e., attacks to attacks and attacks to supports), for each AF $A = 〈 A, Σ 〉$ in the ICCMA dataset, we generated EAFs $E B_{0} = 〈 A, Σ^{'}, Π, Δ 〉$ (or BAFs $B_{0} = 〈 A, Σ^{'}, Π 〉$ if Δ =∅) as follows. First, we selected p × |Σ| attacks in Σ in a random way, and converted them into supports. That is, let Σ^r ⊆ Σ be the set of the chosen p × |Σ| attacks in Σ, for each (a, b) ∈ Σ^r, we added a support randomly chosen in {(a, b) , (b, a)} to Π, and then set Σ′ = Σ ∖ Σ^r. Next, we selected s × |Σ| supports in Π and s × |Σ| attacks in Σ′ in a random way, and for each support/attack (x, y) selected, we added in Δ a second-order attack from a randomly selected argument in A to (x, y). As an example, if |Σ|=100 and p = 20% and s = 10%, then we have that |Σ′|=80 and |Π|=20, |Δ|=20 as there will be 10 second-order attacks toward a support in Π plus 10 second-order attacks toward attack in Σ′.

In the following, we use B1(p,s) and B2(p,s) to refer to the datasets consisting of EAFs obtained by starting from AFs in B1 and B2, respectively, and having a percentage percentage p of supports and a percentage s of second order attacks.

Methodology. For each semantics $S \in {$ pr, st} and EAF $E B_{0} = 〈 A_{0}, Σ_{0}, Π_{0}, Δ_{0} 〉$ (BAF when Δ₀ =∅) in the dataset, we considered every $S$ -extension E₀ of $E B_{0}$ as an initial extension. Then, we randomly selected an update u of the following form (only updates of the types 1)–4) were considered for BAFs):

+(a → b), with a, b ∈ A₀ and (a, b) ∉ Σ₀;

+(a ⇒ b), with a, b ∈ A₀ and (a, b) ∉ Π₀;

-(a → b), with (a, b) ∈ Σ₀;

-(a ⇒ b), with (a, b) ∈ Π₀;

+(a↠(b → c)), with a ∈ A₀, (b, c) ∈ Σ₀, and (a, (b, c)) ∉ Δ₀;

+(a↠(b ⇒ c)), with a ∈ A₀, (b, c) ∈ Π₀, and (a, (b, c)) ∉ Δ₀;

-(a↠(b → c)), with (a, (b, c)) ∈ Δ₀;

-(a↠(b ⇒ c)), with (a, (b, c)) ∈ Δ₀.

Next, we computed an $S$ -extension E for the updated EAF $u (E B_{0})$ by calling our incremental algorithm Incr-EAF. Finally, the average run time of Incr-EAF to compute an $S$ -extension was compared with the average run time of ArgSemSAT if $S = pr$ , or goDIAMOND if $S = st$ , to compute an $S$ -extension for $u^{m} (C M (E B_{0}, u))$ from scratch.

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

Results. Figures 9 and 10 report the average run times (log scale) of the incremental computation (Incr-EAF) and the computation from scratch over the datasets B1(p,s) and B2(p,s), respectively, for the preferred semantics (left-hand side) and the stable semantics (right-hand side) and percentages p ∈ {10 % , 20 %} of supports and s ∈ {0 % , 10 %} of second-order attacks. Each data point reported in the figures is an average run time over 20 runs. For the sake of readability, in the figures we also showed the lines obtained by LOESS local regression.

Fig. 9

Run times (ms) of ICCMA’17 solvers and Incr-EAF over dataset B1(p,s) versus the number of arguments in the input EAF, for the preferred semantics (left-hand side) and stable semantics (right-hand side). The percentage p ∈ {10 % , 20 %} of supports and the percentage s ∈ {0 % , 10 %} of second-order attacks are shown at the bottom of each graph.

Fig. 10

Run times (ms) of ICCMA’17 solvers and Incr-EAF over dataset B2(p,s) versus the number of arguments in the input EAF, for the preferred semantics (left-hand side) and stable semantics (right-hand side). The percentage p ∈ {10 % , 20 %} of supports and the percentage s ∈ {0 % , 10 %} of second-order attacks are shown at the bottom of each graph.

From these results, we can draw the following conclusions:

The incremental algorithm outperforms the competitors that compute extensions from scratch. In fact, on average, our technique is two orders of magnitude faster then the computation from scratch. In particular, the time saved by the incremental computation is higher for the dataset B2(p,s), where the computation from scratch takes much more time due to the complexer structures of the AFs in B2 which are reflected into the generated EAFs. Also, the improvements obtained for the stable semantics are larger than that obtained for the preferred one—this is due to the different external solvers used.

The improvements obtained for BAFs slightly decrease when increasing the percentage p of supports (see Figures 9-10 (a-b) and (c-d)). This is due to the fact that the size of the reduced-AF identified by Incr-Alg [3] (see Section 4.3), as well as that of the meta-AF, increases when the number of supports increases. The same behaviour happens when the percentage s of second-order attacks in EAFs increases (see Figures 9-10 (c-d) and (e-f)). However, worsening in the performance is not dramatic—the incremental technique remains much faster than the computation from scratch in all cases.

Beside the impact of the number of arguments in the EAFs on the performance, we have investigated how the number of relationships between arguments (i.e., attacks and supports) impact on the running times. We found that our algorithm behaves similar to the case that the number of arguments was varied: the shape of the charts (not reported for the sake of brevity) is similar, modulo a constant factor which depends on the average in/out degree of the nodes (i.e., arguments) in the considered dataset. In brief, the average improvement achieved w.r.t the computation from scratch was confirmed also by this analysis.

7 Related work

A comprehensive introduction to (static) abstract argumentation frameworks (AFs) can be found in [12], while [32] provides a survey of bipolar argumentation frameworks (BAFs). Although the idea underlying AFs is simple and intuitive, most of the semantics proposed so far suffer from a high computational complexity [34–37 , 39–42]. Complexity bounds and evaluation algorithms for AFs have been deeply studied in the literature, but most of this research focused on static frameworks, whereas, in practice, AFs (as well as BAFs) are not static systems [14 , 48].

There have been significant efforts coping with dynamics aspects of Dung’s abstract argumentation frameworks, as discussed in what follows. [22, 23] have investigated the principles according to which a grounded extension of a Dung’s abstract argumentation frameworks does not change when the set of arguments/attacks are changed. [24, 25] have addressed the problem of revising the set of extensions of an argumentation framework, and studied how the extensions can evolve when a new argument is considered. They focus on adding one argument interacting with one initial argument (i.e. an argument which is not attacked by any other argument). [20] 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 [10], where it is studied how the acceptability of arguments evolves when a new argument is added to the decision system. The division-based method, proposed by [48] and then refined by [14], divides the updated framework into two parts: affected and unaffected, where only the status of affected arguments is recomputed after updates.

Leveraging on the results introduced in [48, 50] investigated the efficient evaluation of the justification status of a subset of arguments in an AF (instead of the whole set of arguments), and proposed an approach based on answer-set programming for local computation. In [49], an AF is decomposed into a set of strongly connected components, yielding sub-AFs located in layers, which are then used for incrementally computing the semantics of the given AF by proceeding layer by layer. Recently, [61] introduced a matrix representation of argumentation frameworks and proposed a matrix reduction that, when applied to dynamic argumentation frameworks, resembles the division-based method in [48].

Other relevant works on dynamic aspects of Dung’s argumentation frameworks include the following. [15] 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. [18] have investigated whether and how it is possible to modify a given AF so that a desired set of arguments becomes an extension, whereas [54] have studied equivalence between two AFs when further information (another AF) is added to both AFs. [16] have focused on expansions where new arguments and attacks may be added but the attacks among the old arguments remain unchanged, while [17] have characterized update and deletion equivalence, where adding/deleting arguments/attacks is allowed (deletions were not considered by [16, 54]).

Bipolarity in argumentation is discussed in [9], where a survey of the use of bipolarity is given, as well as a formal definition of BAF that extends the Dung’s concept of argumentation framework by including supports is provided. In [8], a bipolar scale is used for distinguishing arguments in favour or against a decision in the context of multiple criteria decision making. Differently from BAFs where arguments support/attack other arguments, in [8] arguments are instead intended to be in favour or against goals (i.e., decisions). As discussed in [32], different interpretations of the concept of support have been proposed. The acceptability of arguments in the presence of the support relation was first investigated in [26]. Then, to handle bipolarity in argumentation, [27, 28] proposed an approach based on using the concept of coalition of arguments, where arguments are grouped together, and defeats occur between coalitions. However, when considering a deductive interpretation of support [21, 60], as we did in this paper, coalitions may lead to counterintuitive results [32], though they are useful in contexts where support is interpreted differently. Changes in bipolar argumentation frameworks have been studied in [29], where it is shown how the addition of one argument together with one support involving it (and without any attack) impacts the extensions of the updated BAF.

The problem of efficiently and incrementally computing extensions of dynamic BAFs has been first addressed in [2]. Here we extended that paper from two standpoints. First, we provided a more efficient approach for BAFs by leveraging on the notion of compact meta-AF introduced in Section 4.2, where only needed meta-arguments/attacks are included in the meta-argumentation level (the meta-AF used in [2] has the form of that presented in Section 4.2 where meta-arguments of the type X_a,b and Y_a,b, as well as the chains of attacks between them, are included). We experimentally found that, on average, using the compact version of the meta-AF yields an improvement of about 305% over using the original approach proposed in [2]. Second, we generalized the approach proposed for BAFs to the case of EAFs, which allow us to deal with attacks towards the attack relation [4 , 51] and defeasible support [21], and experimentally evaluated the overall approach using up-to-date solvers and benchmarks from the ICCMA’17 argumentation competition.

8 Conclusion and future work

We introduced a technique for the incremental computation of extensions of dynamic EAFs, i.e., BAFs (possibly) incorporating second-order attacks. Following the meta-argumentation approach [32], according to which EAFs are translated into semantically equivalent AFs, we introduced a translation where updates and initial extensions of EAFs are taken into account. Then, we exploited the incremental algorithm recently proposed in [3] and computed extensions of the meta-AFs, from which the updated extensions of EAFs are obtained. Our experiments showed that the incremental technique outperforms the computation from scratch by two orders of magnitude, on average.

Although in this paper we focused on updates consisting of adding/removing one attack/support, our technique can be extended to deal with sets of updates performed simultaneously. Indeed, the construction described in [45] for reducing the application of a set of updates to the application of a single attack update can be easily extended to deal with multiple updates for EAFs. The implementation of such kind of updates for EAFs is left for future work.

We also plan to extend our technique to deal with other interpretations of support, particularly the approach in [27, 28] where meta-AFs are also adopted to cope with bipolarity in argumentation.

Finally, we envisage the use of our incremental approach in the context of structured argumentation [11 , 56]. A first step in this direction has been taken in [5, 6] where the analysis of the part of DeLP-programs [43]—from which structured arguments are derived—that changes after an update is performed by exploiting the notion of reachability for (hyper-)graphs representing the programs.

Footnotes

1

2

Another kind of implicit attack which we do not consider in this paper because of the deductive interpretation of support is the secondary attack [28], which occurs when in a BAF there is a sequence bΣa₁Πa₂Π … Πa_n with n ≥ 1. Considering supported and secondary attacks leads to an alternative interpretation of support [28]. However, when considering a deductive interpretation of support, secondary attacks may lead to counterintuitive results [], though they are useful in contexts where support is interpreted differently.

3

Observe that for the stable semantics, the set of extensions $E_{st} (u (B_{0}))$ of the updated BAF may be empty; in this case, the algorithm returns ⊥.

4

The technique can be further extended to consider (second-order) attacks from an attack to another attack [].

References

http://argumentationcompetition.org/2017/results.html, 2017.

Alfano

, Greco

and Parisi

, Computing stable and preferred extensions of dynamic bipolar argumentation frameworks, In Proc of Workshop on Advances In Argumentation In Artificial Intelligence co-located with XVI International Conference of the Italian Association for Artificial Intelligence (AI*IA), 2017, pp. 28–42.

Alfano

, Greco

and Parisi

, Efficient computation of extensions for dynamic abstract argumentation frameworks: An incremental approach, In Proc of International Joint Conference on Artificial Intelligence (IJCAI), 2017, pp. 49–55.

Alfano

, Greco

and Parisi

, Computing extensions of dynamic abstract argumentation frameworks with second-order attacks, In Proc of International Database Engineering & Applications Symposium (IDEAS), 2018, pp. 183–192.

Alfano

, Greco

, Parisi

, Simari

G.I.

and Simari

G.R.

, An incremental approach to structured argumentation over dynamic knowledge bases, In Proc of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2018.

Alfano

, Greco

, Parisi

, Simari

G.I.

and Simari

G.R.

, Incremental computation of warranted arguments in dynamic defeasible argumentation: The rule addition case, In Proc of the Symposium on Applied Computing (SAC), 2018, pp. 911–917.

Alsinet

, Argelich

, Béjar

, Fernández

, Mateu

and Planes

, An argumentative approach for discovering relevant opinions in twitter with probabilistic valued relationships, Pattern Recognition Letters105 (2018), 191–199.

Amgoud

, Bonnefon

J.-F.

and Prade

, An argumentation-based approach to multiple criteria decision, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU), 2005, pp. 269–280.

Amgoud

, Cayrol

and Lagasquie-Schiex

M.-C.

, On the bipolarity in argumentation frameworks, In Proc of International Workshop on Non-Monotonic Reasoning (NMR), 2004, pp. 1–9.

10.

Amgoud

and Vesic

, Revising option status in argument-based decision systems, Journal of Logic and Computation22(5) (2012), 1019–1058.

11.

Atkinson

, Baroni

, Giacomin

, Hunter

, Prakken

, Reed

, Simari

G.R.

, Thimm

and Villata

, Towards artificial argumentation, AI Magazine38(3) (2017), 25–36.

12.

Baroni

, Caminada

and Giacomin

, An introduction to argumentation semantics, The Knowledge Engineering Review26(4) (2011), 365–410.

13.

Baroni

, Cerutti

, Giacomin

and Guida

, Encompassing attacks to attacks in abstract argumentation frameworks, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2009, pp. 83–94.

14.

Baroni

, Giacomin

and Liao

, On topology-related properties of abstract argumentation semantics. A correction and extension to dynamics of argumentation systems: A division-based method, Artificial Intelligence212 (2014), 104–115.

15.

Baumann

, Splitting an argumentation framework, In Proc of International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR), 2011, pp. 40–53.

16.

Baumann

, Normal and strong expansion equivalence for argumentation frameworks, Artificial Intelligence193 (2012), 18–44.

17.

Baumann

, Context-free and context-sensitive kernels: Update and deletion equivalence in abstract argumentation, In Proc of European Conference on Artificial Intelligence (ECAI), 2014, pp. 63–68.

18.

Baumann

and Brewka

, Expanding argumentation frameworks: Enforcing and monotonicity results, In Proc of Third International Conference on Computational Models of Argument (COMMA), 2010, pp. 75–86.

19.

Bench-Capon

T.J.M.

and Dunne

P.E.

, Argumentation in artificial intelligence, Artificial Intelligence171(10-15) (2007), 619–641.

20.

Bisquert

, Cayrol

, de Saint-Cyr

F.D.

and Lagasquie-Schiex

M.-C.

, Characterizing change in abstract argumentation systems, In Trends in Belief Revision and Argumentation Dynamics, volume 48, 2013, pp. 75–102.

21.

Boella

, Gabbay

D.M.

, van der Torre

L.W.N.

and Villata

, Support in abstract argumentation, In Proc of Third International Conference on Computational Models of Argument (COMMA), 2010, pp. 111–122.

22.

Boella

, Kaci

and van der Torre

L.W.N.

, Dynamics in argumentation with single extensions: Abstraction principles and the grounded extension, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU), 2009, pp. 107–118.

23.

Boella

, Kaci

and van der Torre

L.W.N.

, Dynamics in argumentation with single extensions: Attack refinement and the grounded extension, In Proc of Sixth International Workshop on Argumentation in Multi-Agent Systems (ArgMAS), 2009, pp. 150–159.

24.

Cayrol

, de Saint-Cyr

F.D.

and Lagasquie-Schiex

M.-C.

, Revision of an argumentation system, In Proc of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2008, pp. 124–134.

25.

Cayrol

, de Saint-Cyr

F.D.

and Lagasquie-Schiex

M.-C.

, Change in abstract argumentation frameworks: Adding an argument, Journal of Artificial Intelligence Research38 (2010), 49–84.

26.

Cayrol

and Lagasquie-Schiex

M.-C.

, On the acceptability of arguments in bipolar argumentation frameworks, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU), 2005, pp. 378–389.

27.

Cayrol

and Lagasquie-Schiex

M.-C.

, Bipolar abstract argumentation systems, In Argumentation in Artificial Intelligence, 2009, pp. 65–84.

28.

Cayrol

and Lagasquie-Schiex

M.-C.

, Coalitions of arguments: A tool for handling bipolar argumentation frameworks, International Journal of Intelligent System25(1) (2010), 83–109.

29.

Cayrol

and Lagasquie-Schiex

M.-C.

, Change in abstract bipolar argumentation systems, In Proc of International Conference on Scalable Uncertainty Management (SUM), 2015, pp. 314–329.

30.

Cerutti

, Vallati

, Giacomin

and Zanetti

, Argsemsat-2017.

31.

Charwat

, Dvorák

, Gaggl

S.A.

, Wallner

J.P.

and Woltran

, Methods for solving reasoning problems in abstract argumentation - A survey, Artificial Intelligence220 (2015), 28–63.

32.

Cohen

, Gottifredi

, García

A.J.

and Simari

G.R.

, A survey of different approaches to support in argumentation systems, The Knowledge Engineering Review29(5) (2014), 513–550.

33.

Dung

P.M.

, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence77(2) (1995), 321–358.

34.

Dunne

P.E.

, The computational complexity of ideal semantics, Artificial Intelligence173(18) (2009), 1559–1591.

35.

Dunne

P.E.

and Wooldridge

, Complexity of abstract argumentation, In Argumentation in Artificial Intelligence, 2009, pp. 85–104.

36.

Dvorák

, Pichler

and Woltran

, Towards fixed-parameter tractable algorithms for argumentation, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU), 2010.

37.

Dvorák

and Woltran

, Complexity of semistable and stage semantics in argumentation frameworks, Information Processing Letters110(11) (2010), 425–430.

38.

Falappa

M.A.

, Garcia

A.J.

, Kern-Isberner

and Simari

G.R.

, On the evolving relation between belief revision and argumentation, The Knowledge Engineering Review26(1) (2011), 35–43.

39.

Fazzinga

, Flesca

and Parisi

, Efficiently estimating the probability of extensions in abstract argumentation, In Proc of International Conference on Scalable Uncertainty Management (SUM), 2013, pp. 106–119.

40.

Fazzinga

, Flesca

and Parisi

, On the complexity of probabilistic abstract argumentation frameworks, ACM Transactions on Computational Logic16(3) (2015), 22.

41.

Fazzinga

, Flesca

and Parisi

, On efficiently estimating the probability of extensions in abstract argumentation frameworks, International Journal of Approximate Reasoning69 (2016), 106–132.

42.

Fazzinga

, Flesca

, Parisi

and Pietramala

, PARTY: A mobile system for efficiently assessing the probability of extensions in a debate, In Proc of International Conference on Database and Expert Systems Applications (DEXA), 2015, pp. 220–235.

43.

García

A.J.

and Simari

G.R.

, Defeasible logic programming: An argumentative approach, Theory and Practice of Logic Programming (TPLP)4(1-2) (2004), 95–138.

44.

Greco

and Parisi

, Efficient computation of deterministic extensions for dynamic abstract argumentation frameworks, In Proc of European Conference on Artificial Intelligence (ECAI), 2016, pp. 1668–1669.

45.

Greco

and Parisi

, Incremental computation of deterministic extensions for dynamic argumentation frameworks, In Proc of European Conference On Logics In Artificial Intelligence (JELIA), 2016, pp. 288–304.

46.

Greco

and Parisi

, Incremental computation of grounded semantics for dynamic abstract argumentation frameworks, In Proc of 2nd Workshop on Conflict Resolution in Decision Making (COREDEMA), 2016, pp. 66–81.

47.

Kökciyan

, Yaglikci

and Yolum

, Argumentation for resolving privacy disputes in online social networks: (extended abstract), In Proc of International Conference on Autonomous Agents and Multiagent Sytems (AAMAS), 2016, pp. 1361–1362.

48.

Liao

B.S.

, Jin

and Koons

R.C.

, Dynamics of argumentation systems: A division-based method, Artificial Intelligence175(11) (2011), 1790–1814.

49.

Liao

, Toward incremental computation of argumentation semantics: A decomposition-based approach, Ann Math Artif Intell67(3-4) (2013), 319–358.

50.

Liao

and Huang

, Partial semantics of argumentation: Basic properties and empirical results, J Log Comput23(3) (2013), 541–562.

51.

Modgil

, An abstract theory of argumentation that accommodates defeasible reasoning about preferences, In Proc of European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2007, pp. 648–659.

52.

Modgil

and Prakken

, Revisiting preferences and argumentation, In Proc of International Joint Conference on Artificial Intelligence (IJCAI), 2011, pp. 1021–1026.

53.

Modgil

, Toni

, Bex

, Bratko

, Chesñevar

C.I.

, DvUNDECorák

, Falappa

M.A.

, Fan

, Gaggl

S.A.

, García

A.J.

, González

M.P.

, Gordon

T.F.

, Leite

, MoUNDECzina

, Reed

, Simari

G.R.

, Szeider

, Torroni

and Woltran

, Agreement Technologies, volume 8 of Law, Governance and Technology, Chapter 21: The Added Value of Argumentation: Examples and Challenges, 2013, pp. 357–404. Springer.

54.

Oikarinen

and Woltran

, Characterizing strong equivalence for argumentation frameworks, Artificial Intelligence175(14-15) (2011), 1985–2009.

55.

Rahwan

, Simari

G.R.

, Argumentation in Artificial Intelligence. Springer Publishing Company, Incorporated, 1st edition, 2009.

56.

Rahwan

, Simari

G.R.

, Argumentation in Artificial Intelligence. Springer Publishing Company, Incorporated, New York, 1st edition, 2009.

57.

Strass

, Ellmauthaler

, goDIAMOND 0.6.6 – ICCMA 2017 system description, 2017. Second International Competition on Computational Models of Argumentation: http://www.dbai.tuwien.ac.at/iccma17/

58.

Thimm

and Villata

, The first international competition on computational models of argumentation: Results and analysis, Artificial Intelligence252 (2017), 267–294.

59.

Thimm

, Villata

, Cerutti

, Oren

, Strass

and Vallati

, Summary report of the first international competition on computational models of argumentation, Artificial Intelligence Magazine37(1) (2016), 102.

60.

Villata

, Boella

, Gabbay

D.M.

and van der Torre

L.W.N.

, Modelling defeasible and prioritized support in bipolar argumentation, Annals of Mathematics and Artificial Intelligence66(1-4) (2012), 163–197.

61.

and Cayrol

, The matrix approach for abstract argumentation frameworks, In Proc of International Workshop on Theory and Applications of Formal Argumentation (TAFA), 2015, pp. 243–259.

update		L₀ (b)
+(a → b)		IN	UNDEC	OUT
L₀ (a)	IN			pr, st
	UNDEC			pr
	OUT	pr,st		pr,st

update		L₀ (b)
+(a↠(b → c))		IN	UNDEC	OUT
L₀ (a)	IN			pr, st
	UNDEC			pr
	OUT	pr,st		pr,st

A meta-argumentation approach for the efficient computation of stable and preferred extensions in dynamic bipolar argumentation frameworks

Abstract

1 Introduction

2 Bipolar argumentation framework

2.2 Labelling and status of arguments

2.3 Meta-argumentation framework

4 Computing extensions of updated BAFs

Table 1 Cases for which E 0 ∈ E S ( u ( B 0 ) ) for u = +(a → b) update L0 (b) +(a → b) IN UNDEC OUT L0 (a) IN pr, st UNDEC pr OUT pr,st pr,st

5 Dealing with second order attacks

Table 5 Cases for which E 0 ∈ E S ( u ( B 0 ) ) for u = +(a↠(b → c)) update L0 (b) +(a↠(b → c)) IN UNDEC OUT L0 (a) IN pr, st UNDEC pr OUT pr,st pr,st

6 Empirical evaluation

8 Conclusion and future work

Footnotes

1

2

3

4

References

Table 1
Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a → b)

update L₀ (b)

+(a → b) IN UNDEC OUT

L₀ (a) IN pr, st

UNDEC pr

OUT pr,st pr,st

Table 5
Cases for which $E_{0} \in E_{S} (u (B_{0}))$ for u = +(a↠(b → c))

update L₀ (b)

+(a↠(b → c)) IN UNDEC OUT

L₀ (a) IN pr, st

UNDEC pr

OUT pr,st pr,st