When Incompleteness Does Not Matter: The Case of Incomplete Abstract Argumentation Framework (Under the Possible Perspective)

1 Introduction

Abstract Argumentation Frameworks (AAF) [Dung, 1995] are a well-established AI paradigm, valued for their flexibility in modeling diverse problems-from dispute management to fields like process mining [Fazzinga et al., 2022]. This success has driven research into AAF extensions designed to broaden their scope, particularly those capable of encoding uncertainty. In this regard, probabilistic AAFs have been introduced to enrich AAFs with quantitative information about the likelihood of arguments and attacks [Li et al., 2011; Fazzinga et al., 2015; Fazzinga et al., 2019]), thereby representing a probability distribution over the candidate frameworks. While probabilistic AAFs encode the uncertainty quantitatively, incomplete AAFs (iAAFs [Baumeister et al., 2018; Fazzinga et al., 2020; Fazzinga et al., 2026]) extend AAFs by introducing qualitative uncertainty: arguments or attacks may be marked as uncertain, meaning they may or may not occur, without committing to probability values.

∗Contact Author

This simple mechanism makes iAAFs particularly intuitive and user-friendly: an analyst can compactly describe a range of possible argumentation scenarios by labeling some components as potentially absent. As a consequence, several works have examined different aspects of iAAF reasoning, such as the complexity of acceptance and extension verification, algorithmic procedures for evaluating the acceptance status, and generalizations incorporating supports or correlations between uncertain components [Baumeister et al., 2021; Fazzinga et al., 2020; Fazzinga et al., 2021a; Fazzinga et al., 2021b; Fazzinga et al., 2023; Fazzinga et al., 2026; Mailly, 2024].

Example 1. Lawyer Ann is reasoning about an upcoming trial. To anticipate how the jury might evaluate the evidence, Ann mentally adopts the jury's perspective and constructs an abstract argumentation model of the case. Witness and expert statements are represented as arguments, while the conflicts between the statements (as supposedly perceived by the jurors) as attacks. The resulting argumentation graph is in Figure 1(a). In the attempt to foresee which lines of reasoning the jury could find persuasive, Ann looks into the preferred extensions of the so-obtained argumentation framework, and realizes that the unique preferred extension is S1 = {y, z, b}.

Now, Ann is not sure that the witness that is supposed to claim the argument z will show up at the trial, and that the jury will perceive the attack between arguments y and a (since the jurors may not have the technical skills required to perceive this attack). Hence, Ann decides to "upgrade" to the iAAF paradigm, and specifies that argument z and attack (y, a) are uncertain (see Figure 1(b)). This means that the four alternative scenarios for the argumentation graph in Figure 1(c), called completions, must be now considered. Correspondingly, the possible and the necessary perspectives for the reasoning can be adopted: under the possible (resp., necessary) perspective, a set S is an extension and an argument a is accepted if and only if S is an extension and a accepted in at least one (resp., in every) completion. Thus, by reasoning under the possible perspective, Ann gets the information that, as the uncertainty may be resolved in different ways, not only S1 should be considered as a preferred extension, but also S2 = {y, b} and S3 = {y, a}, that are possible extensions (as they are extensions in C3 and C4, respectively). In turn, not only the arguments y, z, b should be considered as accepted, since also a turns out to be possibly accepted (as it is accepted in C4). So, Ann is now aware that there is some chance that the jury will perceive a as a justified argument, and, if she believes that a is contrary to her client's interests and if she does not want to run the risk of this situation occurring, she may decide to invest in presenting additional arguments that could weaken a. ✷

Despite the considerable attention devoted to iAAFs, a fundamental question remains open: does adding qualitative uncertainty to AAFs genuinely increase expressive power? More precisely, given an iAAF IF, it is unknown whether reasoning based on its possible or its necessary extensions can be accomplished by reasoning over the extensions of an AAF "equivalent" to IF .

In this paper, we address this gap. Specifically, we focus on the possible perspective of the reasoning and study whether, given an iAAF IF, there exists an AAF F such that: (i) the set of its extensions coincides with the set of possible extensions of IF (equivalence); or (ii) the possible extensions of IF can be recovered from the extensions of F by projecting away auxiliary arguments introduced to simulate uncertainty (projection-equivalence).

Our results reveal a nuanced picture. Under the admissible semantics, every iAAF admits an equivalent AAF. Under the stable and the preferred semantics, every iAAF admits a projection-equivalent AAF. For other classical semantics (i.e. grounded and complete), we show that neither equivalence nor projection-equivalence necessarily holds. Besides clarifying the expressive relationship between iAAFs and AAFs, our analysis has practical implications: when equivalence or projection-equivalence is achievable, we provide explicit algorithms translating an iAAF into an equivalent (or projection-equivalent) AAF whose size is linear in the size of the iAAF. This is in some ways surprising: the completions of an iAAF are exponential in the size of the iAAF, so it is not obvious that traditional reasoning on an AAF of comparable size can account for an exponential number of scenarios. Given this, we show in which cases the so-obtained AAFs can be used as the input of standard argumentation reasoners (working over AAFs) to solve the verification, extension counting or enumeration, and acceptance problems over iAAFs, without the need for an ad-hoc machinery.

Beyond its immediate contribution to abstract argumentation theory, this work has broader implications for several areas of Artificial Intelligence concerned with reasoning under uncertainty. By addressing conditions under which qualitative uncertainty can be compiled away, our results contribute to a deeper understanding of the expressiveness of formalisms with incomplete knowledge: this insight is relevant to knowledge representation and non-monotonic reasoning, where similar questions arise concerning the expressive role of language extensions designed to model incomplete information [Governatori et al., 2004]. Moreover, the ability to reason about incomplete argumentative structures while ultimately relying on classical frameworks can inform the design of reasoning mechanisms in multi-agent systems, where agents often operate with partial views of others' beliefs or interactions [Herzig and Yuste Ginel, 2021].

2 Preliminaries

We assume that the reader is familiar with Abstract Argumentation Frameworks (AAFs) and, in particular, with the notions of extension and of credulously (Cr-) and skeptically (Sk-) accepted argument, under the so-called Dungean semantics: admissible (ad), stable (st), grounded (gr), complete (co), preferred (pr). AAFs will be denoted as pairs of the form ⟨A,D⟩, where A and D are the sets of arguments and attacks, respectively. Given an AAF F under a semantics σ, we will denote the set of its extensions as σ(F), and the sets of its credulously and skeptically arguments as CAσ (F) and SAσ (F), respectively. Given this, we here review incomplete Abstract Argumentation Frameworks (iAAFs) [Baumeister et al., 2018], that allow the uncertainty affecting the presence of arguments and attacks to be qualitatively modeled.

Definition 1. An incomplete AAF (iAAF) is a tuple IF = ⟨A,A? ,D,D? ⟩, where A and A? are disjoint sets of arguments, and D and D? disjoint sets of attacks between arguments in A ∪ A? . The arguments and attacks in A and D (resp., A? and D? ) are said to be certain (resp., uncertain), since they are (resp., are not) guaranteed to occur. If D? = ∅ (resp., A? = ∅), IF is called an argument-incomplete AAF, or arg-iAAF (resp., an attack-incomplete AAF, or att-iAAF).

iAAFs compactly represent the alternative scenarios for the argumentation graph, i.e. the possible combinations of arguments and attacks that can occur according to what is certain and uncertain. Each scenario is an AAF called completion.

Definition 2 (Completion). Given an iAAF IF = ⟨A, A? , D, D? ⟩, a completion of IF is an AAF F = ⟨A′ , D′ ⟩ where A ⊆ A′ ⊆ (A ∪ A? ) and D ∩ (A′ × A′ ) ⊆ D′ ⊆ (D ∪ D? ) ∩ (A′ × A′ ).

The possible and necessary perspectives are natural ways to account for the presence of multiple completions when adapting the notions of extension and acceptance to iAAFs:

Definition 3. Let IF be an iAAF, S a set of arguments, a an argument, and σ a semantics. S is said to be an extension and a an X-accepted argument (with X ∈ {Cr, Sk}) under the possible (resp., necessary) perspective if, for at least one (resp., every) completion F of IF , S is an extension of F and a an X-accepted argument of F , respectively.

Under a semantics σ, we denote the sets of possible and necessary extensions of an iAAF IF as σpos (IF) and σnec (F), the sets of its credulously and skeptically accepted arguments as PCAσ (IF) and PSAσ (IF), under the possible perspective, and as NCAσ (IF) and NSAσ (IF), under the necessary perspective, respectively.

Example 2. Under σ = ad, the possible extensions of the iAAF IF in Figure 1(b) are σpos (IF)= { ∅, {y}, {z}, {y, b}, {z, b}, {a}, {y, a}} (in particular, {a}, {y, a} are extensions of C4). Among these, only ∅ and {y} are necessary extensions. Moreover, PCA ad = {y, z, a, b}, i.e. every argument is possibly Cr-accepted, since it is Cr-accepted in at least one completion. Indeed, PSA ad = NSA ad = ∅, i.e. no argument is Sk-accepted (neither possibly nor necessarily), since ∅ is an extension of every completion.

3 Problem Statement

Inspired by the motivations outlined in the introduction, we seek to provide insights into whether there is a difference in expressiveness between the iAAF and AAF paradigms: more specifically, whether it is feasible to simulate the reasoning over iAAFs based on the adaption of the notion of extension (reviewed in Section 2 - Definition 3) via the traditional extension-based reasoning over AAFs. In particular, we focus on the possible perspective of the reasoning, and defer the study of the necessary perspective to future work.

To this end, we introduce two notions of equivalence between iAAFs and AAF (in doing this, we use the projection operator Π defined as follows: given two sets of arguments A, S, and a set of sets S, ΠA(S) is the set S ∩A, and ΠA(S) the set {S′ |∃X ∈ S s.t. ΠA(X) = S′ }).

Definition 4. Let IF = ⟨A,A? ,D,D? ⟩ be an iAAF, F = ⟨A′ ,D′ ⟩ an AAF, and σ a semantics. IF and F are equivalent, written as IF ≡σ F (resp., projection-equivalent, written as IF ≡σΠ F) if σpos (IF) = σ(F) (resp., σpos (IF) = ΠA∪A? σ(F )).

Obviously, IF ≡σ F implies IF ≡σΠ F. Given this, the problem addressed in the rest of the paper is:

"Let σ be a semantics. Does there always exist, for any iAAF IF, an AAF F such that IF ≡σ F or, at least, IF ≡σΠ F?"

Indeed, in posing this question we impose no restriction on how equivalent or projection-equivalent AAFs may be constructed. The only obvious constraint, stemming from the notion of equivalence, is that such AAFs must contain all arguments occurring in the possible extensions of the iAAF. That said, the difference between equivalence and projectionequivalence is in the role of any new arguments introduced to define parts of the AAF that simulate uncertainty. In the case of equivalence, these new arguments serve only as auxiliary devices to support the reasoning process and do not belong to the extensions. In contrast, under projection-equivalence, such arguments may end up being integral parts of the extensions, although they can be ignored when projecting the extensions to obtain the possible extensions. Apart from this distinction, the problem formulation leaves complete freedom to add or remove arguments and attacks, allowing the construction of equivalent AAFs of arbitrary size. In answering this question, however, we will be precise: when we claim a positive result, we show that an equivalent AAF of comparable size -namely, linear size- can be constructed. When we claim a negative result, we mean that no such construction exists, even imposing no bound on the size of the AAF.

4 When Do IAAFs Admit Equivalent or Projection-Equivalent AAFs?

We address the fundamental research question introduced so far starting from the case of admissible semantics. In this case, we introduce Algorithm 1, that translates any input iAAF IF into an equivalent AAF F. The underlying rationale is summarized by the following intuitions, that suggest how the uncertainty in an iAAF can be "reduced", by reformulating uncertain arguments/attacks as (groups of) certain arguments and attacks:

-I1 : the semantics of an iAAF (i.e. the set of possible extensions) does not change if every uncertain argument a that is source of no certain attack is converted into a certain argument. The reason is twofold: 1) the fact that all attacks stemming from a (if any) are uncertain suffices to model the case where no argument is attacked by a or defended by a; 2) even if a is made certain, the possibility that a is not included in some extensions is still guaranteed by the admissible semantics, that does not force the arguments that are acceptable w.r.t an extension to be included in the extension itself.

-I2 : also the case where an uncertain argument a is the source of certain attacks can be simulated by making a certain, but now also a counterattack (b, a) must be introduced for each certain attack (a, b) stemming from a. This allows any argument b attacked by a to be in a possible extension not containing a, if this is not forbidden by the relationship of b with the arguments other than a; such a possibility, when a was uncertain, was granted in the completions without a.

-I3 : uncertain attacks towards arguments attacking no argument have no impact on the set of possible extensions, so they can be discarded. The reason is that removing these attacks does not discard any defense in any scenario (so it does not deprive any argument from a chance of being accepted in some scenario), and preserves the possibility that the target arguments of these attacks belong to some possible extension.

-I4 : uncertain attacks towards arguments attacking some argument, on the contrary, have an impact on the set of possible extensions. However, in this case, the effects of the uncertain attacks (y, a) can be simulated by creating a selfcontradicting argument δa and performing the following actions for each certain attack (a, b) stemming from a: A1 : make δa attack b (basically, (δa, b) replicates the role of (a, b)); A2 : make b counterattack a; A3 : make every argument attacking a attack δa; A4 : discard the uncertain attacks (y, a). The intuition is that the counterattack (b, a) allows b to be put in an extension provided that at least one other argument defending it against the attack from δa is in the extension as well, and this is the same as what happens in the original iAAF for b, that can be included in the possible extensions containing at least one argument counterattacking (a, b).

Algorithm 1 implements these intuitions as follows. Lines 3-6 transform the input IF into an iAAF IF ′ with a "reduced amount of uncertainty": basically, they follow intuitions I1, I2, as they 1) materialize the counterattacks against certain attacks from uncertain arguments, and 2) transform uncertain arguments into certain arguments. Then, the for loop starting at line 7 accomplishes actions A1, A2, A3, according to I4; finally, the deletions of the uncertain attacks Algorithm 1: Translating an iAAF into an equivalent

AAF under σ = ad 1 Input: An iAAF IF = ⟨A,A? ,D,D? ⟩ 2 Output: An AAF F such that IF ≡σ F under σ=ad 3 D∗ ← {(b, a)|a ∈ A? ∧ b ∈ A ∪ A? ∧ (a, b) ∈ D}; 4 D′ ←D∪D∗ ; D′? ←D? \D∗ ; 5 A′ ←A∪A? ; 6 IF ′ = ⟨A′ , ∅,D′ ,D′? ⟩; 7 for a ∈ A′ such that ∃(y, a) ∈ D′? ∧ ∃(a, b) ∈ D′ do 8 Let δa be a new argument; 9 A′ ←A′ ∪ {δa}; D′ ←D′ ∪ {(δa, δa)}; 10 for (a, b) ∈ D′ do 11 D′ ← D′ ∪ {(δa, b), (b, a)}; 12 for (x, a) ∈ D′ ∪ D′? do 13 D′ ← D′ ∪ {(x, δa)}; 14 return the AAF F = ⟨A′ ,D′ ⟩;

(suggested by I3 and I4) are implicitly performed by not including the uncertain attacks in the output AAF (line 14).

Performing these steps over the iAAFs on the left-hand side of Figure 2 yields the AAFs on its right-hand side. As for IF ′ : 1) the attack (z, a) (stemming from the uncertain argument z) yields the counterattack (a, z); 2) all the uncertain arguments are made certain; 3) the uncertain attacks (y, a) and (b, a) are removed and trigger no other action, as their target argument is no source of certain attacks. As for IF, the attack (z, a) again yields the counterattack (a, z), while the chain of attacks (y, a), (a, b) is expanded into the portion of AAF consisting of the self-contradicting argument δa that is attacked by every argument attacking a and that attacks b (which, in turn, defends itself against a). The uncertain attack (y, a) is not included in F.

The correctness and the complexity of Algorithm 1 (which implies the size of the AAF into which an input iAAF is translated) are formally stated in what follows.

Theorem 1. Algorithm 1 runs in linear time in the size of the input iAAF IF, and returns an AAF F such that IF ≡ad F.

We now focus on the other Dungean semantics, and show a negative result. That is, it is no more always possible to transform an iAAF into an equivalent AAF, even if no limits are imposed on the size of the AAF and even if the uncertainty is limited to involve only the arguments or the attacks.

Theorem 2. Under σ ∈ {st, co, gr, pr}, there are at least one arg-iAAF IF and one att-iAAF IF ′ such that no AAF F is such that IF ≡σ F and no AAF F ′ is such that IF ′ ≡σ F ′

Proof. Under σ = co, the att-iAAF IF ′ = ⟨A,D,D? ⟩, with A = {a, b, c}, D = {(b, c)}, D? = {(a, b)}, and the arg-iAAF IF= ⟨A,A? ,D⟩, with A = {b, c}, A? = {a}, D={(a, b), (b, c)}, admit no equivalent AAF, since both IF ′ and IF have two possible extensions whose intersection is not a possible extension, while intersecting any two complete extensions of an AAF yields a complete extension.

As for σ ∈ {st, pr, gr}, counterexamples proving the statements are the att-iAAF IF ′ = ⟨A,D,D? ⟩, with A = {a, b}, D = ∅, D? = {(a, b)}, and the arg-iAAF IF = ⟨A,A? ,D⟩, with A = {a}, A? = {b}, D = ∅. The point is that in every AAF F: 1) under σ ∈ {st, pr}, ̸ ∃S′ , S′′ ∈ σ(F) such that S′ ⊂ S′′ ; 2) under σ = gr, |σ(F)| = 1. ✷

Theorem 2 does not rule out the existence of a translation from iAAFs to projection-equivalent AAFs under Dungean semantics different from ad. We show that this holds for σ ∈ st, pr, starting with the stable semantics.

We first provide the intuitions that will guide us towards the definition of Algorithm 2, that transforms iAAFs into projection-equivalent AAFs under σ = st:

I1 : under the stable semantics, every extension S has this property: for each argument a, either a is in S, or an argument xa attacking it is in S. Hence, in an iAAF, an uncertain argument a can be transformed into a certain argument in mutual attack with a new argument xa: the possible extensions not containing a will become possible extensions containing xa, while those containing a are preserved;

I2 : once all the uncertain arguments have been made certain as described above, the only uncertain components still occurring in the iAAF (if any) are uncertain attacks between certain arguments. Thus, a single uncertain attack (a, b) can be simulated by replacing it with a new certain portion of iAAF, consisting of two new arguments δ′ab , δ′′ ab , and the attacks (a, δ′ab ), (δ′ab , δ′′ ab ), (δ′′ ab , b), (b, δ′′ ab ) (see Figure 3). In fact, there is a one-to-one correspondence between the sets of possible extensions before and after the replacement of (a, b). Specifically, every set S that was a possible extension before the replacement is still a possible extension, if both a ∈ S and b ∈ S; otherwise, S gives rise to the possible extension S′ resulting from augmenting S with δ′ab , if a ̸∈ S, or with δ′′ ab , if a ∈ S ∧ b ̸∈ S.

Following these intuitions, Algorithm 2 is divided in two phases: lines 3-7 transform every uncertain argument a into a certain argument with a mutual attack with the new argument xa. Then, lines 9-12 create, for each uncertain attack (a, b), the new arguments δ′ab , δ′′ ab and the above described attacks involving them and a, b. Finally, Algorithm 2 inserts the new sets of arguments and attacks A∗ and D∗ obtained this way in the returned AAF, where the uncertain attacks of the input iAAF are not included. Figure 3 shows an example of transformation made by Algorithm 2, along with the set of possible extensions of the input iAAF and the set of extensions of the returned projection-equivalent AAF.

We now address the preferred semantics. The main idea underlying our strategy for transforming an iAAF into a projection-equivalent AAF is based on forcing the reasoning over the returned AAF to consider the completions of the original iAAF. More specifically, the following intuitions will Algorithm 2: Translating an iAAF into a projectionequivalent AAF under σ = st

1 Input: An iAAF IF = ⟨A,A? ,D,D? ⟩ 2 Output: An AAF F such that IF ≡σΠ F under σ=st 3 ˆ A ← {xa|a ∈ A? }; 4 A′ ←A∪A? ∪ ˆ A; 5 ˆD← {(xa, a), (a, xa)|a ∈ A? }; 6 D′ ←D∪ ˆD; 7 IF ′ = ⟨A′ , ∅,D′ ,D? ⟩; 8 A∗ = ∅; D∗ = ∅; 9 for (a, b) ∈ D? do 10 Let δ′ab and δ′′ ab be new arguments; 11 A∗ ←A∗ ∪ {δ′ab , δ′′ ab }; 12 D∗ ←D∗ ∪{(a, δ′ab ), (δ′ab , δ′′ ab ), (δ′′ ab , b), (b, δ′′ ab )}; 13 return the AAF F = ⟨A′ ∪A∗ ,D′ ∪D∗ ⟩;

guide the transformation:

I1 : if we focus on the uncertain arguments, the various completions of the original iAAF come from choosing, for each of these arguments, if it is included or not. For each uncertain argument a, this choice can be simulated by making it certain and then augmenting the iAAF with a pair of arguments xa, xa in mutual attack, along with the attack (xa, a). This way, a possible extension S coming from a completion C in the original iAAF corresponds to a possible extension S′ of the new iAAF containing xa if a ∈ C, and xa if a ̸∈ C.

I2 : once all the uncertain arguments have been made certain, the various completions come from choosing, for each of uncertain attack (a, b), if it is included or not. Again, this choice can be simulated by means of a pair of arguments δab, δab in mutual attack, that are connected to the chain (a, δ′ab ), (δ′ab , δ′′ ab ), (δ′′ ab , b) by means of the attack (δab, δ′′ ab ). Such a chain introduces two new arguments δ′ab , δ′′ ab and plays a role similar to the chain introduced by Algorithm 2 under σ=st.

Algorithm 3 implements these intuitions, as lines 3-7 make certain every uncertain argument a (and create the new portion of AAF involving the new arguments xa, xa). Then, lines 9-12 replace each uncertain attack with the structure described in the discussion of intuition I2. Figure 4 shows an example of transformation made by Algorithm 3. The reader can easily check that the projection of σ(F) over the original arguments coincides with σpos (IF ).

The correctness and the complexity of the transformation algorithms under the stable and preferred semantics are formally characterized in the following statement.

Algorithm 3: Translating an iAAF into a projectionequivalent AAF under σ = pr

1 Input: An iAAF IF = ⟨A,A? ,D,D? ⟩ 2 Output: An AAF F such that IF ≡σΠ F under σ = pr 3 ˆ A ← {xa, xa|a ∈ A? }; 4 A′ ←A∪A? ∪ ˆ A; 5 ˆD← {(xa, xa), (xa, xa), (xa, a)|a ∈ A? }; 6 D′ ←D∪ ˆD; 7 IF ′ = ⟨A′ , ∅,D′ ,D? ⟩; 8 A∗ = ∅; D∗ = ∅; 9 for (a, b) ∈ D? do 10 Let δab, δab, δ′ab and δ′′ ab be new arguments; 11 A∗ ←A∗ ∪ {δab, δab, δ′ab , δ′′ ab }; 12 D∗ ←D∗ ∪ {(δab, δab), (δab, δab), (δab, δ′′ ab ), (a, δ′ab ), (δ′ab , δ′′ ab ), (δ′′ ab , b)}; 13 return the AAF F = ⟨A′ ∪A∗ ,D′ ∪D∗ ⟩;

Theorem 3. Algorithms 2 and 3 run in linear time in the size of the input iAAF IF, and return an AAF F such that IF ≡σΠ F , with σ = st and σ = pr, respectively.

The theorem below states that what happens under σ ∈ {st, pr} cannot be extended to σ ∈ {co, gr}, even if no polynomial bound is imposed on the size of the AAF.

Theorem 4. Under σ ∈ {co, gr}, there is at least one argiAAF IF and one att-iAAF IF ′ such that there is no AAF F such that IF ≡σΠ F and no AAF F ′ such that IF ′ ≡σΠ F ′ .

5 Properties and Usability of the Transformations

By looking into the algorithms, it is easy to see that the transformations satisfy the following properties:

• linearity of the size: the sizes of the AAFs returned by Algorithms 1, 2, 3 are linear in the size of the input iAAF (as implied by that fact that the algorithms run in linear time);
• preservation of arguments and of certain attacks: all the arguments and the certain attacks in the original iAAF still occur in the returned AAF;
• argument-invariance (only under σ = ad): when the uncertainty involves only arguments and/or attacks toward arguments attacking no further argument, the transformation introduces no new arguments (besides preserving all the original arguments and the certain attacks, as said above).

Overall, these properties say that the transformations generate AAFs where a portion of the original argumentation graph is preserved and whose size does not explode. In the case where the argument invariance is guaranteed, no new dummy arguments are needed, so the resulting AAF may be even easily readable by expert analysts. In any case, in what follows we study how the obtained AAFs, even if they did not prove easily interpretable by humans, are useful to support the reasoning over the original iAAF.

Proposition 1. Let IF = ⟨A,A? ,D,D? ⟩ be an iAAF, S a set of its arguments, and F ad , F st , F pr the AAFs returned by running Algorithms 1, 2, 3 over IF, respectively. Then:

• under σ = ad, S ∈ σpos (IF) iff S ∈ σ(F ad );
• under σ = st, S ∈ σpos (IF) iff S′ ∈ σ(F st ), where: S′ = S ∪ {xa|a ∈ A? ∧ a ̸∈ S} ∪ {δ′ab |(a, b) ∈ D? ∧ a ̸∈ S} ∪ {δ′′ ab |(a, b) ∈ D? ∧ a ∈ S ∧ b ̸∈ S};
• under σ=pr, S∈σpos (IF) iff ∃S′ ∈ σ(F pr ) such that:
• S = ΠA∪A? (S′ ), and
• for each a ∈ A? , it holds that: if a ∈ S then xa ∈ S′ , otherwise, exactly one between xa and xa is in S′ ;
• for each (a, b) ∈ D? it holds that: Π{δab ,δab ,δ′ab ,δ′′ ab } (S′ ) ∈ {{δab}, {δab, δ′ab }, {δab}, {δab, δ′ab }, {δab, δ′′ ab } }.
• under σ ∈ {ad,st,pr}, PCAσ (IF) = ΠA∪A? (CAσ (F σ ));
• under σ ∈ {co,pr}, PCAσ =ΠA∪A? (CA ad (F ad ));
• under σ ∈ {st,pr}, NSAσ (IF) = ΠA(SAσ (F σ )).

Basically, the above proposition states that there is a lineartime computable bijection f between σpos (IF) and σ(F σ ) under σ ∈ {ad, st}. The correspondence in the left-to-right direction implies that the problem of verifying a specific set S as a possible extension of IF is equivalent to verifying f(S) as an extension of F σ , thus providing an efficient scheme for solving the verification over iAAFs by resorting to standard verification solvers over AAFs. On the other hand, the right-to-left correspondence allows us to solve the enumeration and the count of the possible extensions over iAAFs by invoking solvers of these problems over AAFs. Under the preferred semantics, instead, the above proposition implies that each possible extension of IF may correspond to an exponential number of extensions of F pr . For instance, in the case in Figure 4, the possible extension S = {d, b} corresponds to the two extensions {xd, δab, δ′ab , d, b} and {xd, δab, δ′ab , d, b} (in the sense that both the projections of these extensions over A∪A? are S). The reason is that S is an extension in two completions of IF (those containing d, and differing in the presence/absence of (a, b)), so it corresponds to two extensions of F pr . In fact, F pr encodes the completions of IF via the pairs of arguments xa, xa and δab, δab, so the extensions of F pr corresponding to S both contain xd and differ in the presence of δab or δab. Hence, checking if a set is a possible extension of IF may require multiple invocations of extension-checkers over F pr (that is: checking if S ∈ σpos (IF) requires to check if at least one S′ augmenting S as stated in Proposition 1 is in σ(F pr )). Vice versa, the fact that multiple extensions of F pr may correspond to the same possible extension of IF makes any machinery counting the extensions of F pr not usable for counting the possible extensions of IF. However, enumeration algorithms for preferred extensions can be still used on F pr for obtaining (after projections) the possible extensions of IF: in this regard, it should be studied (experimentally and theoretically) when enumerating on F pr and then projecting is more efficient than enumerating the completions of IF, and then enumerating the extensions of each completion and removing the duplicates (as a set can be extension in different completions).

As for the acceptance, Proposition 1 ensures that running traditional solvers for the credulous and skeptical acceptance over the AAFs returned by algorithms 1, 2, and 3 allows us to solve the possible credulous acceptance under σ ∈ {ad, st, pr} and the necessary skeptical acceptance under σ ∈ {st, pr}, without the need to resort to an ad hoc machinery for these acceptances over iAAFs (in particular, PCA co and PCA pr reduce to the case σ = ad). An analogous result does not hold for PSA and NCA: checking if an argument is PSA or NCA requires reasoning not only on the possible extensions, but also on the completions where these extensions come from, since these acceptances encode the membership to one extension of each completion or to every extension of one completion, respectively. In fact, as for σ ∈ {ad, st}, the level of completions is not encoded at all in the AAFs F ad and F st : indeed, the bijection between σpos (IF ) and σ(F σ ) does not allow to reason on the multiple completions of IF where a possible extension S comes from by only looking into S as an extension of F σ . As for σ = pr, as explained above, the AAF F pr instead encodes the completions of IF. However, the CA and SA tests for an argument a do not allow to impose complex conditions on the arguments occurring with a in the extensions (in particular, on the arguments encoding the completions), so they cannot be used over F pr to solve PSA and NCA.

Remark on σ = pr. We have discussed how the results of Proposition 1 limit the re-usability of standard machinery for the verification problem over AAFs for the case of iAAFs. These limitations would be overcome if we could resort to a new transformation from iAAFs to projection-equivalent AAFs which admits an efficiently computable function associating the possible extensions of the input iAAF to the extensions of the returned AAF. Proposition 2 states that this is not possible: due to the strictly higher complexity of verification problems for iAAFs compared to AAFs, no such transformation can exist.

Proposition 2. Under the standard assumption PNP ̸=NPNP and under σ =pr, there is no polynomial-time transformation from any iAAF IF to a projection-equivalent AAF F such that the function f defined as:

∀S ∈ σpos (IF) f(S) = {S′ ∈ σ(F)|S = ΠA∪A?S′ } is computable in polynomial time.

6 RelatedWork

Most of the research works dealing with iAAFs use the notion of extension addressed in this work (some other works adopt a different semantics, where the notions of conflict-freeness and defenses are adapted to account for the presence of uncertainty [Coste-Marquis et al., 2007; Cayrol et al., 2007;

Mailly, 2023; Mailly, 2024]). In particular, the possible extensions studied in this work were introduced in [Fazzinga et al., 2020; Fazzinga et al., 2026] (where they are called i∗ -extensions) to fix some counterintuitive behavior exhibited by the first proposal of the notion extension to iAAFs [Baumeister et al., 2018], and are at the basis of several generalizations of iAAFs (such as [Fazzinga et al., 2021a; Fazzinga et al., 2021b] and [Fazzinga et al., 2023] where the possibility of specifying correlations between uncertain arguments/attacks and of specifying supports between arguments have been studied, respectively). A first attempt to reduce the incompleteness in iAAFs was accomplished in [Alfano et al., 2023], where it was shown that, under σ ∈ {st, gr, co, pr}, an iAAF IF = ⟨A,A? ,D,D? ⟩ can be transformed into an arg-iAAF or att-iAAF IF ′ such that σpos (IF) = ΠA∪A?σpos (IF ′ ). Our results under σ ∈ {st, pr} are stronger, as our transformations completely remove the incompleteness. Moreover, in some sense, our analysis strengthen the results in [Alfano et al., 2023] under σ ∈ {gr, co}, as we prove that it is not possible to completely remove the incompleteness. Moreover, under σ = ad, we also provide the strong and elegant result regarding the equivalence between iAAFs and AAFs.

The results in this paper complete and put order in the picture of iAAFs provided by characterization of the computational complexity of the (possible) verification and acceptance problems in [Baumeister et al., 2021; Fazzinga et al., 2020; Fazzinga et al., 2026]. In this regard, in [Fazzinga et al., 2020], the (possible) verification problem over iAAFs has been shown to be in P under σ ∈ {ad, st, gr, co} (the same as over AAFs) and Σ2p -complete under σ = pr (that is one level higher than over AAFs, where it is coNP-complete). Basically, our results show that there is no one-to-one correspondence between the equality of complexity of the verification problem over iAAFs and AAFs and the existence of (projection-)equivalent transformations from iAAFs and AAFs. In fact, under the semantics where the complexities coincide, it can happen that: 1) an equivalent transformation exists (case σ = ad), 2) an equivalent transformation does not exist, but a projection-equivalent transformation exists (case σ = st), 3) no projection-equivalent transformation exists (case σ ∈ {co, gr}). Then, when we turn our attention to σ = pr, under which the verifications over iAAFs and AAFs are not of the same complexity, again it happens that the existence of a projection-equivalent AAF for any given iAAF is guaranteed. Observe that under σ ∈ {ad, st}, Algorithms 1 and 2 can be used as reductions from the verification problem over an iAAF IF to the verification problem over an AAF F, since in both cases they build AAFs with a one-toone correspondence between σpos (IF) and σ(F). As a matter of fact, the existence of such a transformation/reduction is compatible with the equality of the complexities of the verifications over iAAFs and over AAFs under σ ∈ {ad, st}. On the other hand, under σ = pr, since verification over iAAFs is strictly harder than over AAFs, Proposition 2 guarantees that no such transformation/reduction exists.

This work is also related to the study of equivalence between AAFs [Baumann, 2012; Baumann et al., 2017; Dung, 1995; Oikarinen and Woltran, 2010] and realizability [Baumann and Heine, 2023; Dunne et al., 2015]. As for the equivalence, our notion of equivalence extends to iAAFs the so called "standard equivalence" between AAFs. Projectionequivalence has no corresponding notion of equivalence between AAFs in the literature cited above. As for the realizability, in [Dunne et al., 2015] the signatures of Dungean semantics have been addressed (the signature of a semantics σ identifies the sets of sets of arguments Σσ that can be "realized" as an AAF under σ, that is Σσ = {σ(F)|F is an AAF }). It is easy to see that Σad is closed under union. This implies that, since an iAAF can be seen as a set of AAFs, any iAAF always admits an equivalent AAF. However, this says nothing about the composition of this AAF (which might be of exponential size) and about a strategy for constructing it. Our result (Theorem 1) is much stronger, as we show a linear-time algorithm yielding an equivalent AAF. Under σ ∈ {st, pr}, it can be seen that Σσ is not closed under union. As a matter of fact, our proof of Theorem 2 for these semantics use counterexamples consisting of iAAFs that do not conform to the signatures. Thus, our results on the existence of linear-time transformations of iAAFs into projection equivalent AAFs go far beyond the negative results derivable by this analysis of the signatures.

7 Conclusions and FutureWork

We have addressed a gap in the literature on (incomplete) abstract argumentation by identifying the Dungean semantics under which an iAAF can be transformed into an equivalent or projection-equivalent AAF. Beyond clarifying the actual expressive contribution of allowing uncertainty over the components of an AAF, our results show that, in the cases where transformations exist, reasoning tasks for iAAFs can be reduced to reasoning over standard AAFs, thereby enabling the use of well-established argumentation machinery. At the same time, this does not undermine the role of iAAFs: even when such transformations are available, iAAFs remain a natural and human-readable formalism for the qualitative specification of uncertainty and for the compact representation of the alternative scenarios induced by incompleteness.

Future work includes several directions: extending the study to the necessary perspective; identifying heuristics to simplify transformations in specific cases; experimenting with reasoning over iAAFs by applying our transformations to AAFs and benchmarking against approaches natively designed for iAAFs [Baumeister et al., 2021; Fazzinga et al., 2020]. Finally, the implications for explainable AI are worth investigating, particularly whether explanation methods developed for standard AAFs remain interpretable when applied to AAFs generated from iAAFs.