=Paper=
{{Paper
|id=Vol-3354/paper3
|storemode=property
|title=On Properties and Complexity of Incomplete Argumentation Framework
|pdfUrl=https://ceur-ws.org/Vol-3354/paper3.pdf
|volume=Vol-3354
|authors=Gianvincenzo Alfano,Sergio Greco,Francesco Parisi,Irina Trubitsyna
|dblpUrl=https://dblp.org/rec/conf/aiia/AlfanoGPT22
}}
==On Properties and Complexity of Incomplete Argumentation Framework==
<pdf width="1500px">https://ceur-ws.org/Vol-3354/paper3.pdf</pdf>
<pre>
On Properties and Complexity of Incomplete
Argumentation Framework
Gianvincenzo Alfano, Sergio Greco, Francesco Parisi and Irina Trubitsyna
Department of Informatics, Modeling, Electronics and System Engineering (DIMES),
University of Calabria, Rende, Italy


                                      Abstract
                                      Dung’s Argumentation Framework (AF) has been extended in several directions, including the possibility
                                      of representing unquantified uncertainty about the existence of arguments and attacks. The framework
                                      resulting from such an extension is called incomplete Argumentation Framework (iAF). In this paper,
                                      we discuss three satisfaction problems recently proposed for iAF, namely totality, determinism and
                                      functionality [1], and analyze their complexity under several semantics. We then show that any iAF can be
                                      rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain.
                                      Finally, we relate iAF to probabilistic argumentation framework, where uncertainty is quantified.

                                      Keywords
                                      Formal Argumentation Theory, Uncertainty, Computational Complexity.




1. Introduction
Formal argumentation has emerged as one of the important fields in Artificial Intelligence [2, 3, 4].
In particular, Dung’s abstract Argumentation Framework (AF) is a simple yet powerful formalism
for modeling disputes between two or more agents [5]. An AF consists of a set of arguments and a
binary attack relation over the set of arguments that specifies the interactions between arguments:
intuitively, if argument 𝑎 attacks argument 𝑏, then 𝑏 is acceptable only if 𝑎 is not. Hence,
arguments are abstract entities whose status is entirely determined by the attack relation. An AF
can be seen as a directed graph, whose nodes represent arguments and edges represent attacks.
Several argumentation semantics—e.g. grounded (gr), complete (co), preferred (pr), stable
(st) [5], and semi-stable (sst) [6]—have been defined for AF, leading to the characterization of
𝜎-extensions, that intuitively correspond to the sets of arguments that can be collectively accepted
under semantics 𝜎 ∈ {gr, co, st, pr, sst}.
   Various proposals have been made to extend the Dung framework with the aim of better
modeling the knowledge to be represented [7, 8, 9, 10, 11, 12, 13, 14]. For the representation of
uncertain information, two main extensions have been proposed: incomplete AF (iAF), where
arguments and attacks may be uncertain [15, 16], and probabilistic AF (PrAF), where arguments
and attacks are associated with a probability [17, 18, 19]. In this paper we focus on iAF, but we

6𝑡ℎ Workshop on Advances In Argumentation In Artificial Intelligence (AI3 2022), November 28- December 2, 2022,
Udine, Italy
$ g.alfano@dimes.unical.it (G. Alfano); greco@dimes.unical.it (S. Greco); fparisi@dimes.unical.it (F. Parisi);
i.trubitsyna@dimes.unical.it (I. Trubitsyna)
                                    © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
 CEUR
 Workshop
 Proceedings
               http://ceur-ws.org
               ISSN 1613-0073
                                    CEUR Workshop Proceedings (CEUR-WS.org)
             e                                    e
         a       b                            a       b                             a      b
        c        d                            c       d                             c      d
Figure 1: iAF Δ of Example 1(left) and its completions Λ1 (center) and Λ2 (right).


will also study its connection with PrAF.

Example 1. Consider an iAF Δ = ⟨{a, b, c, d}, {e}, {(a, b), (b, a), (a, c), (b, d), (c, d), (d, c),
(d, a), (e, a), (e, b)}, ∅⟩ whose corresponding graph is shown in Figure 1(left), where dashed
nodes represent uncertain arguments (see Definition 1 for the formal definition). Δ describes the
following scenario. A party planner invites Alice, Bob, Carl, David, and Erik to join a party. Due
to their old rivalry (i) Alice replies that she will join the party if Bob, David and Erik do not; (ii)
Bob replies that he will join the party if Alice and Erik do not; (iii) Carl replies that he will join
the party if Alice and David do not; (iv) David replies that he will join the party if Bob and Carl
do not; and (v) Erik replies that he is not sure whether he can join the party. This situation can be
modeled by iAF Δ, where an argument x states that “(the person whose names’ initial is) x joins
the party”, and argument e =“Erik joins the party" is uncertain.                                    □

   The semantics of an iAF is given by considering all completions, i.e. AFs obtained by removing
consistent subsets of the uncertain elements, and for each completion its 𝜎-extensions under a
given semantics 𝜎. The completions of iAF Δ of Example 1 are the AF Λ1 and Λ2 shown in
Figure 1, center and right-hand side respectively, where Λ1 is the AF obtained from Δ by keeping
all the arguments and attacks, while completion Λ2 is obtained from Δ by removing the uncertain
argument e and, consistently with this, attacks (e, a) and (e, b) starting from e.
   Since most of the argumentation semantics defined for AF are non-deterministic (i.e. multiple-
status, as they prescribe more than one extension), the notions of credulous and skeptical
acceptance have been defined. Thus, given a semantics 𝜎, an argument is credulously accepted
if it occurs in at least one 𝜎-extension, whereas it is skeptically accepted if all 𝜎-extensions
contain it. Acceptance problems have been recently extended to iAF: an argument is possibly
credulously (resp. skeptically) accepted if there exists a completion where it is credulously (resp.
skeptically) accepted; an argument is necessarily credulously (resp. skeptically) accepted if for
all completions it is credulously (resp. skeptically) accepted.

Contributions. Our main contributions are as follows.

 ∙ We present three satisfaction problems for iAF called determinism (DS), totality (TS), and
  functionality (FS) (Section 3). Intuitively, totality tells us if an argument can be decided
  whatever the considered scenario (i.e. completion/world) is, while determinism tells us if we
  can safely make a decision in every scenario. Functionality combines totality and determinism
  and thus tells us if an argument can be firmly decided whatever the considered scenario is, that
  is if the information at hand is sufficient to make a decision in every possible scenario.
∙ We investigate the complexity of the problems of checking determinism, totality, and function-
 ality for general iAF and odd-cycle free iAF (a summary of the results is reported in Table 1).

∙ We show that an iAF Δ can be rewritten into an “equivalent” one Δ′ , such that for every
 𝜎-extension 𝐸 of Δ, there is a 𝜎-extension 𝐸 ′ of Δ′ coinciding with 𝐸, modulo some meta-
 arguments added in the rewriting (Section 4). Particularly, Δ′ can be of one of the following
 forms: 𝑖) only arguments or only attacks are uncertain (Δ′ is said to be an arg-iAF or att-
 iAF, respectively); or 𝑖𝑖) uncertainty is only on arguments that are not attacked by any other
 argument (Δ′ is said to be an farg-iAF). We show that an arg-iAF can be translated into an
 farg-iAF. It can be shown that the results in Table 1 also hold for these restricted forms of iAFs.

∙ Finally, we study the relationships between iAF and PrAF and relate the acceptance problems
 in iAF to probabilistic acceptance in PrAF (Section 5). We derive a PrAF corresponding a
 given iAF and show that computing the probability of acceptance of an argument is FP#P -hard
 even restricting to acyclic iAFs.

  We assume the reader is familiar with the complexity classes used in the paper [20].


2. Preliminaries
In this section we recall the (abstract) Argumentation Framework (AF) and the incomplete AF.

2.1. Argumentation Framework
An abstract Argumentation Framework (AF) [5] is a pair ⟨𝐴, 𝑅⟩, where 𝐴 is a set of arguments
and 𝑅 ⊆ 𝐴 × 𝐴 is a set of attacks.
  Given an AF Λ = ⟨𝐴, 𝑅⟩ and a set 𝑆 ⊆ 𝐴 of arguments, an argument 𝑎 ∈ 𝐴 is said to be i)
defeated w.r.t. 𝑆 iff there exists 𝑏 ∈ 𝑆 such that (𝑏, 𝑎) ∈ 𝑅, and ii) acceptable w.r.t. 𝑆 iff for
every argument 𝑏 ∈ 𝐴 with (𝑏, 𝑎) ∈ 𝑅, there is 𝑐 ∈ 𝑆 such that (𝑐, 𝑏) ∈ 𝑅. The sets of arguments
defeated and acceptable w.r.t. 𝑆 are as follows (where Λ is understood):

    • Def(𝑆) = {𝑎 ∈ 𝐴 | ∃𝑏 ∈ 𝑆 . (𝑏, 𝑎) ∈ 𝑅};
    • Acc(𝑆) = {𝑎 ∈ 𝐴 | ∀𝑏 ∈ 𝐴 . (𝑏, 𝑎) ∈ 𝑅 ⇒ 𝑏 ∈ Def(𝑆)}.

Given an AF ⟨𝐴, 𝑅⟩, a set 𝑆 ⊆ 𝐴 of arguments is said to be conflict-free iff 𝑆 ∩ Def(𝑆) = ∅.
Moreover, a set 𝑆 ⊆ 𝐴 is said to be a complete (co) extension iff it is conflict-free and 𝑆 =
Acc(𝑆). A complete extension 𝑆 ⊆ 𝐴 is said to be:

    • preferred (pr) iff it is ⊆-maximal;
    • stable (st) iff it is a total preferred extension, i.e. a preferred extension such that 𝑆 ∪
      Def(𝑆) = 𝐴;
    • semi-stable (sst) iff it is a preferred extension with a maximal set of decided elements;
    • grounded (gr) iff it is ⊆-minimal.
   In the following, if not specified otherwise, 𝜎 denotes any semantics in {gr, co, st, pr, sst}.
For any AF Λ and semantics 𝜎, 𝜎(Λ) denotes the set of 𝜎-extensions of Λ. All the above-
mentioned semantics except the stable admit at least one extension (i.e. 𝜎(Λ) ̸= ∅), and the
grounded admits exactly one extension (i.e. |gr(Λ)| = 1) [5, 6]. The grounded semantics is
called deterministic (or unique status), whereas the other semantics are called non-deterministic
(or multiple status). The stable semantics is said to be total as each argument belongs to either
𝐸 or Def(𝐸) (i.e. it is either true or false) for every extension 𝐸. For any AF Λ, it holds that
st(Λ) ⊆ sst(Λ) ⊆ pr(Λ) ⊆ co(Λ), and gr(Λ) ⊆ co(Λ). An AF is acyclic (resp. odd-cycle
free) if the associated graph is acyclic (resp. odd-cycle free). For acyclic AFs all the considered
semantics coincide.
   In the following we consider the acceptability of argument literals (or simply literals). A
literal is either an argument 𝑎 or its negation ¬𝑎. A set of literals 𝑆 is said to be consistent if it
does not contain two literals 𝑎 and ¬𝑎. We use ¬𝑆 to denote the set {¬𝑎 | 𝑎 ∈ 𝑆}, and 𝑆 * to
denote 𝑆 ∪ ¬𝑆. To deal with literals, we define the notion of fulfillment of an extension. Given
an AF Λ = ⟨𝐴, 𝑅⟩ and an extension 𝐸 for it, the fulfillment of 𝐸 is 𝐸 ∪ ¬Def(𝐸). Clearly, the
fulfillment of an extension is a consistent set of literals. Herein, arguments in 𝐸 are represented
as positive literals (i.e. interpreted as true), while arguments defeated by 𝐸 are represented as
negative literals (i.e. interpreted as false). In the rest of the paper, with a little abuse of notation,
whenever we refer to an extension we mean its fulfillment.
   For any AF Λ = ⟨𝐴, 𝑅⟩, semantics 𝜎, and literal 𝑎 ∈ 𝐴* , we say that 𝑎 is credulously (resp.
skeptically) accepted (under semantics 𝜎), denoted as 𝐶𝐴𝜎 (Λ, 𝑎) (resp. 𝑆𝐴𝜎 (Λ, 𝑎)) if 𝑎 belongs
to at least a (resp. every) 𝜎-extension of Λ. We use CA𝜎 (resp. SA𝜎 ), or simply CA (resp. SA)
whenever 𝜎 is understood, to denote the credulous (resp. skeptical) acceptance problem, that is,
the problem of deciding whether a literal is credulously (resp. skeptically) accepted. Clearly,
for the grounded semantics, which has exactly one extension, these problems are identical (i.e.
CAgr ≡ SAgr ).

Example 2. Consider the AF Λ = ⟨{a, b, c, d}, {(a, b), (b, a), (a, c), (b, c), (c, d), (d, c)}⟩.
Λ has 4 complete extensions: 𝐸0 = ∅, 𝐸1 = {a, ¬b, ¬c, d}, 𝐸2 = {¬a, b, ¬c, d} and 𝐸3 =
{¬c, d}. That is, co(Λ) = {𝐸0 , 𝐸1 , 𝐸2 , 𝐸3 }. 𝐸0 is the grounded extension, 𝐸1 and 𝐸2 are stable
(preferred and semi-stable) extensions. Thus, a, b, d, as well as ¬a, ¬b, ¬c, are credulously
accepted for all semantics except the grounded; only d and ¬c are skeptically accepted for stable,
preferred and semi-stable semantics.                                                            □

2.2. Incomplete Argumentation Framework
We now recall the incomplete Argumentation Framework (iAF) [15].

Definition 1 (Incomplete AF). An incomplete Argumentation Framework (iAF) is a tuple Δ =
⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩, where 𝐴 and 𝐵 are disjoint sets of arguments, and 𝑅 and 𝑇 are disjoint sets of
attacks between arguments in 𝐴 ∪ 𝐵. Arguments in 𝐴 and attacks in 𝑅 are said to be certain,
while arguments in 𝐵 and attacks in 𝑇 are said to be uncertain.

  Certain arguments in 𝐴 are definitely known to exist, while uncertain arguments in 𝐵 are not
known for sure: they may occur or may not. Analogously, certain attacks in 𝑅 are definitely
known to exist if both the incident arguments exist, while for uncertain attacks in 𝑇 it is not
known for sure if they hold, even if both the incident arguments exist.
  An iAF compactly represents alternative AF scenarios, or possible worlds, called completions.
Definition 2 (Completion). A completion for an iAF Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ is an AF Λ = ⟨𝐴′ , 𝑅′ ⟩
where 𝐴 ⊆ 𝐴′ ⊆ 𝐴 ∪ 𝐵 and 𝑅 ∩ (𝐴′ × 𝐴′ ) ⊆ 𝑅′ ⊆ (𝑅 ∪ 𝑇 ) ∩ (𝐴′ × 𝐴′ ).
   The set of completions of Δ is denoted by 𝑐𝑜𝑚𝑝(Δ).
   An iAF ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ is acyclic (resp. odd-cycle free) iff the AF ⟨𝐴 ∪ 𝐵, 𝑅 ∪ 𝑇 ⟩ is acyclic
(resp. odd-cycle free).
   To define acceptability and properties satisfaction of literals for iAFs, we refine the definition of
fulfillment of extensions. Given an iAF Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ and an extension 𝐸 for a completion
Λ = ⟨𝐴′ , 𝑅′ ⟩ of Δ, the fulfillment of 𝐸 is 𝐸 ∪ ¬𝐷𝑒𝑓 (𝐸) ∪ ¬(𝐵 ∖ 𝐴′ ). Herein, arguments in 𝐸
are represented as positive literals (i.e. interpreted as true), while arguments attacked by 𝐸 as
well as uncertain arguments not occurring in Λ are represented as negative literals (i.e. interpreted
as false).
Example 3. The only preferred extension of the completion Λ2 for the iAF Δ of Example 1 is
{b, c}, whose fulfillment is {¬a, b, c, ¬d, ¬e}.                                        □

Acceptance problems. Credulous and skeptical acceptance for iAF have been recently
proposed in [21], where the goal, i.e. the element for which acceptance is checked, is an argument.
As we focus on fulfillment of extensions, our goal is a literal.
Definition 3 (Possible/Necessary Credulous/Skeptical Acceptance). Let Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ be
an iAF and 𝜎 ∈ {gr, co, st, pr, sst}. Then, a literal 𝑔 ∈ 𝐴* ∪ 𝐵 * is said to be:
   1. possibly credulously accepted under 𝜎, denoted as 𝑃𝐶𝐴𝜎 (Δ, 𝑔), iff there exists a comple-
      tion Λ of Δ and a 𝜎-extension 𝐸 of Λ such that 𝑔 ∈ 𝐸;
   2. possibly skeptically accepted under 𝜎, denoted as 𝑃𝑆𝐴𝜎 (Δ, 𝑔), iff there exists a completion
      Λ of Δ such that 𝑔 occurs in every 𝜎-extension of Λ;
   3. necessarily credulously accepted under 𝜎, denoted as 𝑁𝐶𝐴𝜎 (Δ, 𝑔), iff for every completion
      Λ of Δ, there exists a 𝜎-extension 𝐸 of Λ such that 𝑔 ∈ 𝐸;
   4. necessarily skeptically accepted under 𝜎, denoted as 𝑁𝑆𝐴𝜎 (Δ, 𝑔), iff for every completion
      Λ of Δ, 𝑔 occurs in every 𝜎-extension of Λ.
   We use PCA𝜎 (resp. PSA𝜎 , NCA𝜎 , NSA𝜎 ), or simply PCA (resp. PSA, NCA, NSA) whenever
𝜎 is understood, to denote the problem of deciding acceptance according to Item 1 (resp. 2, 3, and
4) of Definition 3. For the grounded semantics we have PCAgr ≡ PSAgr and NCAgr ≡ NSAgr .
Example 4. Consider the iAF Δ = ⟨{a, b, d}, {c}, {(a, b), (b, a)}, ∅⟩ shown in Figure 2 (left),
where bidirectional arrows represent mutual attacks. Δ has 2 completions: Λ1 = ⟨{a, b, d},
{(a, b), (b, a)}⟩ and Λ2 = ⟨{a, b, c, d}, {(a, b), (b, a)}⟩ (see Figure 2). Under semantics 𝜎 ∈
                                            ′                        ′′
{st, pr, sst}, Λ1 has the two extensions 𝐸1 = {a, ¬b, ¬c, d} and 𝐸1 = {¬a, b, ¬c, d}; moreover,
                            ′                       ′′
Λ2 has the two extensions 𝐸2 = {a, ¬b, c, d} and 𝐸2 = {¬a, b, c, d}. Thus, a, b, c, d, ¬a, ¬b, ¬c
satisfy PCA; c, d, ¬c satisfy PSA; a, b, d,¬a,¬b satisfy NCA and only d satisfies NSA.          □
                   a      b                   a      b                a      b

                   c      d                          d                c      d

Figure 2: iAF Δ of Example 4 (left) and its completions Λ1 (center) and Λ2 (right).


3. Totality, Determinism and Functionality
In this section we present three satisfaction problems for iAF called determinism (DS), totality
(TS), and functionality (FS) that have been recently proposed in [1]. Informally, an argument
is said to be deterministic if in every completion all extensions assign the same status (either
accepted, rejected, or undecided) to it. Moreover, an argument is said to be total, if for all
extensions it is either accepted or rejected (i.e. it is never undecided). Totality is inspired by
the criterion leading to stable semantics [5]. In fact, it requires the same property as the stable
semantics but for a given goal argument (instead of all arguments). When both totality and
determinism hold for a given argument, we say that it is functional. Thus, for iAF, totality tells
us if an argument can be decided whatever the considered scenario (i.e. completion/world) is,
while determinism tells us if we can safely make a decision in every scenario (completion).
Functionality combines totality and determinism and thus tells us if an argument can be firmly
decided whatever the considered scenario is, as shown in the following example.

Example 5. Continuing with Example 1, suppose the party planner is interested to know if, what-
ever Erik decides to do, he has sufficient information to decide whether or not Alice (resp. Bob)
joins the party. The preferred (stable/semi-stable) extensions of Λ1 and Λ2 are {{c, e}, {d, e}}
and {{b, c}}, respectively. As a and b are functional, the party planner concludes that a decision
on the fact that Alice (resp. Bob) joins or not the party can be taken in both the scenarios that
Erik joins or not the party.
   Note that such questions cannot be answered by possible/necessary credulous/skeptical accep-
tance. In fact, a is functional but not possible credulously accepted, and b is functional but not
necessary skeptically accepted.                                                                 □

Definition 4 (Total, deterministic, functional literals). Let Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ be an iAF, 𝜎 ∈
{gr, co, st, pr, sst}, and 𝑔 ∈ 𝐴* ∪ 𝐵 * a goal literal. We say that 𝑔 is:

    • total under 𝜎, denoted as 𝑇 𝑆𝜎 (Δ, 𝑔), if for each Λ ∈ 𝑐𝑜𝑚𝑝(Δ), i) 𝜎(Λ) ̸= ∅ and ii) for
      each 𝐸 ∈ 𝜎(Λ), either 𝑔 ∈ 𝐸 or ¬𝑔 ∈ 𝐸;
    • deterministic under 𝜎, denoted as 𝐷𝑆𝜎 (Δ, 𝑔), if for each Λ ∈ 𝑐𝑜𝑚𝑝(Δ), i) 𝜎(Λ) ̸= ∅,
      and ii) either 𝑆𝐴𝜎 (Λ, 𝑔) or 𝑆𝐴𝜎 (Λ, ¬𝑔) or (¬𝐶𝐴𝜎 (Λ, 𝑔) ∧ ¬𝐶𝐴𝜎 (Λ, ¬𝑔));
    • functional under 𝜎, denoted as 𝐹𝑆𝜎 (Δ, 𝑔), if 𝑔 is total and deterministic under 𝜎, that is,
      for each Λ ∈ 𝑐𝑜𝑚𝑝(Δ), i) 𝜎(Λ) ̸= ∅ and ii) either 𝑆𝐴𝜎 (Λ, 𝑔) or 𝑆𝐴𝜎 (Λ, ¬𝑔).

  The next result immediately derives from definitions.

Fact 1. Let Δ be an iAF, 𝜎 ∈ {gr, co, st, pr, sst} and 𝑔 a literal. We have that i) 𝑇 𝑆 𝜎 (Δ, 𝑔)
≡ 𝑇 𝑆 𝜎 (Δ, ¬𝑔), ii) 𝐷𝑆 𝜎 (Δ, 𝑔) ≡ 𝐷𝑆 𝜎 (Δ, ¬𝑔), and iii) 𝐹 𝑆 𝜎 (Δ, 𝑔) ≡ 𝐹 𝑆 𝜎 (Δ, ¬𝑔) hold.
                                                                                          1
      d                                                     d                        d2
  a       b c                 a     b c                 a       b c                 a b c
Figure 3: iAF Δ of Example 6 (left), its completions Λ1 and Λ2 (center), and its derived PrAF Δ𝑝
(right).


Example 6. Consider the iAF Δ = ⟨𝐴 = {a, b, c}, 𝐵 = {d}, 𝑅 = {(a, b), (b, a), (b, c),
(c, c), (d, a), (d, b)}, 𝑇 = ∅⟩ reported in Figure 3, left side. Δ has two completions Λ1 = ⟨𝐴,
𝑅 ∖ {(d, a), (d, b)}⟩ and Λ2 = ⟨𝐴 ∪ 𝐵, 𝑅⟩, also shown in Figure 3 (center). For Λ1 there are three
complete extensions (recall that we refer to the fulfillments): 𝐸0 = {¬d}, 𝐸1 = {a, ¬b, ¬d} and
𝐸2 = {¬a, b, ¬c, ¬d}. The grounded extension is 𝐸0 , while 𝐸1 is preferred, and 𝐸2 is stable,
preferred, and semi-stable. For Λ2 there is only one complete extension 𝐸3 = {¬a, ¬b, d}, which
is grounded, preferred, and semi-stable. The goal b is 𝑖) total only for semantics pr and sst (it is
not total for st as Λ2 does not have stable extensions) and 𝑖𝑖) deterministic for semantics gr, st
and sst (it is not deterministic for pr as the two preferred extensions, 𝐸1 and 𝐸2 , of Λ1 are such
that 𝐸1 contains ¬b while 𝐸2 contains b). Thus, b is functional for sst only.                    □

  We use TS𝜎 (resp. DS𝜎 , FS𝜎 ), or simply FS (resp. TS, DS) whenever 𝜎 is understood, to
denote the problem of deciding whether a literal is total (resp. deterministic, functional).
  The next proposition provides conditions under which unattacked arguments are functional.

Proposition 1. For any iAF Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ and unattacked argument 𝑔 ∈ 𝐴 ∪ 𝐵, it holds
that 𝑔 is functional i) under semantics 𝜎 ∈ {gr, co, pr, sst}, and ii) under semantics 𝜎 = st if
Δ is odd-cycle free.

   Thus, under semantics 𝜎 ∈ {co, gr, pr, sst}, every unattacked argument is total and deter-
ministic. However, this does not hold for general iAFs under stable semantics, as there could be
completions prescribing no extensions.
   We conclude this section by providing the complexity of the problems of deciding whether a
literal is total, deterministic, and functional for the case of general and odd-cycle free iAFs.

Theorem 1. For general/odd-cycle free iAFs, the complexity results of Table 1 hold.

   The odd-cycle free property guarantees that, except for the grounded and complete seman-
tics, the complexity of checking determinism and functionality decreases by one level of the
polynomial hierarchy whereas checking totality becomes trivial.


4. Equivalent Forms of iAFs
In this section we show that iAFs can be rewritten into equivalent iAFs where uncertainty is
restricted to either attacks or (unattacked) arguments.

Definition 5. An iAF Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ is said to be argument-incomplete (arg-iAF for short) if
𝑇 = ∅, whereas it is said to be attack-incomplete (att-iAF for short) if 𝐵 = ∅.
                                   (General) iAF           odd-cycle free iAF
                      𝜎       TS       DS        FS      TS      DS          FS
                      gr   coNP-c trivial coNP-c coNP-c           trivial   coNP-c
                      co   coNP-c coNP-c coNP-c coNP-c           coNP-c     coNP-c
                      st    Π𝑝2 -c Π𝑝2 -c  Π𝑝2 -c trivial        coNP-c     coNP-c
                              𝑝      𝑝
                      pr    Π2 -c  Π2 -c   Π𝑝2 -c trivial        coNP-c     coNP-c
                     sst    Π𝑝2 -c Π𝑝2 -c  Π𝑝2 -c trivial        coNP-c     coNP-c
Table 1
Complexity of totality (TS), determinism (DS), and functionality (FS) problems for iAFs. For any
complexity class 𝒞, 𝒞-c means C-complete.


    Given an iAF Δ, we denote by 𝑎𝑟𝑔(Δ) the arg-iAF derived from Δ by replacing every
uncertain attack (𝑎, 𝑏) with the certain attacks (𝑎, 𝛼𝑎𝑏 ), (𝛼𝑎𝑏 , 𝛽𝑎𝑏 ), (𝛽𝑎𝑏 , 𝑏), where 𝛼𝑎𝑏 (resp. 𝛽𝑎𝑏 )
is a fresh certain (resp. uncertain) argument.
    Analogously, we denote by 𝑎𝑡𝑡(Δ) the att-iAF derived from Δ as follows: for each uncertain
argument 𝑏, make 𝑏 certain and add an uncertain attack (𝛼, 𝑏), where 𝛼 is a fresh certain argument—
it is sufficient to add only one fresh argument 𝛼.

Example 7. Consider the iAF Δ = ⟨{b, c}, {a}, {(a, b), (b, a)}, {(b, c)}⟩ shown in Figure 4
(left). The arg-iAF derived from Δ is Δ′ = ⟨{b, c, 𝛼bc }, {a, 𝛽bc }, {(a, b), (b, a), (b, 𝛼bc ), (𝛼bc ,
𝛽bc ), (𝛽bc , c)}, ∅⟩ shown in Figure 4 (center), whereas the att-iAF derived from Δ is Δ′′ =
⟨{b, c, a, 𝛼}, ∅, {(a, b), (b, a)}, {(b, c), (𝛼, a)}⟩ shown in Figure 4 (right).                    □

  The transformations described above to eliminate uncertain attacks/arguments are inspired by
those to eliminate attacks/arguments with probability less than 1 in probabilistic AF [22].
  We now introduce a special class of arg-iAFs.

Definition 6. An arg-iAF Δ = ⟨𝐴, 𝐵, 𝑅, ∅⟩ is said to be fact-uncertain (farg-iAF) iff ∀(𝑎, 𝑏) ∈ 𝑅,
𝑏 ̸∈ 𝐵.

   Observe that the iAF of Example 1 is an farg-iAF.
   Given an arg-iAF Δ, 𝑓𝑎𝑟𝑔(Δ) denotes the farg-iAF derived from Δ as follows: for each
uncertain argument 𝑏 which is attacked in Δ, make 𝑏 certain and add the attacks (𝑏𝑢 , 𝑏𝑐 ), (𝑏𝑐 , 𝑏),
where 𝑏𝑐 (resp. 𝑏𝑢 ) is a fresh certain (resp. uncertain) argument. With a little abuse of notation,
for any iAF Δ we use 𝑓𝑎𝑟𝑔(Δ) to denote 𝑓𝑎𝑟𝑔(𝑎𝑟𝑔(Δ)).

Example 8. Considering the iAF Δ of Example 7, the derived farg-iAF 𝑓 𝑎𝑟𝑔(Δ) is shown in
Figure 5. The completions of 𝑓 𝑎𝑟𝑔(Δ) are obtained by selecting all subsets of the set {a𝑢 , 𝛽bc
                                                                                              𝑢 }

of uncertain arguments.                                                                        □

  Given an iAF Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩, let 𝜙 ∈ {𝑎𝑟𝑔, 𝑎𝑡𝑡, 𝑓 𝑎𝑟𝑔}, for any Λ′ = ⟨𝐴′ , 𝑅′ ⟩ ∈
𝑐𝑜𝑚𝑝(𝜙(Δ)), 𝑎𝑓Δ (Λ′ ) denotes the AF Λ′′ = ⟨𝐴′′ , 𝑅′′ ⟩ ∈ 𝑐𝑜𝑚𝑝(Δ) with:

    • 𝐴′′ = 𝐴 ∪ ((𝐵 ∩ 𝐴′ ) ∖ {𝑎 | (𝛼, 𝑎) ∈ 𝑅′ ∨ 𝑎𝑢 ̸∈ 𝐴′ }), and
    • 𝑅′′ = (𝑅∩(𝐴′′ ×𝐴′′ )) ∪ ((𝑇 ∩(𝐴′′ ×𝐴′′ ))∖{(𝑎, 𝑏) | (𝛽𝑎𝑏 ̸∈ 𝐴′ )∨(𝛽𝑎𝑏
                                                                         𝑐 ∈ 𝐴′ ∧𝛽 𝑢 ̸∈ 𝐴′ )}.
                                                                                  𝑎𝑏
 a       b       c           a        b        αbc         βbc         c         α   a   b      c
Figure 4: iAF Δ of Example 7 (left), arg-iAF Δ′ derived from Δ (center), and att-iAF Δ′′ derived
from Δ (right).


                                 a        b          αbc         βbc        c

                                                                  c         u
                                 ac       au                     βbc       βbc

Figure 5: Farg-iAF of Example 8.


   Herein, the set {𝑎 | (𝛼, 𝑎) ∈ 𝑅′ ∨ 𝑎𝑢 ̸∈ 𝐴′ } is used to avoid considering arguments either (𝑖)
attacked by 𝛼 in 𝑐𝑜𝑚𝑝(𝑎𝑡𝑡(Δ)) or (𝑖𝑖) always false in 𝑐𝑜𝑚𝑝(𝑓 𝑎𝑟𝑔(Δ)) as 𝑎𝑢 ̸∈ 𝐴′ . Analogously,
{(𝑎, 𝑏) | (𝛽𝑎𝑏 ̸∈ 𝐴′ ) ∨ (𝛽𝑎𝑏
                           𝑐 ∈ 𝐴′ ∧ 𝛽 𝑢 ̸∈ 𝐴′ )} is used to avoid considering uncertain attacks
                                       𝑎𝑏
that are chosen to not occur in either (𝑖) 𝑐𝑜𝑚𝑝(𝑎𝑟𝑔(Δ)), as 𝛽𝑎𝑏 ̸∈ 𝐴′ , or (𝑖𝑖) 𝑐𝑜𝑚𝑝(𝑓 𝑎𝑟𝑔(Δ))
      𝑐 ∈ 𝐴′ ∧ 𝛽 𝑢 ̸∈ 𝐴′ ).
as (𝛽𝑎𝑏           𝑎𝑏

Example 9. Consider the iAF Δ of Example 7 and its farg-iAF 𝑓𝑎𝑟𝑔(Δ) of Example 8. For
Λ = ⟨𝐴 ∪ {au }, 𝑅 ∖ {(𝛽bcu , 𝛽 c )}⟩ ∈ 𝑐𝑜𝑚𝑝(𝑓 𝑎𝑟𝑔(Δ)), containing the uncertain argument au but
                              bc
     u
not 𝛽bc , 𝑎𝑓Δ (Λ) = ⟨{a, b, c}, {(a, b), (b, a)}⟩ ∈ 𝑐𝑜𝑚𝑝(Δ) that contains the uncertain argument
a and does not contain the uncertain attack (b, c).                                           □

Lemma 1. For any iAF Δ and 𝜙 ∈ {𝑎𝑟𝑔, 𝑎𝑡𝑡, 𝑓𝑎𝑟𝑔}, 𝑎𝑓Δ : 𝑐𝑜𝑚𝑝(𝜙(Δ)) → 𝑐𝑜𝑚𝑝(Δ) is a
surjective function.

  The next theorem states the ‘equivalence’ between iAFs and the iAFs derived by applying the
previous mappings.

Theorem 2. Let Δ = ⟨𝐴, 𝐵, 𝑅, 𝑇 ⟩ be an iAF, 𝜎 ∈ {gr, co, st, pr, sst}, and 𝜙 ∈ {𝑎𝑟𝑔, 𝑎𝑡𝑡, 𝑓𝑎𝑟𝑔}.
Then, 𝑐𝑜𝑚𝑝(Δ) = {𝑎𝑓Δ (Λ) | Λ ∈ 𝑐𝑜𝑚𝑝(𝜙(Δ))}, and
𝜎(Λ′ ) = {𝐸 ∩ (𝐴 ∪ 𝐵) | Λ ∈ 𝑐𝑜𝑚𝑝(𝜙(Δ)) ∧ Λ′ = 𝑎𝑓Δ (Λ) ∧ 𝐸 ∈ 𝜎(Λ)} ∀Λ′ ∈ 𝑐𝑜𝑚𝑝(Δ).

   Thus, any iAF Δ is equivalent to an arg-iAF (resp. farg-iAF, att-iAF) Δ′ in the sense that
there is mapping between the completions of 𝜙(Δ) and the completions of Δ, and for any pair of
AFs for which the mapping holds, the two AFs have the same (modulo arguments added in the
rewriting) set of 𝜎-extensions, for 𝜎 ∈ {gr, co, st, pr, sst}. This result entails that arg-iAFs
(resp. farg-iAF, att-iAF) have the same expressivity of general iAFs, though arg-iAFs (resp. farg-
iAF, att-iAF) have a simpler structure. The results of Theorem 2 with those of Theorem 1 entail
that the complexity results for the problems of checking totality, determinism, and functionality
for iAFs in Table 1 also hold for att-iAF, arg-iAF and f-arg-iAF.
   Finally, as shown next, the restricted forms of iAF allow to establish a tight connection between
iAF and Probabilistic AF, and simplify the presentation as it suffices to focus on arg-iAF and an
analogous form of restricted Probabilistic AF where only arguments are uncertain.
5. Relationship with Probabilistic Acceptance
Probabilistic Argumentation Framework (PrAF) has been investigated in the recent years [18, 23,
24, 25, 26, 27, 28]. Incomplete AF is tightly connected to PrAF, as every completion of an iAF
corresponds to a so-called possible world in PrAF. Here we highlight this relationship and relate
acceptance problems in iAF, to probabilistic acceptance in PrAF.
   W.l.o.g. we focus on PrAF where only arguments are uncertain (and attacks are certain, i.e.
their probability is 1), since as shown in [22] a PrAF with probabilities on arguments and attacks
can be transformed into an equivalent PrAF where only arguments may have probability lower
than 1 (that is, the probability of arguments is greater than 0 and lower than or equal to 1, while
that of attacks is 1). Here, an argument 𝑎 ∈ 𝐴 is viewed as a probabilistic event that is independent
from events associated with other arguments 𝑏 ∈ 𝐴 (with 𝑏 ̸= 𝑎).
   Analogously to what is said above, since any iAF is equivalent to an arg-iAF, w.l.o.g. in the
following we consider arg-iAFs and denote them by triples ⟨𝐴, 𝐵, 𝑅⟩ (i.e. omitting the empty set
of uncertain attacks).
Definition 7 (PrAF). A Probabilistic Argumentation Framework (PrAF) is a triple ⟨𝐴, 𝑅, 𝑃 ⟩
where ⟨𝐴, 𝑅⟩ is an AF, and 𝑃 is a function assigning a non-zero probability value to every
argument in 𝐴, that is, 𝑃 : 𝐴 → (0, 1].
   Observe that assigning probability equal to 0 to arguments is useless. Basically, the value
assigned by 𝑃 to any argument 𝑎 represents the probability that 𝑎 actually occurs. Moreover,
every attack (𝑎, 𝑏) occurs with conditional probability 1, that is, 𝑎 attacks 𝑏 whenever both 𝑎 and
𝑏 occur.
   The meaning of a PrAF is given in terms of possible worlds. Given a PrAF ∇ = ⟨𝐴, 𝑅, 𝑃 ⟩, a
possible world of ∇ is an AF Λ = ⟨𝐴′ , 𝑅′ ⟩ such that 𝐴′ ⊆ 𝐴 and 𝑅′ = 𝑅 ∩ (𝐴′ × 𝐴′ ). We use
𝑝𝑤(∇) to denote the set of all possible worlds of ∇. An interpretation for a PrAF ∇ = ⟨𝐴, 𝑅, 𝑃 ⟩
is a probability distribution function (PDF) 𝐼 over the set 𝑝𝑤(∇) of the possible worlds. Each
Λ = ⟨𝐴′ , 𝑅′ ⟩ ∈ 𝑝𝑤(∇) is assigned by 𝐼 probability 𝐼(Λ), where:
                                        ∏︀          ∏︀
                             𝐼(Λ) =        𝑃 (𝑎) ·        (1 − 𝑃 (𝑎)).
                                       𝑎∈𝐴         𝑎∈𝐴∖𝐴′

  We now define a PrAF Δ𝑝 encoding an iAF Δ.
Definition 8 (Derived PrAF). Given an arg-iAF Δ = ⟨𝐴, 𝐵, 𝑅⟩, the PrAF derived from Δ is
Δ𝑝 = ⟨𝐴∪𝐵, 𝑅, 𝑃 ⟩, where 𝑃 : 𝐴 ∪ 𝐵 → {1/2, 1} with 𝑃 (𝑎) = 1 for 𝑎 ∈ 𝐴 and 𝑃 (𝑏) = 1/2
for 𝑏 ∈ 𝐵.
   It is easy to check that, given an arg-iAF Δ = ⟨𝐴, 𝐵, 𝑅⟩, for every Λ ∈ 𝑝𝑤(Δ𝑝 ), 𝐼(Λ) is
                       1
equal to either 0 or 2|𝐵| . As stated next, non-zero probability possible worlds of derived PrAF
  𝑝
Δ one-to-one correspond to completions of Δ.
Proposition 2. For any arg-iAF Δ, 𝑐𝑜𝑚𝑝(Δ) = {Λ | Λ ∈ 𝑝𝑤(Δ𝑝 ) ∧ 𝐼(Λ) > 0}.
Example 10. Consider the arg-iAF Δ of Example 6 (see Figure 3). The derived PrAF Δ𝑝 =
⟨𝐴 ∪ 𝐵, 𝑅, 𝑃 ⟩, with 𝑃 (𝑥) = 1 for 𝑥 ∈ {a, b, c} and 𝑃 (d) = 1/2, is shown in Figure 3 (right).
There are only two possible worlds with probability greater than 0: Λ1 = ⟨𝐴, 𝑅 ∖ {(d, a), (d, b)}⟩
and Λ2 = ⟨𝐴 ∪ 𝐵, 𝑅⟩ with 𝐼(Λ1 ) = 𝐼(Λ2 ) = 1/2.                                                 □
   Given a PrAF, the probabilistic acceptance provides the probability that a given goal is
accepted [28]. Specifically, given a PrAF ∇, a semantics 𝜎, and a goal literal 𝑔, the probability
                                    ∑︀associating to every extension 𝐸 ∈ 𝜎(Λ), with Λ ∈ 𝑝𝑤(∇),
that 𝑔 is accepted can be computed by
a probability 𝑃 𝑟(𝐸, Λ, 𝜎) so that 𝐸∈𝜎(Λ) 𝑃 𝑟(𝐸, Λ, 𝜎) = 1 (the sum of the probabilities of
the 𝜎-extensions of Λ is equal to 1). More in detail, a PrAF Δ𝑝 derived from a given iAF Δ is
considered, and a PDF over the set 𝜎(Λ) of the extensions of each possible world Λ ∈ 𝑝𝑤(Δ𝑝 ) is
required. This means that the condition 𝜎(Λ) ̸= ∅ must hold. To ensure this, in the rest of this
section, if not specified otherwise, whenever we write semantics 𝜎 and (arg-)iAF Δ we mean
that either i) 𝜎 ∈ {gr, co, pr, sst} and Δ is an (arg-)iAF without restrictions or ii) 𝜎 = st
and Δ is odd-cycle free; in the latter case, the existence of an extension is guaranteed since
st(Λ) = sst(Λ) = pr(Λ) ̸= ∅ for all Λ ∈ 𝑝𝑤(Δ𝑝 ).

Definition 9 (Probabilistic Acceptance). Given an arg-iAF Δ = ⟨𝐴, 𝐵, 𝑅⟩ and a literal 𝑔 ∈
𝐴* ∪ 𝐵 * , the probability 𝑃 𝑟𝐴𝜎Δ (𝑔) that 𝑔 is acceptable w.r.t. semantics 𝜎 is:
                                              ∑︁
                         𝑃 𝑟𝐴𝜎Δ (𝑔) =                  𝐼(Λ) · 𝑃 𝑟(𝐸, Λ, 𝜎)
                                        Λ ∈ 𝑝𝑤(Δ𝑝 )∧
                                       𝐸 ∈ 𝜎(Λ) ∧ 𝑔 ∈ 𝐸


where 𝑃 𝑟(·, Λ, 𝜎) is a PDF over the set 𝜎(Λ).

   Hereafter, we consider the uniform PDF assigning to every 𝜎-extension of Λ the same proba-
bility (1/𝑛 where 𝑛 is the number of 𝜎-extensions). Our results still hold for other PDFs over
𝜎(Λ), such as that used in [28].
   Given an arg-iAF Δ and a literal 𝑔, the problem of computing the value 𝑃 𝑟𝐴𝜎Δ (𝑔) (under a
given semantics 𝜎) is denoted by PrA𝜎 , or simply PrA whenever 𝜎 is understood. We recall that
PrA𝜎 is defined after choosing an arbitrary but fixed PDF over the set of extensions. As stated
next, PrA𝜎 is FP#P -hard, regardless of the chosen PDF and semantics 𝜎.

Theorem 3. PrA𝜎 is FP#P -hard, even for acyclic arg-iAF and for any chosen PDF.

  We observe that, consistently with our intuition, the complexity of the probabilistic counterpart
of the verification problem, that is computing the probability that a set of arguments is a 𝜎-
extension for a PrAF [24], is not harder than that of PrA𝜎 which focuses on acceptance.
  The following propositions highlight the relations between iAFs and PrAFs (with uniform PDF
over extensions).

Proposition 3. For any goal 𝑔, we have that: 𝑃𝐶𝐴𝜎 (Δ, 𝑔) is false iff 𝑃 𝑟𝐴𝜎Δ𝑝 (𝑔) = 0; and
𝑁𝑆𝐴𝜎 (Δ, 𝑔) is true iff 𝑃 𝑟𝐴𝜎Δ𝑝 (𝑔) = 1.

   The connection between iAF and PrAF is also investigated in [16], where the PrAF associated
to an iAF assigns a probability in (0, 1) to each uncertain argument. Moreover, PCA, PSA,
NCA, and NSA are related to the concept of probabilistic credulous/skeptical acceptance [29],
which is different from that of probabilistic acceptance of Definition 9. Indeed, the probability
that an argument 𝑔 is credulously (resp. skeptically) accepted is the sum of the probabilities of
the possible worlds where 𝑔 is credulously (resp. skeptically) accepted, according to a given
semantics 𝜎. Hence, the probability of a world Λ is added to the summation iff 𝑔 belongs to at
least one (resp. every) 𝜎-extension of Λ. In contrast, with the aim of offering a more granular
approach, Definition 9 uses the probabilities assigned to 𝜎-extensions by the PDF 𝑃 𝑟(·, Λ, 𝜎).
For instance, taking the PrAF Δ𝑝 of Example 10 (see Figure 3), under the complete semantics the
probabilistic skeptical (resp. credulous) acceptance of b is 0 (resp. 1/2), while 𝑃 𝑟𝐴co
                                                                                       Δ𝑝 (b) = 1/6
as b belongs to one of three extensions of one of the two worlds (see Example 11 below).
Although the conditions of Proposition 3 are similar to those identified in [16], they refer to
different notions of probabilistic acceptance. In fact, while probabilistic skeptical and credulous
acceptance define an interval, Definition 9 provides a precise value in that interval.
   The next proposition considers acyclic arg-iAFs, a subclass of odd-cycle free iAFs.

Proposition 4. Let Δ = ⟨𝐴, 𝐵, 𝑅⟩ be an acyclic arg-iAF and 𝑔 a goal. It holds that:
∙ 𝑃𝑆𝐴𝜎 (Δ, 𝑔) ≡ 𝑃𝐶𝐴𝜎 (Δ, 𝑔) and 𝑁𝑆𝐴𝜎 (Δ, 𝑔) ≡ 𝑁𝐶𝐴𝜎 (Δ, 𝑔);
                                          1
∙ 𝑃𝑆𝐴𝜎 (Δ, 𝑔) is true iff 𝑃 𝑟𝐴𝜎Δ𝑝 (𝑔) ≥ 2|𝐵| ;
                                               1
∙ 𝑁𝑆𝐴𝜎 (Δ, 𝑔) is false iff 𝑃 𝑟𝐴𝜎Δ𝑝 (𝑔) ≤ 1 − 2|𝐵| .

  Our last result relates the satisfaction of properties (e.g. totality) to probabilistic acceptance.
                                     𝜎           𝜎
        ∑︀ A goal 𝑔 is total iff 𝑃 𝑟𝐴Δ (𝑔) + 𝑃 𝑟𝐴Δ (¬𝑔) = 1; and deterministic iff ∀Λ ∈
Theorem 4.
𝑐𝑜𝑚𝑝(Δ), 𝑃 𝑟(𝐸, Λ, 𝜎) = 1, where either:
            𝛼
(𝑖) 𝛼 = 𝐸 ∈ 𝜎(Λ) ∧ 𝑔 ∈ 𝐸        or
(𝑖𝑖) 𝛼 = 𝐸 ∈ 𝜎(Λ) ∧ ¬𝑔 ∈ 𝐸         or
(𝑖𝑖𝑖) 𝛼 = 𝐸 ∈ 𝜎(Λ) ∧ (𝑔 ̸∈ 𝐸 ∧ ¬𝑔 ̸∈ 𝐸).

Example 11. Consider again the iAF of Example 6. Assuming a uniform distribution for the
probabilities of extensions, the probabilistic acceptance of literals is as reported in the following
table, where a grey cell means that the literal of the cell’s column is total, under the semantics of
the cell’s row.
                          a      ¬a      b       ¬b    c   ¬c      d      ¬d
                  gr      0      1/2     0       1/2   0    0     1/2     1/2
                  co     1/6     2/3    1/6      2/3   0   1/6    1/2     1/2
                  st      0      1/2    1/2      0     0   1/2     0      1/2
                  pr     1/4     3/4    1/4      3/4   0   1/4    1/2     1/2
                  sst     0       1     1/2      1/2   0   1/2    1/2     1/2
                                                                                   □


6. Conclusions and Future Work
We have presented the totality, determinism and functionality properties for iAFs, and provided
complexity bounds for the problems of checking whether these properties hold under five well-
known argumentation semantics [1]. Analogously to several other computational approaches in
formal argumentation, these problems generally suffers from high computational complexity [30,
31, 32, 33, 28, 34, 35, 36, 37]. We have also identified equivalent forms of iAFs (in terms of
extensions), investigated possible and necessary variants of the credulous and skeptical acceptance
problems for iAFs. We have also explored the relationship between acceptance problems in iAFs
and probabilistic acceptance in PrAFs.
   As future work we plan to consider other notions of acceptance that, as totality, determinism,
and functionality, require the existence of an extension (e.g. skeptical acceptance under stable
semantics requiring non-emptyness [38]). We envisage that SAT-based approaches for computing
credulous and skeptical acceptance [39] could be used to define algorithms for checking function-
ality, totality and determinism since these properties can be defined in terms of credulous and
skeptical acceptance for AFs. More elaborated solutions need to be investigated for iAF. Con-
sidering the connections between iAFs and Control AFs [40, 41, 42, 43], we plan to investigate
totality, determinism, and functionality also in that context. Finally, it would be interesting to
consider the concepts of totality, determinism, and functionality in the presence of some kinds of
preferences, such as those in [10, 11, 14, 44, 45].


References
 [1] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Incomplete argumentation frameworks:
     Properties and complexity, in: Proc. of AAAI, 2022, pp. 5451–5460.
 [2] T. Bench-Capon, P. E. Dunne, Argumentation in artificial intelligence, Artif. Intell. 171
     (2007) 619 – 641.
 [3] G. R. Simari, I. Rahwan (Eds.), Argumentation in Artificial Intelligence, Springer, 2009.
 [4] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter, H. Prakken, C. Reed, G. R. Simari,
     M. Thimm, S. Villata, Towards artificial argumentation, AI Magazine 38 (2017) 25–36.
 [5] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
     reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321–358.
 [6] M. Caminada, Semi-stable semantics, in: Proceedings of the 1st International Conference
     on Computational Models of Argument (COMMA), 2006, pp. 121–130.
 [7] A. Cohen, S. Gottifredi, A. J. Garcia, G. R. Simari, An approach to abstract argumentation
     with recursive attack and support, J. of Applied Logic 13 (2015) 509–533.
 [8] C. Cayrol, J. Fandinno, L. F. del Cerro, M. Lagasquie-Schiex, Structure-based semantics of
     argumentation frameworks with higher-order attacks and supports, in: Proc. of COMMA,
     2018, pp. 29–36.
 [9] G. Brewka, H. Strass, S. Ellmauthaler, J. P. Wallner, S. Woltran, Abstract dialectical
     frameworks revisited, in: Proc. of IJCAI, 2013, pp. 803–809.
[10] L. Amgoud, C. Cayrol, On the acceptability of arguments in preference-based argumentation,
     in: Proc. of UAI, 1998, pp. 1–7.
[11] S. Modgil, H. Prakken, A general account of argumentation with preferences, Artif. Intell.
     195 (2013) 361–397.
[12] S. Coste-Marquis, C. Devred, P. Marquis, Constrained argumentation frameworks, in: Proc.
     of KR, 2006, pp. 112–122.
[13] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Argumentation frameworks with strong and
     weak constraints: Semantics and complexity, in: Proc. of AAAI, 2021, pp. 6175–6184.
[14] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract
     argumentation, in: Proc. of IJCAI, 2022, pp. 2517–2524.
[15] D. Baumeister, D. Neugebauer, J. Rothe, H. Schadrack, Verification in incomplete argumen-
     tation frameworks, Artif. Intell. 264 (2018) 1–26.
[16] D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen, J. Rothe, Acceptance in
     incomplete argumentation frameworks, Artif. Intell. (2021) 103470.
[17] P. M. Dung, P. M. Thang, Towards (probabilistic) argumentation for jury-based dispute
     resolution, in: Proc. of COMMA, 2010, pp. 171–182.
[18] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: Proc. of TAFA,
     2011, pp. 1–16.
[19] A. Hunter, Some foundations for probabilistic abstract argumentation, in: Proc. of COMMA,
     2012, pp. 117–128.
[20] C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994.
[21] D. Baumeister, D. Neugebauer, J. Rothe, Credulous and skeptical acceptance in incomplete
     argumentation frameworks, in: Proc. of COMMA, 2018, pp. 181–192.
[22] T. Mantadelis, S. Bistarelli, Probabilistic abstract argumentation frameworks, a possible
     world view, International Journal of Approximate Reasoning 119 (2020) 204–219.
[23] T. Rienstra, Towards a probabilistic Dung-style argumentation system, in: Proc. of the
     International Conference on Agreement Technologies, 2012, pp. 138–152.
[24] B. Fazzinga, S. Flesca, F. Parisi, On the complexity of probabilistic abstract argumentation
     frameworks, ACM Transactions on Computational Logic 16 (2015) 22:1–22:39.
[25] B. Fazzinga, S. Flesca, F. Furfaro, Complexity of fundamental problems in probabilistic
     abstract argumentation: Beyond independence, Artificial Intelligence 268 (2019) 1–29.
[26] B. Fazzinga, S. Flesca, F. Furfaro, Abstract argumentation frameworks with marginal
     probabilities, in: Proc. of IJCAI, 2022, pp. 2613–2619.
[27] B. Fazzinga, S. Flesca, F. Furfaro, Probabilistic bipolar abstract argumentation frameworks:
     complexity results, in: Proc. of IJCAI, 2018, pp. 1803–1809.
[28] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in
     probabilistic abstract argumentation: Complexity and approximation, in: Proceedings of
     the International Conference on Principles of Knowledge Representation and Reasoning
     (KR), 2020, pp. 33–43.
[29] B. Fazzinga, S. Flesca, F. Furfaro, Credulous and skeptical acceptability in probabilistic
     abstract argumentation: complexity results, Intelligenza Artificiale 12 (2018) 181–191.
[30] W. Dvorák, M. Järvisalo, J. P. Wallner, S. Woltran, Complexity-sensitive decision procedures
     for abstract argumentation, Artificial Intelligence 206 (2014) 53–78.
[31] M. Kröll, R. Pichler, S. Woltran, On the complexity of enumerating the extensions of
     abstract argumentation frameworks, in: Proceedings of International Joint Conference on
     Artificial Intelligence (IJCAI), 2017, pp. 1145–1152.
[32] G. Alfano, S. Greco, F. Parisi, On scaling the enumeration of the preferred extensions
     of abstract argumentation frameworks, in: Proceedings of ACM/SIGAPP Symposium on
     Applied Computing (SAC), 2019, pp. 1147–1153.
[33] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. R. Simari, Dynamics in abstract
     argumentation frameworks with recursive attack and support relations, in: Proceedings of
     the 24th European Conference on Artificial Intelligence (ECAI), 2020, pp. 577–584.
[34] G. Alfano, S. Greco, Incremental skeptical preferred acceptance in dynamic argumentation
     frameworks, IEEE Intelligent Systems 36 (2021) 6–12.
[35] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation of
     warranted arguments in dynamic defeasible argumentation: the rule addition case, in:
     Proceedings of the 33rd Annual ACM Symposium on Applied Computing, (SAC), 2018,
     pp. 911–917.
[36] G. Alfano, S. Greco, F. Parisi, Incremental computation in dynamic argumentation frame-
     works, IEEE Intell. Syst. 36 (2021) 80–86.
[37] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for
     structured argumentation over dynamic DeLP knowledge bases, Artificial Intelligence 300
     (2021) 103553.
[38] P. E. Dunne, M. Wooldridge, Complexity of abstract argumentation, in: Argumentation in
     Artificial Intelligence, Springer, 2009, pp. 85–104.
[39] M. Järvisalo, SAT for argumentation, in: Proceedings of the International Workshop on
     Systems and Algorithms for Formal Argumentation (SAFA), volume 2171, 2018, pp. 1–3.
[40] D. Neugebauer, J. Rothe, K. Skiba, Complexity of nonemptiness in control argumentation
     frameworks, in: Proc. of ECSQARU, 2021, pp. 117–129.
[41] F. Gaignier, Y. Dimopoulos, J. Mailly, P. Moraitis, Probabilistic control argumentation
     frameworks, in: Proc. of AAMAS, 2021, pp. 519–527.
[42] Y. Dimopoulos, J. Mailly, P. Moraitis, Control argumentation frameworks, in: Proceedings
     of the AAAI Conference on Artificial Intelligence, 2018, pp. 4678–4685.
[43] A. Niskanen, D. Neugebauer, M. Järvisalo, Controllability of control argumentation
     frameworks, in: Proc. of IJCAI, 2020, pp. 1855–1861.
[44] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
     Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[45] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)cp-nets:
     Max and rank voting, Artif. Intell. 303 (2022) 103636.

</pre>