# incomplete_argumentation_frameworks_properties_and_complexity__12500d34.pdf

Incomplete Argumentation Frameworks: Properties and Complexity

Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Irina Trubitsyna

Department of Informatics, Modeling, Electronics and System Engineering, University of Calabria, Italy {g.alfano, greco, fparisi, i.trubitsyna}@dimes.unical.it

Dung s Argumentation Framework (AF) has been extended in several directions, including the possibility of representing unquantiﬁed uncertainty about the existence of arguments and attacks. The framework resulting from such an extension is called incomplete AF (i AF). In this paper, we ﬁrst introduce three new satisfaction problems named totality, determinism and functionality, and investigate their computational complexity for both AF and i AF under several semantics. We also investigate the complexity of credulous and skeptical acceptance in i AF under semi-stable semantics a problem left open in the literature. We then show that any i AF can be rewritten into an equivalent one where either only (unattacked) arguments or only attacks are uncertain. Finally, we relate i AF to probabilistic argumentation framework, where uncertainty is quantiﬁed.

Introduction

Formal argumentation has emerged as one of the important ﬁelds in Artiﬁcial Intelligence (Bench-Capon and Dunne 2007; Simari and Rahwan 2009; Atkinson et al. 2017). In particular, Dung s abstract Argumentation Framework (AF) is a simple yet powerful formalism for modeling disputes between two or more agents (Dung 1995). An AF consists of a set of arguments and a binary attack relation over the set of arguments that speciﬁes the interactions between arguments: intuitively, if argument a attacks argument b, then b is acceptable only if a 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) (Dung 1995), and semi-stable (sst) (Caminada 2006) have been deﬁned for AF, leading to the characterization of σ-extensions, that intuitively consist of 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. The extensions include Bipolar AF (Nouioua and Risch 2011; Nouioua 2013; Villata et al. 2012), AF

Copyright 2022, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Figure 1: i AF of Example 1.

with recursive attacks and supports (Cohen et al. 2015; Gottifredi et al. 2018; Cayrol et al. 2018), Dialectical framework (Brewka and Woltran 2010; Brewka et al. 2013), AF with preferences (Amgoud and Cayrol 1998; Modgil and Prakken 2013) and constraints (Coste-Marquis, Devred, and Marquis 2006; Arieli 2015; Alfano et al. 2021b), as well extensions for representing uncertain information. For the representation of uncertain information, two main extensions have been proposed: incomplete AF (i AF), where arguments and attacks may be uncertain (Baumeister et al. 2018, 2021), and probabilistic AF (Pr AF), where arguments and attacks are associated with a probability (Dung and Thang 2010; Li, Oren, and Norman 2011; Hunter 2012). In this paper we focus on i AF, but we will also study its connection with Pr AF.

Example 1. Consider an i AF = {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, where dashed nodes represent uncertain arguments (see Deﬁnition 1 for the formal deﬁnition). 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 that can join the party. This situation can be modeled by i AF , 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 i AF 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 σ.

Example 2. Continuing with Example 1, the completions of are as follows:

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

Λ1 = {a, b, c, d, e}, {(a, b), (b, a), (a, c), (b, d), (c, d), (d, c), (d, a), (e, a), (e, b)} ; Λ2 = {a, b, c, d}, {(a, b), (b, a), (a, c), (b, d), (c, d), (d, c), (d, a)} .

Completion Λ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 deﬁned for AF are non-deterministic (or multiple-status), the notions of credulous and skeptical acceptance have been deﬁned. 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 i AF: 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. Our main contributions are as follows.

Determinism, totality, and functionality for AF. We introduce three satisfaction problems for AF called determinism (DS), totality (TS), and functionality (FS). Informally, an argument is said to be deterministic if all extensions assign the same status (either accepted, rejected, or undeﬁned) to it, whereas it is said to be total if for all extensions it is either accepted or rejected (i.e. it is never undeﬁned). Totality is inspired by the criterion leading to stable semantics (Dung 1995). In fact, it requires the same property as the stable semantics but for a given goal argument (instead of all arguments). Speciﬁcally, while stable semantics forces the status of all arguments to be either accepted or rejected, totality requires this condition for a given goal argument under semantics σ. For instance, given an AF, we may be interested to know if an argument The defendant is guilty can be decided w.r.t. any σ-extension, i.e. if it is total. For AFs, determinism tells us if the status of a given argument is always the same (accepted/rejected/undecided), that is if we can safely make a decision or not based on the available knowledge. When both totality and determinism hold for a given argument, we say that it is functional. We study the complexity of the problems of checking determinism (DS), totality (TS), and functionality (FS) under several semantics for general and odd-cycle free AF (see Table 1).

Determinism, totality, and functionality for i AF. We extend the totality, deterministic and functional properties to i AFs. In this context, an argument a is total (resp. deterministic, functional) if it is total (resp. deterministic, functional) in every completion. Thus, for i AF, 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 ﬁrmly decided whatever the considered scenario is, that is if the information at hand

(General) AF odd-cycle free AF σ TS DS FS TS DS FS gr P trivial P P trivial P co P co NP-c P P co NP-c P st NP-c DP-c DP-c trivial co NP-c co NP-c pr Πp 2-c Πp 2-c Πp 2-c trivial co NP-c co NP-c sst Πp 2-c Πp 2-c Πp 2-c trivial co NP-c co NP-c

Table 1: Complexity of TS, DS, and FS problems for AFs.

(General) i AF odd-cycle free i AF σ TS DS FS TS DS FS gr co NP-c trivial co NP-c co NP-c trivial co NP-c co co NP-c co NP-c co NP-c co NP-c co NP-c co NP-c st Πp 2-c Πp 2-c Πp 2-c trivial co NP-c co NP-c pr Πp 2-c Πp 2-c Πp 2-c trivial co NP-c co NP-c sst Πp 2-c Πp 2-c Πp 2-c trivial co NP-c co NP-c

Table 2: Complexity of TS, DS, and FS problems for i AFs.

is sufﬁcient to make a decision irrespective of the possible world, as shown in the following example.

Example 3. Continuing with Examples 1 and 2, suppose the party planner is interested to know if, whatever Erik decide to do, he has sufﬁcient information to decide whether or not Alice (resp. Bob) joins the party. The preferred (stable/semistable) 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 scenarios (Erik joins or not the party). Note that such questions cannot be answered by possible/necessary credulous/skeptical acceptance. In fact, a is functional but not possible credulously accepted, and b is functional but not necessary skeptically accepted.

We investigate the complexity of the problems of checking determinism, totality, and functionality for general i AF and odd-cycle free i AF. Our results are reported in Table 2.

Possible/Necessary Credulous/Skeptical Acceptance under Semi-Stable Semantics. We investigate the problems of (i) possible credulous (resp. skeptical) acceptance (PCA, resp. PSA), and (ii) necessary credulous (resp. skeptical) acceptance (NCA, resp. NSA) under semi-stable semantics though studied for semantics σ {gr, co, st, pr}, the investigation of the complexity of these problems was left open for semi-stable semantics in (Baumeister et al. 2018; Fazzinga, Flesca, and Furfaro 2020). We show that under semi-stable semantics PCA (resp. PSA) is Σp 2-complete (resp. Σp 3-complete), whereas NCA (resp. NSA) is Πp 3complete (resp. Πp 2-complete). Thus, compared with the results for the preferred semantics (Baumeister et al. 2018), the complexity increases of one level of the polynomial hierarchy for credulous reasoning, while it does not change for skeptical reasoning and for problems DS, TS and FS (the results on last two rows of Table 2 coincide).

Equivalent Forms of i AF: arg-i AF, att-i AF, and farg-i AF. We show that an i AF can be rewritten into an equivalent

one , such that for every σ-extension E of , there is a σ-extension E of coinciding with E (modulo some meta-arguments added in the rewriting). Particularly, can be of one of the following forms: i) only arguments or only attacks are uncertain ( is said to be an arg-i AF or att-i AF, respectively); or ii) uncertainty is only on arguments that are not attacked by any other argument ( is said to be an farg-i AF). We also show that an arg-i AF can be translated into an farg-i AF. It can be shown that the results in Table 2 also hold for these restricted forms of i AFs.

Relationship between i AF and Pr AF. Finally, using the equivalence result between i AF and arg-i AF, we investigate the relationships between i AF and Pr AF and relate the (possible/necessary credulous/skeptical) acceptance problems in i AF to probabilistic acceptance in Pr AF. For instance, we show that, under the assumption that for each completion the existence of at least one extension is guaranteed, if an argument is necessarily skeptically accepted then its probabilistic acceptance is 1, whereas in all other cases if the argument is accepted then the probability of acceptance is in the interval (0, 1]. In our approach we derive a Pr AF encoding a given i AF, and also show that computing the probability of acceptance of an argument is FP#P-hard even restricting to acyclic i AFs. Proofs of our results are available in (Alfano et al. 2021c).

Preliminaries In this section, we ﬁrst review the Dung s framework and the incomplete one, and then recall complexity classes.

Argumentation Framework An abstract Argumentation Framework (AF) (Dung 1995) is a pair A, R , where A is a set of arguments and R A A is a set of attacks. Given an AF Λ = A, R and a set S A of arguments, an argument a A is said to be i) defeated w.r.t. S iff there exists b S such that (b, a) R, and ii) acceptable w.r.t. S iff for every argument b A with (b, a) R, there is c S such that (c, b) R. The sets of arguments defeated and acceptable w.r.t. S are as follows (where Λ is understood): Def(S)={a A | b S . (b, a) R}; Acc(S)={a A | b A . (b, a) R b Def(S)}. Given an AF A, R , a set S A of arguments is said to be conﬂict-free iff S Def(S) = . Moreover, S A is said to be a complete (co) extension iff it is conﬂict-free and S = Acc(S). A complete extension S A 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 S Def(S) = A; 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 speciﬁed 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) (Dung 1995; Caminada 2006). 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 E or Def(E) (i.e. it is either true or false) for every extension E. For any AF Λ, it holds that st(Λ) sst(Λ) pr(Λ) co(Λ), and gr(Λ) co(Λ). An AF is acyclic (resp. oddcycle 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 a or its negation a. A set of literals S is said to be consistent if it does not contain two literals a and a. We use S to denote the set { a | a S}, and S to denote S S. To deal with literals, we deﬁne the notion of fulﬁllment of an extension. Given AF Λ = A, R and an extension E for it, the fulﬁllment of E is E Def(E). Clearly, the fulﬁllment of an extension is a consistent set of literals. Herein, arguments in E are represented as positive literals (i.e. interpreted as true), while arguments defeated by E 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 fulﬁllment. For any AF Λ = A, R , semantics σ, and literal a A , we say that a is credulously (resp. skeptically) accepted (under semantics σ), denoted as CAσ(Λ, a) (resp. SAσ(Λ, a)) if a 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 4. Consider the AF Λ = {a, b, c, d}, {(a, b), (b, a), (a, c), (b, c), (c, d), (d, c)} . Λ has 4 complete extensions: E0 = , E1 = {a, b, c, d}, E2 = { a, b, c, d} and E3 = { c, d}. That is, co(Λ) = {E0, E1, E2, E3}. E0 is the grounded extension, E1 and E2 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.

Incomplete Argumentation Framework

We now recall the incomplete AF (Baumeister et al. 2018).

Deﬁnition 1 (Incomplete AF). An incomplete (abstract) Argumentation Framework (i AF) is a tuple = A, B, R, T , where A and B are disjoint sets of arguments, and R and T are disjoint sets of attacks between arguments in A B. Arguments in A and attacks in R are said to be certain, while arguments in B and attacks in T are said to be uncertain.

Certain arguments in A are deﬁnitely known to exist, while uncertain arguments in B are not known for sure: they may occur or may not. Analogously, certain attacks in R are deﬁnitely known to exist if both the incident arguments ex-

ist, while for uncertain attacks in T it is not known for sure if they hold, even if both the incident arguments exist. An i AF compactly represents alternative AF scenarios, called completions. Deﬁnition 2 (Completion). A completion for an i AF = A, B, R, T is an AF Λ = A , R where A A A B and R (A A ) R (R T) (A A ). The set of completions of is denoted by comp( ). An i AF A, B, R, T is acyclic (resp. odd-cycle free) iff the AF A B, R T is acyclic (resp. odd-cycle free). To deﬁne acceptability and properties satisfaction of literals for i AFs, we reﬁne the deﬁnition of fulﬁllment of extensions. Given an i AF = A, B, R, T and an extension E for a completion Λ = A , R of , the fulﬁllment of E is E Def(E) (B \ A ). Herein, arguments in E are represented as positive literals (i.e. interpreted as true), while arguments attacked by E as well as uncertain arguments not occurring in Λ are represented as negative literals (i.e. interpreted as false). Example 5. Consider the i AF of Example 1 and the completion Λ2 reported in Example 2. Λ2 has only one preferred extension, {b, c}, whose fulﬁllment is { a, b, c, d, e}.

Acceptance problems. Credulous and skeptical acceptance for i AF have been recently proposed in (Baumeister, Neugebauer, and Rothe 2018), where the goal, i.e. the element for which acceptance is checked, is an argument. As we focus on fulﬁllment of extensions, our goal is a literal. Deﬁnition 3 (Possible/Necessary Credulous/Skeptical Acceptance). Let = A, B, R, T be an i AF and σ {gr, co, st, pr, sst}. Then, a literal g A B is said to be: 1. possibly credulously accepted under σ, denoted as PCAσ( , g), iff there exists a completion Λ of and a σ-extension E of Λ such that g E; 2. possibly skeptically accepted under σ, denoted as PSAσ( , g), iff there exists a completion Λ of such that g occurs in every σ-extension of Λ; 3. necessarily credulously accepted under σ, denoted as NCAσ( , g), iff for every completion Λ of , there exists a σ-extension E of Λ such that g E; 4. necessarily skeptically accepted under σ, denoted as NSAσ( , g), iff for every completion Λ of , g 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 Deﬁnition 3. For the grounded semantics we have PCAgr PSAgr and NCAgr NSAgr. Example 6. Consider the i AF = {a, b, d}, {c}, {(a, b), (b, a)}, . has 2 completions: Λ1 = {a, b, d}, {(a, b), (b, a)} and Λ2 = {a, b, c, d}, {(a, b), (b, a)} . Under semantics σ {st, pr, sst}, Λ1 has two extensions E 1 = {a, b, c, d} and E 1 = { a, b, c, d}, while Λ2 has two extensions E 2 = {a, b, c, d} and E 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 satisﬁes NSA.

Observe that we consider acceptance of literals and, differently from (Fazzinga, Flesca, and Furfaro 2020) and (Baumeister et al. 2018), we also deal with sst semantics.

Complexity Classes We recall here the main complexity classes used in the paper and, in particular, the deﬁnition of the classes Σp k and Πp k, with k 0 (see e.g. (Papadimitriou 1994)): (i) Σp 0 = Πp 0 = P; (ii) Σp 1 = NP and Πp 1 = co NP; and (iii) Σp k = NP Σp k 1 and Πp k = coΣp k, k > 0. P denotes the class of problems that can be solved in polynomial time (w.r.t. the size of the input) by a deterministic Turing machine. NPC denotes the class of problems that can be solved in polynomial time using an oracle in the class C by a non-deterministic Turing machine. Under a standard complexity assumption, Σp k Σp k+1 PSPACE and Πp k Πp k+1 PSPACE. A language L is in the class DP iff there are two languages L1 NP and L2 co NP such that L = L1 L2. FP is the class of the function problems that can be solved in polynomial time by a deterministic Turing machine. FP#P is the class of functions computable by a polynomial-time Turing machine with a #P oracle. #P is the complexity class of the functions counting the number of accepting paths of a nondeterministic poly-time Turing machine (Valiant 1979).

Totality, Determinism and Functionality in AF In this section we discuss desirable properties to be satisﬁed by literals w.r.t. a given semantics. As discussed in the introduction, these properties concern the fact that the status of a literal is i) never undeﬁned (totality), ii) the same in all extensions (determinism), and iii) never undeﬁned and the same in all extensions (functionality). They will be extended to the case of i AFs in a subsequent section.

Deﬁnition 4. Let Λ = A, R be an AF, σ {gr, co, st, pr, sst}, and g A a literal. We say that g is:

total under σ, denoted as TSσ(Λ, g), if i) σ(Λ) = and ii) for each E σ(Λ), either g E or g E; deterministic under σ, denoted as DSσ(Λ, g), if i) σ(Λ) = , and ii) either SAσ(Λ, g) or SAσ(Λ, g) or ( CAσ(Λ, g) CAσ(Λ, g)); functional under σ, denoted as FSσ(Λ, g), if g is total and deterministic under σ, that is i) σ(Λ) = and ii) either SAσ(Λ, g) or SAσ(Λ, g).

Observe that only for σ = st we may have σ(Λ) = : for all other semantics we have that σ(Λ) = . We use TSσ (resp. DSσ, FSσ) to denote the problem of deciding whether a goal is total (resp. deterministic, functional). The next theorem states the complexity of checking these properties.

Theorem 1. For general AFs, it holds that:

TSσ is polynomial for σ {gr, co}, NP-complete for σ = st, and Πp 2-complete for σ {pr, sst}; DSσ is trivial for σ = gr, co NP-complete for σ = co, DP-complete for σ = st, and Πp 2-complete for σ {pr, sst}; FSσ is polynomial for σ {gr, co}, DP-complete for σ = st, and Πp 2-complete for σ {pr, sst}.

Example 7. Considering the AF of Example 4, literals c and d are functional for σ {st, pr, sst}, whereas a and b are total, but not deterministic, for σ = st. Obviously, for σ = gr all literals are deterministic, but not total. Theorem 2. For odd-cycle free AFs, it holds that: TSσ is polynomial for σ {gr, co}, trivial for σ {st, pr, sst}; DSσ trivial for σ = gr; co NP-complete for σ {co, st, pr, sst}; FSσ is polynomial for σ {gr, co}, and co NP-complete for σ {st, pr, sst}. Proposition 1. For any AF Λ = A, R , literal g A , and semantics σ {gr, co, pr, sst}, it holds that: DSσ(Λ, g) = false SAσ(Λ, g) = false (or, equivalently, SAσ(Λ, g) = true DSσ(Λ, g) = true) , and FSσ(Λ, g) SAσ(Λ, g) SAσ(Λ, g). Concerning the previous results, notice that stable, preferred and semi-stable semantics coincide for odd-cycle free AFs, and thus the existence of a stable extension is always guaranteed (Dung 1995). Thus, Proposition 1 holds also for σ = st and odd-cycle free AFs.

Totality, Determinism and Functionality in i AF The concepts of totality, determinism and functionality, deﬁned in the context of AF can be extended to i AF as follows. Deﬁnition 5 (Total, deterministic, functional literals). Let = A, B, R, T be an i AF, σ {gr, co, st, pr, sst}, and g A B a goal literal. We say that g is: total under σ, denoted as TSσ( , g), if for each Λ comp( ), i) σ(Λ) = and ii) for each E σ(Λ), either g E or g E; deterministic under σ, denoted as DSσ( , g), if for each Λ comp( ), i) σ(Λ) = , and ii) either SAσ(Λ, g) or SAσ(Λ, g) or ( CAσ(Λ, g) CAσ(Λ, g)); functional under σ, denoted as FSσ( , g), if g is total and deterministic under σ, that is, for each Λ comp( ), i) σ(Λ) = and ii) either SAσ(Λ, g) or SAσ(Λ, g). The next result immediately derives from deﬁnitions. Fact 1. Let be an i AF, σ {gr, co, st, pr, sst} and g a literal. We have that i) TSσ( , g) TSσ( , g), ii) DSσ( , g) DSσ( , g), and iii) FSσ( , g) FSσ( , g) hold. Example 8. Consider the i AF = A = {a, b, c}, B = {d}, R = {(a, b), (b, a), (b, c), (c, c), (d, a), (d, b)}, T = reported in Figure 2, left side. has two completions Λ1 = A, R \ {(d, a), (d, b)} and Λ2 = A B, R , also shown in Figure 2 (center). For Λ1 there are three complete extensions (recall that we refer to the fulﬁllments): E0 = { d}, E1 = {a, b, d} and E2 = { a, b, c, d}. The grounded extension is E0, while E1 is preferred, and E2 is stable, preferred, and semi-stable. For Λ2 there is only one complete extension E3 = { a, b, d}, which is grounded, preferred, and semi-stable. The goal b is i) total only for semantics pr and sst (it is not total for st as Λ2 does not have stable extensions) and ii) deterministic for semantics gr, st and

sst (it is not deterministic for pr as the two preferred extensions, E1 and E2, of Λ1 are such that E1 contains b while E2 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 complexity of the aforementioned problems is characterized in the following theorem.

Theorem 3. For general i AFs, it holds that:

TSσ is co NP-complete for σ {gr, co} and Πp 2complete for σ {st, pr, sst}; DSσ is trivial for σ = gr, co NP-complete for σ = co, and Πp 2-complete for σ {st, pr, sst}; FSσ is co NP-complete for σ {gr, co} Πp 2-complete for σ {st, pr, sst}.

The next proposition provides conditions under which unattacked arguments are functional.

Proposition 2. For any i AF = A, B, R, T and unattacked argument g A B, it holds that g 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 deterministic. However, this does not hold for general i AFs 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 odd-cycle free i AFs.

Theorem 4. For odd-cycle free i AFs, it holds that:

TSσ is co NP-complete for σ {gr, co} and trivial for σ {st, pr, sst}; DSσ is trivial for σ = gr, co NP-complete for σ {co, st, pr, sst}; FSσ is co NP-complete for σ {gr, co, st, pr, sst}.

The results of Theorem 4 complement those of Theorem 3 (see Table 2). Except for the grounded and complete semantics, the complexity of checking determinism and functionality decreases by one level of the polynomial hierarchy whereas checking totality becomes trivial.

Acceptance Problems for i AF We ﬁrst characterize the complexity of the so-called veriﬁcation problems for i AF under the semi-stable semantics. To this end, we need to introduce the concepts of possible and necessary extension for i AF (Baumeister et al. 2018; Fazzinga, Flesca, and Furfaro 2020). Given an i AF and a semantics σ, a (consistent) set of literals S is said to be a possible (resp. necessary) σ-extension for if for at least one (resp. for every) completion Λ of , S is a σ-extension of Λ.1 The veriﬁcation problem is then deﬁned as follows. Given an i AF , a semantics σ and a set of literals S,

1We use the deﬁnition of possible (resp. necessary) σ-extension introduced in (Fazzinga, Flesca, and Furfaro 2020) that revised the initial deﬁnition in (Baumeister et al. 2018).

the possible (resp. necessary) veriﬁcation problem is deciding whether S is a possible (resp. necessary) σ-extension of . It has been shown that the complexity of the possible and necessary veriﬁcation problems is polynomial for σ {gr, co, st}, whereas it is Σp 2-complete (resp. co NPcomplete) for the possible (resp. necessary) variant under the preferred semantics (Fazzinga, Flesca, and Furfaro 2020). As stated next, the complexity of the veriﬁcation problems for the semi-stable and preferred semantics coincides. Theorem 5. Given an i AF = A, B, R, T and a consistent set S A B , checking whether S is a possible (resp. necessary) sst-extension of is Σp 2-complete (resp. co NP-complete). After characterizing the complexity of the veriﬁcation problem, in the next theorem we consider the acceptance problems (cf. Deﬁnition 3) for semi-stable semantics. Theorem 6. PCAsst (resp. PSAsst, NCAsst, and NSAsst) is Σp 2-complete (resp. Σp 3-complete, Πp 3-complete, and Πp 2complete). Compared with the results for the other semantics (Baumeister et al. 2018), it turns out that deciding PCA and NCA for sst is more costly than for any other semantics, while deciding PSAsst and NSAsst costs the same as deciding PSApr and NSApr, respectively. Moreover, the results of Theorems 5 and 6 complement those in Table 2, showing that, though problems DS, TS, and FS under sst and pr have the same complexity, these semantics behave differently under credulous reasoning.

Equivalent Forms of i AFs In this section we show that i AFs can be rewritten into equivalent i AFs where uncertainty is restricted to either attacks or (unattacked) arguments. Deﬁnition 6 (arg-i AF and att-i AF). An i AF = A, B, R, T is said to be argument-incomplete (arg-i AF for short) if T = , whereas it is said to be attack-incomplete (att-i AF for short) if B = . Given an i AF , we denote by arg( ) the arg-i AF derived from by replacing every uncertain attack (a, b) with the certain attacks (a, αab), (αab, βab), (βab, b), where αab (resp. βab) is a fresh certain (resp. uncertain) argument. Analogously, we denote by att( ) the att-i AF derived from as follows: for each uncertain argument b, make b certain and add an uncertain attack (α, b), where α is a fresh certain argument it is sufﬁcient to add only one fresh argument α. Example 9. Consider the i AF = {b, c}, {a}, {(a, b), (b, a)}, {(b, c)} . The arg-i AF derived from is = {b, c, αbc}, {a, βbc}, {(a, b), (b, a), (b, αbc), (αbc, βbc), (βbc, c)}, , whereas the att-i AF derived from is = {b, c, a, α}, , {(a, b), (b, a)}, {(b, c), (α, a)} . The transformations described above to eliminate uncertain attacks/arguments are inspired by those proposed in (Mantadelis and Bistarelli 2020) to eliminate attacks/arguments with probability less than 1 in probabilistic AF. We now introduce a special class of arg-i AFs.

Deﬁnition 7 (farg-i AF). An arg-i AF = A, B, R, is said to be fact-uncertain (farg-i AF) iff (a, b) R, b B. Observe that the i AF of Example 1 is an farg-i AF. Given an arg-i AF , farg( ) denotes the farg-i AF derived from as follows: for each uncertain argument b which is attacked in , make b certain and add the attacks (bu, bc), (bc, b), where bc (resp. bu) is a fresh certain (resp. uncertain) argument. With a little abuse of notation, for any i AF we use farg( ) to denote farg(arg( )). Example 10. Considering an arg-i AF = {m, r}, {f, w}, {(f, m), (m, f), (m, w), (w, r), (r, w)}, , the derived farg-i AF is as follows: {f, m, w, r, fc, wc}, {fu, wu}, {(f, m), (m, f), (m, w), (w, r), (r, w), (fu, fc), (fc, f), (wu, wc), (wc, w)}, . The completions of are obtained by selecting all subsets of the set {fu, wu} of uncertain arguments. Given an i AF = A, B, R, T , let ϕ {arg, att, farg}, for any Λ = A , R comp(ϕ( )), af (Λ ) denotes the AF Λ = A , R comp( ) with: A = A ((B A ) \ {a | (α, a) R au A }), and R = (R (A A )) ((T (A A )) \ {(a, b) | (βab A ) (βc ab A βu ab A )}. Herein, the set {a | (α, a) R au A } is used to avoid considering arguments either (i) attacked by α in comp(att( )) or (ii) always false in comp(farg( )) as au A . Analogously, {(a, b) | (βab A ) (βc ab A βu ab A )} is used to avoid considering uncertain attacks that are chosen to not occur in either (i) comp(arg( )), as βab A , or (ii) comp(farg( )) as (βc ab A βu ab A ). Example 11. Consider the i AF of Example 9. Then, farg( ) = A = {a, b, c, ac, αbc, βbc, βc bc}, B = {au, βu bc}, R = {(a, b), (b, a), (ac, a), (au, ac), (b, αbc), (αbc, βbc), (βbc, c), (βc bc, βbc), (βu bc, βc bc)}, T = . For Λ = A {au}, R \ {(βu bc, βc bc)} comp(farg( )), containing the uncertain argument au but not βu bc, af (Λ) = {a, b, c}, {(a, b), (b, a)} comp( ) that contains the uncertain argument a and does not contain the uncertain attack (b, c). Lemma 1. For any i AF and ϕ {arg, att, farg}, af : comp(ϕ( )) comp( ) is a surjective function. The next theorem states the equivalence between i AFs and the i AFs derived by applying the previous mappings. Theorem 7. Let = A, B, R, T be an i AF, σ {gr, co, st, pr, sst}, and ϕ {arg, att, farg}. Then, comp( ) = {af (Λ) | Λ comp(ϕ( ))}, and σ(Λ ) = {E (A B) | Λ comp(ϕ( )) Λ = af (Λ) E σ(Λ)} Λ comp( ). Thus, any i AF is equivalent to an arg-i AF (resp. fargi AF, att-i AF) 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-i AFs (resp. farg-i AF, att-i AF) have the same expressivity of general i AFs, though arg-i AFs (resp. farg-i AF, att-i AF) have a simpler structure. The results of Theorem 7 with those of Theorems 3 and 4 entail that the

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

Table 3: Acceptance probability for literals of Example 8. Bold denotes total literals, under the given semantics.

complexity results for the problems of checking totality, determinism, and functionality for i AFs in Table 2 also hold for each restricted form of i AFs (att-i AF, arg-i AF, f-arg-i AF). Finally, as shown in the next section, the restricted forms of i AF allow to establish a tight connection between i AF and Probabilistic AF, and simplify the presentation as it sufﬁces to focus on arg-i AF and an analogous form of restricted Probabilistic AF where only arguments are uncertain.

Probabilistic Acceptance

Probabilistic Argumentation Framework (Pr AF) has been investigated in the recent years (Li, Oren, and Norman 2011; Rienstra 2012; Fazzinga, Flesca, and Parisi 2015, 2016; Fazzinga, Flesca, and Furfaro 2019; Alfano et al. 2020a). Incomplete AF is tightly connected to Pr AF, as every completion of an i AF corresponds to a so-called possible world in Pr AF. Here we highlight this relationship and relate acceptance problems in i AF, to probabilistic acceptance in Pr AF. W.l.o.g. we focus on Pr AF where only arguments are uncertain (and attacks are certain, i.e. their probability is 1), since as shown in (Mantadelis and Bistarelli 2020) a Pr AF with probabilities on arguments and attacks can be transformed into an equivalent Pr AF where only arguments may have probability lower than 1. Here, an argument a A is viewed as a probabilistic event that is independent from events associated with other arguments b A (with b = a). Analogously to what is said above, since any i AF is equivalent to an arg-i AF, w.l.o.g. in the following we consider argi AFs and denote them by triples A, B, R (i.e. omitting the empty set of uncertain attacks).

Deﬁnition 8 (Pr AF). A Probabilistic Argumentation Framework (Pr AF) is a triple A, R, P where A, R is an AF, and P is a function assigning a non-zero probability value to every argument in A, that is, P : A (0, 1].

Observe that assigning probability equal to 0 to arguments is useless. Basically, the value assigned by P to any argument a represents the probability that a actually occurs. Moreover, every attack (a, b) occurs with conditional probability 1, that is, a attacks b whenever both a and b occur. The meaning of a Pr AF is given in terms of possible worlds. Given a Pr AF = A, R, P , a possible world of is an AF Λ = A , R such that A A and R = R (A A ). We use pw( ) to denote the set of all possible worlds of . An interpretation for a Pr AF = A, R, P is a probability distribution function (PDF) I over the set pw( ) of the possible worlds. Each Λ = A , R pw( ) is assigned by I probability I(Λ), where:

a b c a b c d

Figure 2: (From left to right:) i AF of Example 8, its completions Λ1 and Λ2, and its derived Pr AF p of Example 12.

a A\A (1 P(a)).

We now deﬁne a Pr AF p encoding an i AF . Deﬁnition 9 (Derived Pr AF). Given an arg-i AF = A, B, R , the Pr AF derived from is p = A B, R, P , where P : A B {1/2, 1} with P(a) = 1 for a A and P(b) = 1/2 for b B. It is easy to check that, given an arg-i AF = A, B, R , for every Λ pw( p), I(Λ) is equal to either 0 or 1 2|B| . As stated next, non-zero probability possible worlds of derived Pr AF p one-to-one correspond to completions of . Proposition 3. For any arg-i AF , comp( ) = {Λ | Λ pw( p) I(Λ) > 0}.

Example 12. Consider the arg-i AF of Example 8 (see Figure 2). The derived Pr AF p = A B, R, P , with P(x) = 1 for x {a, b, c} and P(d) = 1/2, is shown in Figure 2. There are only two possible worlds with probability greater than 0: Λ1 = A, R \ {(d, a), (d, b)} and Λ2 = A B, R with I(Λ1) = I(Λ2) = 1/2. Given a Pr AF, the probabilistic acceptance provides the probability that a given goal is accepted (Alfano et al. 2020a). Speciﬁcally, given a Pr AF , a semantics σ, and a goal literal g, the probability that g is accepted can be computed by associating to every extension E σ(Λ), with Λ pw( ), a probability Pr(E, Λ, σ) so that P E σ(Λ) Pr(E, Λ, σ) = 1 (the sum of the probabilities of the σ-extensions of Λ is equal to 1). More in detail, a Pr AF p derived from a given i AF is considered, and a PDF over the set σ(Λ) of the extensions of each possible world Λ pw( p) is required. This means that the condition σ(Λ) = must hold. To ensure this, in the rest of this section, if not speciﬁed otherwise, whenever we write semantics σ and (arg-)i AF we mean that either i) σ {gr, co, pr, sst} and is an (arg-)i AF 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 Λ pw( p). Deﬁnition 10 (Probabilistic Acceptance). Given an arg-i AF = A, B, R and a literal g A B , the probability Pr Aσ (g) that g is acceptable w.r.t. semantics σ is:

Pr Aσ (g) = X

Λ pw( p) E σ(Λ) g E

I(Λ) Pr(E, Λ, σ)

where Pr( , Λ, σ) is a PDF over the set σ(Λ). Hereafter, we consider the uniform PDF assigning to every σ-extension of Λ the same probability (1/n where n is the number of σ-extensions). Our results still hold for other PDFs over σ(Λ), such as that used in (Alfano et al. 2020a). Given an arg-i AF and a literal g, the problem of computing the value Pr Aσ (g) (under a given semantics σ) is

denoted by Pr Aσ, or simply Pr A whenever σ is understood. We recall that Pr Aσ is deﬁned after choosing an arbitrary but ﬁxed PDF over the set of extensions. As stated next, Pr Aσ is FP#P-hard, regardless of the chosen PDF and semantics σ.

Theorem 8. Pr Aσ is FP#P-hard, even for acyclic arg-i AF and for any chosen PDF.

The following propositions highlight the relations between i AFs and Pr AFs (with uniform PDF over extensions).

Proposition 4. For any goal g, we have that:

PCAσ( , g) is false iff Pr Aσ p(g) = 0; NSAσ( , g) is true iff Pr Aσ p(g) = 1.

The connection between i AF and Pr AF is also investigated in (Baumeister et al. 2021), where the Pr AF associated to an i AF 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 (Fazzinga, Flesca, and Furfaro 2018), which is different from that of probabilistic acceptance of Deﬁnition 10. Indeed, the probability that an argument g is credulously (resp. skeptically) accepted is the sum of the probabilities of the possible worlds where g is credulously (resp. skeptically) accepted, according to a given semantics σ. Hence, the probability of a world Λ is added to the summation iff g belongs to at least one (resp. every) σ-extension of Λ. In contrast, with the aim of offering a more granular approach, Deﬁnition 10 uses the probabilities assigned to σ-extensions by the PDF Pr( , Λ, σ). For instance, taking the Pr AF p of Example 12 (see Figure 2), under the complete semantics the probabilistic skeptical (resp. credulous) acceptance of b is 0 (resp. 1/2), while Pr Aco p(b) = 1/6 as b belongs to one of three extensions of one of the two worlds (cf. Table 3). Although the conditions of Proposition 4 are similar to those identiﬁed in (Baumeister et al. 2021), they refer to different notions of probabilistic acceptance. In fact, while probabilistic skeptical and credulous acceptance deﬁne an interval, Deﬁnition 10 provides a precise value in that interval. The next proposition considers acyclic arg-i AFs, a subclass of odd-cycle free i AFs.

Proposition 5. Let = A, B, R be an acyclic arg-i AF and g a goal. It holds that:

PSAσ( , g) PCAσ( , g) and NSAσ( , g) NCAσ( , g); PSAσ( , g) is true iff Pr Aσ p(g) 1 2|B| ; NSAσ( , g) is false iff Pr Aσ p(g) 1 1 2|B| .

Our last result relates the satisfaction of properties (e.g. totality) to probabilistic acceptance.

Theorem 9. A goal g is:

total iff Pr Aσ (g) + Pr Aσ ( g) = 1; deterministic iff Λ comp( ), P

α Pr(E, Λ, σ) = 1,

where either (i) α = E σ(Λ) g E or (ii) α = E σ(Λ) g E or (iii) α = E σ(Λ) (g E g E).

Example 13. Consider again the i AF of Example 8. Assuming a uniform distribution for the probabilities of extensions,

the probabilistic acceptance of literals is as reported in Table 3 (where bold means that the literal of the column is total under the semantics of the row).

Conclusions and Future Work We have presented the total, deterministic and functional properties for AFs and i AFs, and provided complexity bounds for the problems of checking whether these properties hold under ﬁve well-known argumentation semantics. We also identiﬁed equivalent forms of i AFs (in terms of extensions), investigated possible and necessary variants of the credulous and skeptical acceptance problems for i AFs, and addressed the possible and necessary veriﬁcation problems under semi-stable semantics (left open in previous work). We have also explored the relationship between acceptance problems in i AFs and probabilistic acceptance in Pr AFs. As i AF generalizes Partial AF (Coste-Marquis et al. 2007; Baumeister et al. 2021), allowing to model the problem of merging AFs representing subjective views of several agents, we believe that checking totality, determinism, and functionality in such context may help in understanding agents points of view. As future work we plan to extend our investigation to other semantics, such as ideal (Dung, Mancarella, and Toni 2007) and eager semantics (Caminada 2007). We also plan to consider other notions of acceptance that, as totality/determinism/functionality, require the existence of an extension (e.g. skeptical acceptance under stable semantics requiring non-emptyness (Dunne and Wooldridge 2009)). We envisage that SAT-based approaches for computing credulous and skeptical acceptance (J arvisalo 2018) could be used to deﬁne algorithms for checking functionality, totality and determinism since these properties can be deﬁned in terms of credulous and skeptical acceptance for AFs. More elaborated solutions need to be investigated for i AF. Considering the connections between i AFs and Control AFs (Neugebauer, Rothe, and Skiba 2021; Gaignier et al. 2021; Dimopoulos, Mailly, and Moraitis 2018; Mailly 2020; Niskanen, Neugebauer, and J arvisalo 2020), we plan to investigate totality, determinism, and functionality in that context. Finally, given the inherent dynamic nature of argumentation and the typical high computational complexity of most of the reasoning tasks (Alfano et al. 2020a), there have been efforts toward the investigation of incremental techniques that use AF solutions (e.g. extensions, skeptical acceptance) at time t to recompute updated solutions at time t + 1 after that an update (e.g. adding/ removing an attack) is performed (Greco and Parisi 2016a,b; Alfano, Greco, and Parisi 2017, 2019, 2021; Alfano and Greco 2021; Doutre and Mailly 2018). These approaches have been extended to argumentation frameworks more general than AFs (Alfano, Greco, and Parisi 2020; Alfano et al. 2020b; Alfano, Greco, and Parisi 2018a,b; Alfano et al. 2021a, 2018); in (Odekerken, Borg, and Bex 2020) stability in a dynamic structured argumentation setting is studied, where so-called future setups can be seen as completions of an i AF. Following these lines of research, we plan to investigate incremental techniques for checking totality, determinism, and functionality of goal arguments in dynamic i AFs.

References Alfano, G.; Calautti, M.; Greco, S.; Parisi, F.; and Trubitsyna, I. 2020a. Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), 33 43. Alfano, G.; Cohen, A.; Gottifredi, S.; Greco, S.; Parisi, F.; and Simari, G. R. 2020b. Dynamics in Abstract Argumentation Frameworks with Recursive Attack and Support Relations. In Proceedings of the 24th European Conference on Artiﬁcial Intelligence (ECAI), 577 584. Alfano, G.; and Greco, S. 2021. Incremental Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks. IEEE Intelligent Systems, 36(2): 6 12. Alfano, G.; Greco, S.; and Parisi, F. 2017. Efﬁcient Computation of Extensions for Dynamic Abstract Argumentation Frameworks: An Incremental Approach. In Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 49 55. Alfano, G.; Greco, S.; and Parisi, F. 2018a. Computing Extensions of Dynamic Abstract Argumentation Frameworks with Second-Order Attacks. In Proceedings of the 22nd International Database Engineering & Applications Symposium (IDEAS), 183 192. ACM. Alfano, G.; Greco, S.; and Parisi, F. 2018b. A metaargumentation approach for the efﬁcient computation of stable and preferred extensions in dynamic bipolar argumentation frameworks. Intelligenza Artiﬁciale, 12(2): 193 211. Alfano, G.; Greco, S.; and Parisi, F. 2019. An Efﬁcient Algorithm for Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks. In Proceedings of the Twenty Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 18 24. Alfano, G.; Greco, S.; and Parisi, F. 2020. Computing Skeptical Preferred Acceptance in Dynamic Argumentation Frameworks with Recursive Attack and Support Relations. In Proceedings of the 8th International Conference on Computational Models of Argument (COMMA), 67 78. Alfano, G.; Greco, S.; and Parisi, F. 2021. Incremental Computation in Dynamic Argumentation Frameworks. IEEE Intelligent Systems. Alfano, G.; Greco, S.; Parisi, F.; Simari, G. I.; and Simari, G. R. 2018. An Incremental Approach to Structured Argumentation over Dynamic Knowledge Bases. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), 78 87. AAAI Press. Alfano, G.; Greco, S.; Parisi, F.; Simari, G. I.; and Simari, G. R. 2021a. Incremental computation for structured argumentation over dynamic De LP knowledge bases. Artiﬁcial Intelligence, 300: 103553. Alfano, G.; Greco, S.; Parisi, F.; and Trubitsyna, I. 2021b. Argumentation Frameworks with Strong and Weak Constraints: Semantics and Complexity. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 6175 6184. Alfano, G.; Greco, S.; Parisi, F.; and Trubitsyna, I. 2021c. Incomplete Argumentation Frameworks:

Properties and Complexity (Technical Report). http://dx.doi.org/10.13140/RG.2.2.28866.09926. Amgoud, L.; and Cayrol, C. 1998. On the Acceptability of Arguments in Preference-based Argumentation. In Proceedings of the Fourteenth Conference on Uncertainty in Artiﬁcial Intelligence (UAI), 1 7. Arieli, O. 2015. Conﬂict-free and conﬂict-tolerant semantics for constrained argumentation frameworks. Journal of Applied Logic, 13(4): 582 604. Atkinson, K.; Baroni, P.; Giacomin, M.; Hunter, A.; Prakken, H.; Reed, C.; Simari, G. R.; Thimm, M.; and Villata, S. 2017. Towards Artiﬁcial Argumentation. Artiﬁcial Intelligence Magazine, 38(3): 25 36. Baumeister, D.; J arvisalo, M.; Neugebauer, D.; Niskanen, A.; and Rothe, J. 2021. Acceptance in incomplete argumentation frameworks. Artiﬁcial Intelligence, 103470. Baumeister, D.; Neugebauer, D.; and Rothe, J. 2018. Credulous and Skeptical Acceptance in Incomplete Argumentation Frameworks. In Proceedings of the 7th International Conference on Computational Models of Argument (COMMA), 181 192. Baumeister, D.; Neugebauer, D.; Rothe, J.; and Schadrack, H. 2018. Veriﬁcation in incomplete argumentation frameworks. Artiﬁcial Intelligece, 264: 1 26. Bench-Capon, T.; and Dunne, P. E. 2007. Argumentation in Artiﬁcial Intelligence. Artif. Intell., 171: 619 641. Brewka, G.; Strass, H.; Ellmauthaler, S.; Wallner, J. P.; and Woltran, S. 2013. Abstract Dialectical Frameworks Revisited. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 803 809. Brewka, G.; and Woltran, S. 2010. Abstract Dialectical Frameworks. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR). Caminada, M. 2006. Semi-Stable Semantics. In Proceedings of the 1st International Conference on Computational Models of Argument (COMMA), 121 130. Caminada, M. 2007. Comparing two unique extension semantics for formal argumentation: ideal and eager. In Proceedings of the 19th Belgian-Dutch conference on artiﬁcial intelligence (BNAIC), 81 87. Cayrol, C.; Fandinno, J.; del Cerro, L. F.; and Lagasquie Schiex, M. 2018. Structure-Based Semantics of Argumentation Frameworks with Higher-Order Attacks and Supports. In Proceedings of the 7th International Conference on Computational Models of Argument (COMMA), 29 36. Cohen, A.; Gottifredi, S.; Garcia, A. J.; and Simari, G. R. 2015. An approach to abstract argumentation with recursive attack and support. J. of Applied Logic, 13(4): 509 533. Coste-Marquis, S.; Devred, C.; Konieczny, S.; Lagasquie Schiex, M.; and Marquis, P. 2007. On the merging of Dung s argumentation systems. Artif. Intell., 171(10-15): 730 753. Coste-Marquis, S.; Devred, C.; and Marquis, P. 2006. Constrained Argumentation Frameworks. In Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR), 112 122.

Dimopoulos, Y.; Mailly, J.; and Moraitis, P. 2018. Control Argumentation Frameworks. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 4678 4685. Doutre, S.; and Mailly, J. 2018. Constraints and changes: A survey of abstract argumentation dynamics. Argument & Computation, 9(3): 223 248. Dung, P.; Mancarella, P.; and Toni, F. 2007. Computing ideal sceptical argumentation. Artiﬁcial Intelligence, 171(10-15): 642 674. Dung, P. M. 1995. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artiﬁcial Intelligence, 77: 321 358. Dung, P. M.; and Thang, P. M. 2010. Towards (Probabilistic) Argumentation for Jury-based Dispute Resolution. In Proceedings of the 3th International Conference on Computational Models of Argument (COMMA), 171 182. Dunne, P. E.; and Wooldridge, M. 2009. Complexity of Abstract Argumentation. In Argumentation in Artiﬁcial Intelligence, 85 104. Springer. Fazzinga, B.; Flesca, S.; and Furfaro, F. 2018. Credulous and skeptical acceptability in probabilistic abstract argumentation: complexity results. Intelligenza Artiﬁciale, 12(2): 181 191. Fazzinga, B.; Flesca, S.; and Furfaro, F. 2019. Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence. Artiﬁcial Intelligence, 268: 1 29. Fazzinga, B.; Flesca, S.; and Furfaro, F. 2020. Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks. In Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 1712 1718. Fazzinga, B.; Flesca, S.; and Parisi, F. 2015. On the Complexity of Probabilistic Abstract Argumentation Frameworks. ACM Transactions on Computational Logic, 16(3): 22:1 22:39. Fazzinga, B.; Flesca, S.; and Parisi, F. 2016. On efﬁciently estimating the probability of extensions in abstract argumentation frameworks. International Journal of Approximate Reasoning, 69: 106 132. Gaignier, F.; Dimopoulos, Y.; Mailly, J.; and Moraitis, P. 2021. Probabilistic Control Argumentation Frameworks. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 519 527. Gottifredi, S.; Cohen, A.; Garcia, A. J.; and Simari, G. R. 2018. Characterizing acceptability semantics of argumentation frameworks with recursive attack and support relations. Artiﬁcial Intelligence, 262: 336 368. Greco, S.; and Parisi, F. 2016a. Efﬁcient Computation of Deterministic Extensions for Dynamic Abstract Argumentation Frameworks. In Proc. of 22nd European Conference on Artiﬁcial Intelligence (ECAI), 1668 1669. Greco, S.; and Parisi, F. 2016b. Incremental Computation of Deterministic Extensions for Dynamic Argumentation Frameworks. In Proc. of 15th European Conference on Logics in Artiﬁcial Intelligence (JELIA), 288 304.

Hunter, A. 2012. Some Foundations for Probabilistic Abstract Argumentation. In Proceedings of the 4th International Conference on Computational Models of Argument (COMMA), 117 128. J arvisalo, M. 2018. SAT for Argumentation. In Proceedings of the International Workshop on Systems and Algorithms for Formal Argumentation (SAFA), volume 2171, 1 3. Li, H.; Oren, N.; and Norman, T. J. 2011. Probabilistic Argumentation Frameworks. In Proceedings of the First International Workshop on Theorie and Applications of Formal Argumentation (TAFA), 1 16. Mailly, J. 2020. Possible Controllability of Control Argumentation Frameworks. In Proceedings of the 8th International Conference on Computational Models of Argument (COMMA), 283 294. Mantadelis, T.; and Bistarelli, S. 2020. Probabilistic abstract argumentation frameworks, a possible world view. International Journal of Approximate Reasoning, 119: 204 219. Modgil, S.; and Prakken, H. 2013. A general account of argumentation with preferences. Artiﬁcial Intelligence, 195: 361 397. Neugebauer, D.; Rothe, J.; and Skiba, K. 2021. Complexity of Nonemptiness in Control Argumentation Frameworks. In Proceedings of the 16th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 117 129. Niskanen, A.; Neugebauer, D.; and J arvisalo, M. 2020. Controllability of Control Argumentation Frameworks. In Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI), 1855 1861. Nouioua, F. 2013. AFs with Necessities: Further Semantics and Labelling Characterization. In Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM), 120 133. Nouioua, F.; and Risch, V. 2011. Argumentation Frameworks with Necessities. In Proceedings of the International Conference on Scalable Uncertainty Management (SUM). Odekerken, D.; Borg, A.; and Bex, F. 2020. Estimating Stability for Efﬁcient Argument-Based Inquiry. In Proceedings of the 8th International Conference on Computational Models of Argument (COMMA), 307 318. Papadimitriou, C. H. 1994. Computational complexity. Addison-Wesley. Rienstra, T. 2012. Towards a Probabilistic Dung-style Argumentation System. In Proceedings of the First International Conference on Agreement Technologies (AT), 138 152. Simari, G. R.; and Rahwan, I., eds. 2009. Argumentation in Artiﬁcial Intelligence. Springer. Valiant, L. G. 1979. The Complexity of Computing the Permanent. Theoretical Computer Science, 8: 189 201. Villata, S.; Boella, G.; Gabbay, D. M.; and van der Torre, L. W. N. 2012. Modelling defeasible and prioritized support in bipolar argumentation. Annals of Mathematics and Artiﬁcial Intelligence, 66(1-4).