Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks

1 Introduction

Many approaches have been recently proposed for extending Dung's Abstract Argumentation Framework (AAF) to deal with various forms of uncertainty. In this context, a lot of interest has been gained by the "incomplete Abstract Argumentation Frameworks" (iAAFs) introduced in [Baumeister et al., 2018b; Coste-Marquis et al., 2007; Cayrol et al., 2007], whose difference from the "classical" AAFs is that every argument/attack is labeled as certain or uncertain, meaning that it will definitely occur or may not occur in the modeled dispute, respectively. iAAFs are well-suited for a number of situations, such as the merging of AAFs representing the subjective views of different agents. In fact, it allows the attacks that must be definitely considered (as they are shared by all the agents) to be distinguished from those that may not be true (as agents do not agree on their existence). Analogously, arguments may need to be marked as uncertain since it is not known if the agent claiming them will participate the dispute.

An iAAF compactly encodes the possible "scenarios" for the argumentation, named completions, that are the alternative combinations of arguments/attacks that can occur. Thus, a completion is an AAF containing all the certain arguments/attacks of the iAAF plus a subset of its uncertain arguments/attacks. To deal with the multiplicity of completions, the classical notion of extension has been re-formulated into i-extension, in the possible and necessary variants:

∗Contact Author

"Possible and necessary i-extensions of an iAAF": A set of arguments S is a possible (resp., necessary) i-extension of the iAAF IF if, for some (resp., every) completion F of IF, the set S∗ consisting of the arguments in S belonging also to F is such that S∗ is an extension of F.

Example 1 Consider the iAAF IF over the arguments a, b and the attack (a, b). Assume that a is certain, while b and (a, b) are uncertain. Then, IF has 3 completions: F1 = 〈A1,D1〉 = 〈{a}, ∅〉, F2 = 〈A2,D2〉 = 〈{a, b}, ∅〉, F3 = 〈A3,D3〉 = 〈{a, b}, {(a, b)}〉. Let S = {a, b}. It is easy to see that, under the admissible semantics, S is a possible i-extension of IF. In fact, S ∩ A1 = {a} is an admissible extension in the completion F1 (as well as S ∩ A2 = {a, b} is an admissible extension in F2). S is not a necessary iextension of IF (under the admissible semantics) since S ∩ A3 = {a, b} is not an admissible extension in F3.

Now, consider the iAAF IF ′ coinciding with IF, except for the fact that (a, b) in IF ′ is certain. The completions of IF ′ are F ′1 = 〈A′1 ,D′1 〉 = 〈{a}, ∅}〉, F ′2 = 〈A′2 ,D′2 〉 = 〈{a, b}, {(a, b)}〉. Then, under the admissible semantics, S = {a, b} is a possible i-extension (as S ∩ A′1 = {a} is an extension in F ′1 ) but not a necessary i-extension (as S ∩ A′2 = {a, b} is not an extension in F ′2 ). ✷

Looking into Example 1, we can find some aspects of the definition of i-extension that raise some concerns, in particular for the possible variant. Consider the case of IF ′ . The set {a, b} turns out to be a possible i-extension even though there is no completion for which {a, b} is an admissible extension: indeed, they are conflicting (since the attack (a, b) is certain), thus one would reasonably expect that {a, b} should not be considered an admissible extension in any sense. A similar concern arises when using the notion of i-extension as a cornerstone for building other fundamental notions of iAAFs, and in particular when defining the notion of accepted argument as done in classical AAFs. In fact, starting from the traditional definition of "accepted argument", it would be natural to define an "i-accepted argument" as an argument belonging to at least one i-extension. The point is that, this way, in the case of IF ′ , the argument b would be an i-accepted argument as it belongs to the i-extension S = {a, b}: but S is an i-extension since {a} is an extension in F ′1 , where argument b does not occur. In other words, despite b is i-accepted, it belongs to no extension of any completion.

Starting from these observations, in this paper we introduce the "possible i∗ -extension", a revisitation of the notion of possible i-extension defined as follows:

"A set of arguments S is a possible i∗ -extension of an iAAF IF if S is an extension of some completion F of IF",

that basically differs from the one in the literature since the completion F that certifies that S is an i∗ -extension must contain all the arguments of S. According to this alternative definition, S = {a, b} is still a possible i∗ -extension for the iAAF IF in Example 1 (since S is an extension in F2, that contains both a and b) but not for IF ′ (the only completion of IF ′ containing both a and b is F ′2 , where a is in conflict with b). This new definition avoids the possibility that a set of arguments is considered an i∗ -extension even though its arguments never occur together in an extension of some completion. In turn, this makes the "natural" definition of i∗ -acceptable argument reasonable: now an i∗ -accepted argument (i.e., an argument belonging to at least one possible i∗ -extension) is guaranteed to belong to at least one extension of a completion.

The main contribution of this paper is a study of the verification problem for (possible) i-extensions under this revisited definition. In particular, we focus on the complexity characterization of this problem and show that, under several semantics, our revisitation also yields beneficial changes in the complexity. In fact, under the admissible, stable, complete, and grounded semantics, the verification problem, that was shown to be NP-complete in [Baumeister et al., 2018b] for the "original" i-extension, becomes polynomial-time solvable. In this regard, the proofs of the polynomiality under the complete and the grounded semantics are based on elaborate strategies based on removals/insertions of uncertain arguments and attacks that has no analogous counterpart in the literature.

A synopsis of the results on the complexity of the verification problem in [Baumeister et al., 2018b] and of our revisitation is in Table 1. Herein, also the case of necessary i∗ - extension (whose definition is the possible one's, after replacing "some" with "every") is reported. In fact, in order to give a complete picture, we reason on the effects of revisiting the original notion of necessary i-extension as done with possible i∗ -extension. From a computational point of view, this change has no impact on the complexity of the verification. From a "semantics" standpoint, we will show that the original notion of necessary i-extension does not raise the same concerns as the possible one (e.g., necessary i-extensions cannot contain conflicting arguments). However, revisiting the necessary iextension in same direction as the possible i∗ -extension can be useful to encode more strictly that the arguments in S must "collectively" represent a strong point in the dispute.

2 Preliminaries

Abstract Argumentation Frameworks (AAFs). An Abstract Argumentation Framework is a pair 〈A,D〉, where A is a finite set, whose elements are called arguments, and D ⊆ A × A is a binary relation over A, whose elements are called defeats or attacks. Given a set of arguments S and an argument a, we say that "S attacks a" if there is an argument b in S such that b attacks a, and that "a attacks S" if there is an argument b ∈ S such that a attacks b. Moreover, we say that a is acceptable w.r.t. S if every argument attacking a is attacked by S, and say that S is conflict-free if there is no attack between its arguments.

Semantics of AAFs. Several semantics for AAFs have been proposed to identify "reasonable" sets of arguments, called extensions [Dung, 1995]. A set S ⊆ A is: an admissible extension (ad) iff S is conflict-free and all its arguments are acceptable w.r.t. S; a stable extension (st) iff S is conflict-free and S defeats each argument in A \ S; a complete extension (co) iff S is admissible and S contains all the arguments that are acceptable w.r.t. S; a grounded extension (gr) iff S is a minimal (w.r.t. ⊆) complete set of arguments; a preferred extension (pr) iff S is a maximal (w.r.t. ⊆) complete set of arguments. SEM will denote the set of semantics {ad, st, co, gr, pr}.

Incomplete AAFs (iAAFs). We now recall the notion of incomplete AAF [Baumeister et al., 2018b].

Definition 1 (iAAF) An incomplete Abstract Argumentation Framework is a tuple 〈A,A? ,D,D? 〉, where A and A? are disjoint sets of arguments, and D and D? are disjoint sets of defeats between arguments in A ∪ A? . The arguments in A are said to be certain (i.e., they are definitely known to exist), while those in A? uncertain (i.e., it is not known for sure if they occur in the argumentation or not). The defeats in D are said to be certain (i.e., they are definitely known to exist, if both the incident arguments exist), while those in D? uncertain (i..e, it is not for sure whether they hold in the argumentation, even if both the incident arguments exist).

An iAAF compactly represents the alternative scenarios for the argumentation, called completions.

Definition 2 (Completion) A completion for an iAAF IF = 〈A,A? ,D, D? 〉 is an AAF F = 〈A′ ,D′ 〉 where A ⊆ A′ ⊆ (A∪A? ) and D∩(A′ ×A′ )⊆D′ ⊆ (D∪D? ) ∩ (A′ ×A′ ).

In [Baumeister et al., 2018b], i-extensions have been introduced 1 to adapt the fundamental notion of extension to the presence of incompleteness in iAAFs. Specifically, since an iAAF encodes several scenarios, the notion of extension was re-formulated under both the possible and the necessary perspective, where the discriminatory condition is required to be true in at least one and every scenario, respectively.

1 The name i-extension was never used explicitly in [Baumeister et al., 2018b], where the presentation follows the direction of extending the verification problem (rather than adapting the notion of extension) to iAAFs. However, what we call i-extensions are sets of arguments for which the verification problem introduced in [Baumeister et al., 2018b] returns "yes" and vice-versa.

Definition 3 (Possible and necessary i-extension) Given an iAAF IF and the semantics σ ∈ SEM, a set S is said to be a possible (resp., necessary) i-extension for IF (under σ) if, for at least one (resp., for every) completion F = 〈A′ ,D′ 〉 of IF, the set S∗ = S ∩A′ is an extension of F under σ.

Example 1 shows some possible and necessary i-extensions.

3 From i-Extensions to i∗ -Extensions

As a matter of fact, under the possible perspective, the definition of i-extension proposed in [Baumeister et al., 2018b] raises some issues that can be hardly reconciled with the expectation that, even in the presence of uncertainty, an extension should consist of a set of arguments that collectively represent a robust point of view in a dispute. In fact:

• I1: a set S may be an i-extension of an iAAF IF even if, for every completion F where S's arguments occur all together, S is not an extension for F. This happens, for instance, with S = {a, b} in the iAAF IF ′ in Example 1.
• I2: as an undesirable consequence of the point above, a set S may be an i-extension of IF even if some of its arguments are definitely conflicting, due to certain attacks between them (see S = {a, b} in the iAAF IF ′ in Example 1);

I3: even in a possible perspective, one would expect that the fact that an argument belongs to an i-extension (i.e., the argument is "i-acceptable") certifies that the argument is "robust to some extent". Unfortunately, an i-acceptable argument may not be robust at all: for instance, in Example 1, b is i-acceptable for IF ′ (since it belongs to the i-extension {a, b}) but it can be hardly considered robust to any extent, since it is defeated through the certain attack (a, b) from the un-attacked certain argument a. The point is that it can happen that an argument belongs to an i-extension S, but this argument does not belong to any completion F that "certifies" that S is an i-extension.

These issues can be resolved by modifying Definition 3 by requiring that the set S itself (rather than S∗ = S ∩A′ ) is an extension in the completion F, thus obtaining what follows:

Definition 4 (Possible and necessary i∗ -extension) Given an iAAF IF and a semantics σ ∈ SEM, a set S is said to be a possible (resp., necessary) i∗ -extension for IF (under σ) if, for at least one (resp., for every) completion F of IF, the set S is an extension of F under σ.

Example 2 The possible i-extensions of the iAAF IF of Figure 1 under the σ = ad are ∅, {a}, {e}, {a, e}, {a, d}, {e, d}, {a, b}, {e, b}, {a, b, d}, {e, b, d}, {a, d, e}, {a, b, e} and {a, b, d, e}, while the possible i∗ -extensions under the admissible semantics are ∅, {a}, {e}, {a, e}, {a, d}, {e, d} and {a, d, e}. For the possible i-extensions that are not possible i∗ -extensions, the issues I1 and I2 hold. Moreover, argument b raises issue I3 when considering its membership to i-extensions. The necessary i-extensions of IF under σ = ad are ∅, {a}, {e} {a, d}, {e, d}, {a, e} and {a, d, e}, while the necessary i∗ -extensions are ∅, {a} and {a, d}. Observe that, under the necessary perspective, neither the i-extensions nor the i∗ -extensions raise I1 and I2, and no argument raises I3.

As discussed at the end of Example 2, issues I1, I2, I3 for the "original" notion of i-extension under the necessary perspective do not hold. Specifically, if S is a necessary i-extension, no pair of its arguments can be conflicting (issue I2), since there would be at least a completion where these arguments occur along with the attack, and S would not be an extension in this completion. Analogously, no member of a necessary i-extension can be attacked by an un-attacked argument (issue I3). Nevertheless, using the notion of necessary i∗ -extension instead of the original i-extension is reasonable when one wants to adopt an even "more necessary" perspective, where the desiderata that the arguments in S collectively represent a robust point of view is applied by strictly interpreting the term "collectively".

The relationship between i∗ - and i- extensions. Proposition 1 below outlines the hierarchy over i- and i∗ - extensions.

Proposition 1 Given an iAAF IF = 〈A,A? ,D,D? 〉 and a semantics σ ∈ SEM, let N ∗ and N be the sets of necessary i∗ - and i- extensions under σ, respectively, and P ∗ and P the sets of possible i∗ - and i- extensions under σ, respectively. Then, N ∗ ⊆N ⊆P ∗⊆P .

The inclusion N ⊆ P ∗ holds since, if S is a necessary i-extension, it is an extension also in the completions containing all the arguments of S. According to Proposition 1, any i∗ -extension is an i-extension. The vice versa is generally false (e.g., the possible i-extension {a, b} of Example 2 is not an i∗ -extension), but it holds for i-extensions consisting of only certain arguments, since definitions 3 and 4 collapse. This is formalized in the first part of the following statement.

Proposition 2 Let IF = 〈A, A? , D, D? 〉 be an iAAF and σ ∈ SEM. 1) Under both the possible and necessary perspectives, if S is an i-extension and S∩A = S, then S is an i∗ -extension. 2) The vice versa holds only for the necessary perspective.

Point 2) above implies that necessary i∗ -extensions contain no uncertain arguments. This is false for possible i∗ - extensions and for possible and necessary i-extensions (in Example 2, {e} is a possible i∗ -extension, a possible i-extension and a necessary i-extension although e ∈ A? ).

4 Verifying Extensions: Complexity Results

We study the complexity of the following counterparts of the classical verification problem over AAFs:

Definition 5 (IPOSVERσ (S) and INECVERσ (S)) Let IF= 〈A,A? ,D,D? 〉 be an iAAF, S ⊆ A ∪ A? , σ ∈ SEM. IPOSVERσ (S) (resp., INECVERσ (S)) asks for checking if S is a possible (resp., necessary) i∗ -extension for IF under σ.

Our results are summarized in Table 1 and their importance and technical depth are discussed at the end of this section.

Theorem 1 IPOSVERσ (S) is in P under σ ∈ {ad, st}.

Proof. Under σ = ad, IPOSVERσ (S) is true iff S is an extension in the completion containing all the arguments of IF but the uncertain arguments outside S that attack S, and all the attacks except the uncertain attacks towards S (and between arguments in S). The case σ = st is analogous. ✷

The case of the complete semantics is much more complex. We preliminarily introduce the notion of core argument and of c-expansion of a core argument.

Definition 6 Let IF = 〈A,A? ,D,D? 〉 be an iAAF, F = 〈A∗ ,D∗ 〉 one of its completions, S ⊆ A∗ and a0 ∈ A∗ /S. Argument a0 is a core argument w.r.t. IF, F and S iff there is a sequence of arguments a0, . . . , an (with n ≥ 0) such that:

1. {a0, . . . , an} ⊆ A∗ /S;
2. ∀i∈[0..n], ̸ ∃b ∈ S s.t. (b, ai)∈D∗∩D or (ai, b)∈D∗∩D;
3. if n > 0, ∀i ∈ [1..n] (ai, ai-1) ∈ D∗ ;
4. ∃j ∈ [0..n] such that (aj, an) ∈ D∗ .

The set {a0, . . . , an} is said to be a c-expansion of a0.

Observe that, for any core argument, there can be several c-expansions. In what follows, we denote the set of all the core arguments w.r.t. IF, F and S as CORE(IF, F, S).

Example 3 Let IF ′ = 〈A,A? ,D,D? 〉 be the iAAF in Figure 1. Consider F = 〈A ∪ A? ,D ∪ D? 〉 and let S = {a}. Argument e is a core argument w.r.t. IF ′ , F and S, and {e} and {e, d, c} are its c-expansions. The set of all the core arguments w.r.t. IF ′ , F and S is CORE(IF ′ , F, S) = {c, d, e}.

The notions of core argument and c-expansion have been used to design Algorithm 1. This algorithm constructs a completion by first taking all the arguments and attacks, except the uncertain attacks towards S and the uncertain arguments that have a certain attack towards S and are not attacked by S (lines 1-2). Then, for each a ̸∈ S that is acceptable w.r.t. S, it performs the following tasks: first, it tries to make a unacceptable by checking whether a is attacked by a core argument b and removing every uncertain attack from S to b (lines 6-8); next, if a is still acceptable w.r.t. S, it removes a, if it is an uncertain argument (lines 9-11). As an example, Algorithm 1 applied to the iAAF IF ′ of Figure 1 and the set S = {a} builds the completion F ∗ obtained by removing the attacks (f, a) and (a, d) from IF ′ . Specifically, (f, a) is removed at line 2, while (a, d) at line 8 when considering the argument c (which is acceptable w.r.t. S, as S defends it from the attacks coming from b and d). At the end, Algorithm 1 returns true iff S is a complete extension of F ∗ . The following theorem shows that Algorithm 1 solves IPOSVERσ (S).

Theorem 2 IPOSVERσ (S) is in P under σ = co.

Proof. Algorithm 1 runs in polynomial time since both the following tasks are in P : verifying that S is a complete extension of the AAF F ∗ = 〈A∗ , D∗ 〉 constructed by the algorithm (line 6), and verifying if an argument b is a core argument w.r.t. F ∗ and S (line 7). The latter, in fact, can be done with a minor change to the standard in-depth visit of the argumentation graph of IF , where attacks are walked in their opposite sense. As for the correctness/completeness of Algorithm 1,

Algorithm 1 Deciding IPOSVERσ (S) under σ = co

Require: An iAAF IF = 〈A, A? , D, D? 〉 and a set S ⊆ A ∪ A? Ensure: The evaluation of the instance (IF, S) of IPOSVERσ (S) 1: A∗ = (A ∪ A? ) \ {a ∈ A? | ∃(a, b) ∈ D with b ∈ S ∧ ∄(c, a) ∈ D ∪ D? with c ∈ S} 2: D∗ = ((D ∪ D? ) \ {(a, b) ∈ D? |b ∈ S}) ∩ (A∗ × A∗ ) 3: CS = ∅ 4: while ∃a ∈ A∗ \ S s.t. a is acceptable w.r.t. S ∧ a ̸∈ CS do 5: CS = CS ∪ {a} 6: for all b ∈ CORE(IF, F ∗ , S) such that (b, a) ∈ D∗ do 7: for all (c, b) ∈ D∗ ∩D? with c∈S do 8: D∗ = D∗ \ {(c, b)} //removing attacks defending a 9: if a is acceptable w.r.t. S and a ∈ A? then 10: A∗ = A∗ \ {a} 11: D∗ =D∗ \ ({(x, a) ∈ D∗ } ∪ {(a, x) ∈ D∗ }) 12: return IsCompleteExtension(S, F ∗ ); //where F ∗ = 〈A∗ ,D∗ 〉

if S is a complete extension of F ∗ , then IPOSVERσ (S) obviously evaluates to true. Thus, we focus on the inverse implication, and assume by contradiction that S is a complete extension for a completion α = 〈A′ , D′ 〉, but not for F ∗ . The latter implies that either (I) S is not an admissible extension for F ∗ , or (II) ∃x ∈ A∗ /S s.t. x is acceptable w.r.t. S in F ∗ . It rather easy to see that (I) leads to a contradiction, thus we now consider the case (II). We distinguish two sub-cases: x∈A′ and x̸∈A′ , and consider only the first one, as the latter is trivial. Since S is a complete extension for α, then x is not acceptable w.r.t. S in α. This implies that x in α is attacked by either 1) an argument y ∈ S, or 2) an argument x1 ̸∈ S that is not attacked by S. In case (1), the attack (y, x) is not in D∗ , as otherwise x would not be acceptable w.r.t. S in F ∗ . Hence, (y, x) was removed at line 8 (as x ∈ A∗ , (y, x) cannot have been removed at line 11). Since this requires that x ∈ CORE(IF, F ∗ , S), then there is z ∈ CORE(IF, F ∗ , S) such that (z, x) ∈ D∗ (i.e., z is the argument attacking x in a c-expansion of x). Hence, in the subsequent steps of Algorithm 1, when x is considered at line 4, the argument z will be considered at line 6 and all the attacks from S to z removed from F ∗ (lines 7- 8). This will make x not acceptable w.r.t. S in F ∗ (as it is attacked by z which, in turn, is not attacked by S), which is a contradiction. In case (2), the argument x in α is attacked by an argument x1 ̸∈ S that, in turn, is not attacked by S. First, observe that there can be no argument x0 ∈ S such that (x1, x0) ∈ D′ , as otherwise S would not be a complete extension for α. However, since S is a complete extension for α, it holds that x1 is not acceptable w.r.t S in α. This implies that there is x2 ∈ A′ /S such that (x2, x1) ∈ D′ and x2 is not attacked by S and does not attack S. By iterating this reasoning, we can find a sequence of arguments x, x1, . . . , xn, with n ∈ [1..|A′ \ S|], that is a c-expansion of x. Hence, x1 ∈ CORE(IF, α, S), that implies x1 ∈ CORE(IF, F ∗ , S) (as Algorithm 1 preserves arguments/attacks occurring in any c-expansion). Hence, no attack from S to x1 is in F ∗ , as it is removed at line 8, thus contradicting that x is acceptable for S in F ∗ . ✷

We now consider σ = gr. In what follows, we still use the notions of core argument ad c-expansion, but applied

Algorithm 2 Checking IPOSVERσ (S) under σ = gr

Require: An iAAF IF = 〈A, A? , D, D? 〉 and a set S ⊆ A ∪ A? ; Ensure: true iff the instance (IF, S) of IPOSVERσ (S) is true; 1: F = 〈AF ,DF 〉 = 〈A∪S,D∩ ((A∪S) × (A∪S))〉 2: if S is not conflict free in F then 3: return false 4: GR = groundedExtension(F) 5: if GR∩S = ∅ then 6: return false 7: for all a ∈ S \GR do 8: F =〈AF ,DF∪{(ai, b)| (ai, b)∈D? ∧(b, a)∈DF∧ai∈ S}〉 9: GR = groundedExtension(F) 10: if S ̸⊆ GR then 11: return false 12: F ∗ = 〈AF∗ = A∪A? , DF∗ = D ∪DF ∪ (D? ∩ ((AF∗ \ S) × (AF∗ \ S)))〉 13: for all a ∈ GR \ S do 14: if a is a core argument w.r.t. F ∗ and S then 15: Add to F arguments/attacks of a c-expansion of a 16: GR = groundedExtension(F ); CS = ∅ 17: while ∃a ∈ ((GR \ S) \ CORE(F, F, S) \ Cs do 18: if ∃b ∈ S s.t. (b, a) ∈ D? then 19: F = 〈AF , DF ∪ {(b, a)}〉 20: GR = groundedExtension(F); CS = CS ∪ {a} 21: if S ̸= GR then 22: return false 23: return true

on traditional AAFs rather than iAAFs. In fact, any AAF F = 〈A,D〉 is an iAAF where everything is certain, thus: 1) a is a core argument w.r.t. F and S iff a is core argument w.r.t. 〈A, ∅,D, ∅〉, F and S; 2) a sequence a0, . . . , an is a c-expansion of a0 w.r.t. F and S iff it is a c-expansion of a0 w.r.t. 〈A, ∅,D, ∅〉, F and S. We also use the notion of extargument (w.r.t. F and S), that is an argument of F that either 1) is attacked by S, or 2) is a core argument w.r.t. F and S. As stated in Lemma 1, being an ext-argument somehow characterizes the arguments outside the grounded extension.

Lemma 1 Let F = 〈A,D〉 be an AAF, S ⊆ A, and GR the grounded extension of F . 1) If S = GR, then every a ∈ A\S is an ext-argument w.r.t. F and S; 2) If S ⊆ GR and every a ∈ GR\S is an ext-argument w.r.t. F and S, then S = GR.

As we will see, Lemma 1 is exploited to guide the strategy implemented in Algorithm 2, that solves IPOSVERσ (S) by incrementally building a completion where new uncertain attacks/arguments are inserted whenever their presence falsifies conditions preventing S from being the grounded extension.

Theorem 3 IPOSVERσ (S) is in P under σ = gr.

Proof. We prove that Algorithm 2 is correct and complete (its polynomiality can be shown analogously to Algorithm 1). If Algorithm 2 returns true (line 23), F is a completion of IF and S is the grounded extension for F, hence IPOSVERσ (S) is true. We now prove that, if Algorithm 2 returns false, there is no completion wherein S is the grounded extension. False is returned in four lines, and we consider them separately.

1. line 3 and line 6: straightforward.

ii) line 11: By contradiction, assume that there is a completion C different from F such that S is the grounded extension of C. Let S′ ⊂ S be the set of S's arguments having no incoming attack in F, and S′′ the set of arguments having no incoming attacks in C. It is easy to see that S′′ ⊆ S′ ⊆ S. Reasoning inductively, it can be proved that S = T ∗C (S′′ ) ⊆ T ∗ F (S′ ), where T ∗X (Y ) is the closure of TX(Y ) = Y ∪ {a ∈ AX | ∃(b, a) ∈ DX ∧ ∀(b′ , a) ∈ DX ∃s ∈ Y s.t. (s, b′ ) ∈ DX}, where X = 〈AX, DX〉 is a generic AAF and Y ⊆ AX. Basically, TX(Y ) differs from the standard operator computing the arguments acceptable w.r.t. Y in that TX(Y ) includes only new arguments with at least one incoming attack. From S = T ∗C (S′′ ) ⊆ T ∗ F (S′ ), and from the fact that T ∗ F (S′ ) ⊆ GR (which holds since S′ has no incoming attacks in F), we obtain S ⊆ GR, which contradicts that false is returned at line 11.

iii) line 22: By contradiction, assume that there is a completion F ′ = 〈A′ ,D′ 〉 wherein S is the grounded extension. Let F x = 〈Ax ,Dx 〉 be the status of the AAF F under construction immediately before executing line x, and GRx be its grounded extension. F ′ must contain all the arguments and attacks of F 13 , otherwise S would not be admissible in F ′ for what said in cases i), ii) and iii). Moreover, since S is the grounded extension in F ′ , Lemma 1 implies that every a ∈ A′ \ S is an ext-argument (i.e., either ∃(b, a) ∈ D′ with b ∈ S, or a is a core argument w.r.t. F ′ and S).

This means that, for each ext-argument a (w.r.t. F ′ and S) occurring in GR13 \S, it will be possible to augment F 13 with an attack from S to a or with arguments/attacks composing a c-expansion of a (in the algorithm, the arguments/attacks composing a c-expansion of a are taken from the F ∗ built at line 12, that, by construction, contains every c-expansion that may be in F ′ ). In particular, for every core argument a of F ′ in GR13 \ S, the algorithm will insert a c-expansion of a. The other arguments of F ′ in GR13 \ S are arguments attacked by S in F ′ , and, for each a of them, a c-expansion or an attack from S is inserted (in fact, F 13 may have been augmented with a c-expansion of a, even if in F ′ a was not a core argument but was attacked by S). Observe that every attack considered for the insertion into F 13 does not attack core arguments, thus any c-expansion in F 13 or inserted into F 13 at line 15 is still a c-expansion in F 21 . Therefore, every node of F 21 in GR21 \ S is an ext-argument w.r.t. F 21 and S. This, along with the fact S ⊆ GR21 (that can be proved using the same inductive reasoning used to prove point iii), implies that S is the grounded extension in F 21 (Lemma 1), thus contradicting that false is returned at line 22. ✷

As stated in what follows, the only case where the verification problems for i∗ - and i- extensions have the same complexity is σ = pr: the proof of the Σ2p -completeness in [Baumeister et al., 2018b] for i-extensions also applies to i∗ -extensions.

We now turn our attention to the necessary perspective. From the point of view of the computational complexity, switching from i-extensions to i∗ -extensions has no impact. In fact, it is easy to see that the upper bounds on the complexity of the verification of necessary i-extensions shown in [Baumeister et al., 2018b] also hold for our INECVERσ (S). Specifically, INECVERσ (S) can be solved by first checking whether all the arguments in S are certain (as Proposition 2 states that necessary i∗ -extension are i-extensions whose arguments are certain), and then invoking a solver verifying if S is an iextension. According to the results in [Baumeister et al., 2018b], this immediately implies that INECVERσ (S) is in P under σ ∈ {ad, st, co, gr} and in NP under σ ∈ {pr}. In particular, as for σ = pr, the lower bound can be proved by using the reduction used in the NP-hardness proof of [Baumeister et al., 2018b] when the incompleteness affects only the attacks: obviously, in this case the arguments in S are all certain, thus i- and i∗ - extensions coincide (Proposition 2). This proves the following theorem.

Theorem 5 INECVERσ (S) is in P under σ ∈ {ad, st, co, gr} and is NP -complete under σ ∈ {pr}.

Discussion of the results. The results on IPOSVERσ (S) are rather surprising. In fact, despite the change in the definition seems to be minimal, switching from i-extensions to i∗ -extensions has been shown to have a huge impact on the complexity of the verification in the possible perspective: for σ ∈ {ad, st, co, gr}, IPOSVERσ (S) is in P , while the verification of "original" i-extensions is NP-complete. Technically, the most difficult results are those on the polynomiality of IPOSVERσ (S) under σ ∈ {co, gr}. They have required an elaborate strategy for proving that a set S is an i∗ - extension based on the removal (for σ=co) and the insertion (for σ = gr) of arguments and attacks from/into the iAAF. Under σ = co, our strategy strictly generalizes that used in [Baumeister et al., 2018b] to show that verifying i-extensions is in P when only attacks are uncertain. In this partially incomplete setting, i-extensions and i∗ -extensions coincide (see Proposition 1). However, the strategy in [Baumeister et al., 2018b] cannot be used for Theorem 2, since it does not take into account the possibility of maintaining or discarding arguments besides attacks.

5 RelatedWork

Besides the works in [Baumeister et al., 2018b; CosteMarquis et al., 2007], many efforts have been devoted to the management of uncertainty in abstract argumentation. The Partial Argumentation Framework (PAF) introduced in [Cayrol et al., 2007] is one of the first attempts to incorporate qualitative uncertainty in AAFs. The main difference with iAAFs (besides the fact that the uncertainty in PAFs only affects the attacks) is in the semantics of extensions, that is not based on completions, but on re-defining the classical notion of admissibility under different levels of cautiousness (where only certain attacks or also uncertain attacks must be defended). Solving the verification problem over iAAFs is also related to the problems of revising AAFs to enforce the existence of an extension [Baumann and Ulbricht, 2019], or to make a set an extension [Coste-Marquis et al., 2015] (where, however, only minimal sets of changes are considered), and to the credulous/skeptical conclusion problems in Control Argumentation Frameworks [Dimopoulos et al., 2018] (where, however, there is no way no simulate the possible semantics for i-extensions of iAAFs with uncertain attacks).

Recently, the acceptance problem for iAAFs has been shown in [Baumeister et al., 2018a] to be NP-complete for every σ ∈ SEM in the possible credulous variant. Interestingly, the semantics of accepted argument used in [Baumeister et al., 2018a] corresponds to our i∗ -accepted argument, and not i-accepted argument. Thus, our results put some order in the literature of computational complexity of reasoning over iAAFs, since they show the expected exponential blow up when moving from the verification to the acceptance problem under σ ∈ {ad, st, co} ("expected" means that it is suggested by what happens for classical AAFs). Interestingly, this blow up also affects the grounded semantics, owing to the fact that different completions may have different grounded extensions. It is worth noting that this blow up would be unobservable by considering the verification problem over iextensions (rather than i∗ -extensions), that is beyond P.

Among the approaches allowing a quantitative specification of the uncertainty in AAFs (for instance, in terms of preferences and/or weights [Bench-Capon, 2003; Amgoud and Vesic, 2011; Modgil, 2009; Dunne et al., 2011; Coste-Marquis et al., 2012; Brewka et al., 2014], or of probabilities [Hunter, 2014; Dung and Thang, 2010; Doder and Woltran, 2014; Dondio, 2014; Hunter, 2012; Li et al., 2011; Fazzinga et al., 2013; 2015; 2018; Thimm, 2012; Hunter and Thimm, 2014], or of trust degrees [Fazzinga et al., 2020]), the most related to our framework is the probabilistic AAF (prAAF) of [Li et al., 2011], where arguments/attacks are independent events associated with marginal probabilities. In fact, an iAAF can be viewed as a prAAF where the marginal probabilities are replaced with boolean values encoding the two alternatives certain/uncertain, so that any instance of IPOSVERσ (S) can be reduced to the problem P-EXT(S) of computing the probability of an extension in a prAAF, i.e., the sum of the probabilities of the possible worlds where S is an extension. In the light of this, our results on IPOSVERσ (S) under σ ∈ {co, gr} are of particular interest: in fact, while in [Fazzinga et al., 2015; 2019] P-EXT(S) was shown to be intractable (namely, FP #P -complete) under these semantics, in this work we have shown that IPOSVERσ (S) is in P.

6 Conclusions

The notion of i-extension, adapting the notion of extension to incomplete AAFs, has been revisited. Under the possible perspective, i-extensions have been show to violate relevant properties of "traditional" extensions, such as the conflictfreeness. An alternative notion (i.e., i∗ -extension) has been introduced and its beneficial effects on the semantics and the complexity have been shown. Future work will focus on variants of the possible and necessary perspectives that are supported by a minimum number of completions.