# featured_argumentation_framework_semantics_and_complexity__32ee90c3.pdf

Featured Argumentation Framework: Semantics and Complexity

Gianvincenzo Alfano , Sergio Greco , Francesco Parisi and Irina Trubitsyna DIMES Department, University of Calabria, Rende, Italy {g.alfano, greco, fparisi, i.trubitsyna}@dimes.unical.it

Dung s Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning tasks more intuitive and/or expressive. We present a novel extension of AF called Featured AF (FAF), where each argument has associated a set of features expressed by means of unary and binary facts. In such a context, a query is expressed by means of a conjunctive relational calculus formula which is evaluated over the extensions of the FAF. Then, this framework is further expanded into the so-called Extended FAF (EFAF), where a ﬁrst-order logic formula (FOL) is used for reasoning over feasible subframeworks that satisfy the FOL formula and minimally differ from the original framework. We investigate the computational complexity of veriﬁcation and acceptance problems under several semantics and show that incomplete AF (i AF) frameworks, including correlated i AF and constrained i AF, are special cases of EFAF.

1 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]. Argumentation has applications in several contexts, e.g. modeling dialogues, negotiation [Dimopoulos et al., 2019], persuasion [Prakken, 2009], and process mining [Fazzinga et al., 2022b]. 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 role 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), and stable (st) [Dung, 1995] have been deﬁned for AF, leading to the characterization of σ-extensions, that intu-

Figure 1: AF Λ of Example 1.

itively consist of the sets of arguments that can be collectively accepted under semantics σ {gr, co, st, pr}. Various proposals have been made to extend the Dung s 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 with recursive attacks and supports [Cohen et al., 2015; Gottifredi et al., 2018; Cayrol et al., 2018; Alfano et al., 2024a], Dialectical framework [Brewka et al., 2013], AF with preferences [Amgoud and Cayrol, 1998; Modgil and Prakken, 2013; Alfano et al., 2023b] and constraints [Coste Marquis et al., 2006; Arieli, 2015; Alfano et al., 2023c; Alfano et al., 2024b], 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; Baumeister et al., 2021], and probabilistic AF (Pr AF), where arguments and attacks are associated with a probability [Dung and Thang, 2010; Li et al., 2011; Hunter, 2012; Alfano et al., 2023a; Fazzinga et al., 2022a]. Our example concerns opinions about air pollution.

Example 1. Consider a scenario in which three air pollution experts, Alice (a), Bob (b), and Carl (c), are asked to propose short-, medium-, and long-term solutions to the problem. The experts have different general opinions: Alice supports industrial pollution regulation policies, Bob supports trafﬁc limitation policies, and Carl promotes changes in human habits. Each expert expresses opinions for the short, medium, and long term, represented by the arguments x1, x2, x3, respectively, where x denotes the ﬁrst letter of the experts name. These 9 arguments can be summarized as follows: a1: Impose immediate ﬁnes and sanctions on industries exceeding pollution limits; a2: Enforce stricter industrial regulations with compliance mechanisms;

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

a3: Mandate the adoption of green technologies to achieve sustainable industrial practices; b1: Implement congestion charges and restrict access for highpolluting vehicles; b2: Expand public transportation to reduce private vehicle use; b3: Redesign cities to prioritize pedestrians, cyclists, and electric vehicles; c1: Launch awareness campaigns to encourage reduced car usage and energy conservation; c2 Integrate environmental education into schools and workplaces; c3: Promote societal norms through incentives for ecofriendly behavior and penalties for unsustainable actions. The following attacks can be derived from considerations made by the three experts. Short-term: (a1, b1),(b1, c1),(c1, a1),(c1, b1); Medium-term: (a2, b2),(b2, c2),(c2, a2),(b2, a2); Long-term: (a3, b3),(b3, c3),(c3, a3),(c3, b3); Cross-timeframes: (a1, c3),(c3, b2),(b2, c1), (b3, c1). The derived AF Λ (see Figure 1) has two stable (and preferred) extensions: E1={a1, b2, a3} and E2 = {c1, c2, c3}.

The previous example shows how possible air pollution policies can be deﬁned using AF under stable (and preferred) semantics. However, by modeling the problem by means of AF, we neglect important information that can be very useful. In our example, we disregard useful information about the text associated with the argument, the author (and her sex and age), and the type of policy (short-, medium-, long-term). Generally, an argument is associated with a sentence with a proper meaning. This means that, in adopting the abstraction of AF, a lot of relevant information, such as the argument s text, the author s id and gender, the date it was introduced, the topic (e.g. what the argument is about), the polarity (e.g. whether the sentence conveys a positive, negative or neutral sentiment), the polarity rating, the sentence style (e.g. veracity, sarcasm, irony), and many others, are lost. As, in our opinion, these features should be made explicit and appropriately used, in this paper we propose an extension of AF called Featured Argumentation Framework (FAF), where arguments might have associated features expressed by means of (ﬁrst-order unary and binary) facts. Thus, the knowledge is represented through an underlying AF and a set of facts representing the features associated with arguments and with the AF s topology.

Example 2. Considering Example 1, each argument could have associated features such as author (e.g. author (a1, Alice)), text (e.g. text (c2, integrate environmental education into schools and workplaces )), supported policy, (e.g. policy (b1, trafﬁc limitation)), term time (e.g. term (c3, long)).

In such a context, users pose queries consisting of conjunctive relational calculus formulae such as checking whether there exists an extension containing only arguments concerning policies proposed by the same expert (E2 is an extension of such kind in Example 1). Herein, a query is evaluated with respect to the extensions of the underlying AF, each consisting of a subset of arguments with the associated features. As

FAF may have multiple extensions, we study the credulous and skeptical acceptance of queries (a.k.a. brave and cautious acceptance, respectively, in the database (DB) context). Consider now the case where there are two politicians, the former is interested only in short-term policies, the latter is interested only in policies regarding pollution regulations and trafﬁc limitations. For reasoning about the ﬁrst context (concerning short-term policies), we should focus on the subframework containing only the arguments a1, b1 and c1, whereas for the second context we should consider the subframework containing only the arguments whose only policies are pollution regulation and trafﬁc limitation. To this end, we propose an Extended FAF (EFAF), where a First Order Logic (FOL) formula (also called constraint) is added to the FAF. The FOL formula is used to extract FAF subframeworks (subframeworks for short), that are subsets of the original FAF (i.e. the original EFAF without the constraint), that satisfy the constraints and differ from the original FAF by a minimal set or a minimum number of arguments and attacks. Considering a multi-agent context, the FAF represents the general knowledge shared by all agents, whereas each constraint represent the knowledge of a given agent.

Example 3. The subframework containing only short-term policies can be deﬁned by means of the FOL formula X.term(X, short), whereas the subframework considering only arguments denoting policies regarding both pollution regulation and trafﬁc limitation can be deﬁned by means of the FOL formula X.policy(X, pollution regulation) policy(X, trafﬁc limitation). On the other side, the formula X.policy(X, pollution regulation) X.policy(X, trafﬁc limitation) allows determining two alternative subframeworks.

The FOL formula can be viewed as an integrity constraint used to guarantee that available arguments and features correctly model the outside world. There is a tight connection with the Knowledge Base (KB) ﬁeld as the facts denoting features and the AF topology represents the input database, C represents a set of constraints, and the subframeworks correspond to the subsets of the input facts that satisfy C and minimally differ from the source database (called repairs in the KB context). Dealing with repairs in KBs is a critical area in knowledge management and AI [Arenas et al., 1999; Greco et al., 2001; Bertossi, 2011]. In our setting, a subframework satisﬁes the constraint and differs from the original FAF by a minimal set or a minimum number of arguments and attacks these two minimality criteria are called set and cardinality (subframework) semantics, respectively. More speciﬁcally, a subframework is obtained by deleting a minimal set or a minimal number of arguments and attacks, so that the FOL formula is satisﬁed w.r.t the resulting FAF. Clearly, if deleting an argument then related attacks and features are deleted as well. Therefore, an EFAF can be seen as representative of a set of FAFs obtained by extracting feasible subframeworks. Then, its semantics can be deﬁned in terms of the semantics of its subframeworks. This means that, similarly to other frameworks previously introduced in the literature (e.g. incomplete AF, probabilistic AF), the subframeworks can be seen

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

as possible worlds. Thus, classical veriﬁcation and acceptance problems (i.e. credulous and skeptical acceptance) need to be reconsidered in light of the presence of possible worlds, leading to the concepts of possible and necessary veriﬁcation, as well as possible and necessary credulous/skeptical acceptance (cf. Deﬁnitions 7 and 8). Notice that, although the introduction of features allows knowing information about the content and meaning of arguments, their acceptance continues to be determined by the relationships between arguments, rather than the features content.

Contributions. Our main contributions are as follows. We introduce an extension of AF called Featured AF (FAF) where each argument has a set of associated features deﬁned through unary and binary facts. Queries over FAF are expressed by means of conjunctive relational calculus formulae which are evaluated over the FAF s extensions. We show that the complexity of acceptance problems in FAF does not increase with respect to that of AF. We further extend the FAF framework, leading to the socalled Extended FAF (EFAF), by adding i) features describing the topology of the underlying AF, and ii) a FOL formula which is used to select subframeworks (i.e. FAFs) satisfying the formula and differing from the original framework by a minimal set (or a minimal number) of elements (i.e. arguments and attacks). We introduce the veriﬁcation and acceptance problems for EFAF and thoroughly investigate the complexity of these problems. A summary of our results for the veriﬁcation and possible/necessary credulous/skeptical acceptance under argumentation semantics σ {gr, co, pr, st} and under set and cardinality subframework semantics are reported in Table 1 and Table 2, respectively. It turns out that standard reasoning problems in EFAF are strictly harder than the corresponding ones in incomplete AF [Baumeister et al., 2021], correlated i AF [Fazzinga et al., 2021a; Fazzinga et al., 2021b] and constrained i AF [Mailly, 2024]. Consistently with our complexity results, we show that incomplete AF, correlated and constrained i AF can be viewed as special cases of EFAF, in the sense that each of them can be rewritten into an extensions-equivalent EFAF, under both set and cardinality subframework semantics.

We assume the reader is familiar with the basic concepts of computational complexity.

2 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 ﬁxed):

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; grounded (gr) iff it is -minimal.

In the following, if not speciﬁed otherwise, σ denotes any semantics in {gr, co, st, pr}. 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]. For any AF Λ, it holds that st(Λ) pr(Λ) co(Λ), and gr(Λ) co(Λ). For any AF Λ = A, R and set of arguments S A, we use Λ S = A S, R (S S) to denote the AF obtained by projecting Λ over the arguments in S; we use σ(Λ) S = {E S | E σ(Λ)} to denote the set of the intersections of the extensions in σ(Λ) and S. Given two AFs Λ = A, R and Λ = A , R , we say that: (i) Λ is included in Λ (denoted as Λ Λ) iff A A and R R, that is, Λ can be obtained from Λ through the deletion of a (possibly empty) set of arguments and attacks; (ii) Λ is strictly included in Λ (denoted as Λ Λ) iff Λ Λ and Λ = Λ, that is, Λ can be obtained from Λ through the deletion of a non-empty set of arguments and attacks. For any AF Λ = A, R , semantics σ, and argument 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 one (resp. every) σ-extension of Λ. We use CAσ (resp. SAσ), or CA (resp. SA) whenever σ is understood, to denote the credulous (resp. skeptical) acceptance problem, that is, the problem of deciding whether an argument 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, d}, E2 = {b, d} and E3 = {d}. That is, co(Λ) = {E0, E1, E2, E3}. E0 is the grounded extension, E1 and E2 are stable (and preferred) extensions. Thus, a, b, d are credulously accepted for all semantics except the grounded; only d is skeptically accepted under stable and preferred semantics.

3 Featured AF

We now introduce an extension of Dung s AF that consists of adding features associated with the arguments, leading to the concept of the Featured Argumentation Framework (FAF).

Syntax. We assume to have distinct countable sets of arguments A, constants D, variables V, and (unary and binary) base predicates Pb. Constants can be either natural numbers or alphanumeric strings starting with a lower-case letter, whereas variables are denoted by alphanumeric strings starting with an upper-case letter. We also assume to have the

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

predeﬁned (or built-in) unary predicate arg. P denotes the set of all predicates (base and built-in). Arguments, constants and variables are terms. An atom is of the form p(a, b) (resp. p(a)), where p is a binary (resp. unary) predicate symbol and a, b are terms. Unary atoms take values from A, (base) binary atoms take values from A D. A variable-free base atom is called a fact. Given a set A of arguments, we use Arg A to denote the set of built-in facts {arg(a) | a A}.

Deﬁnition 1. A Featured AF (FAF) is a triple Ω= A, R, F where A, R is an AF and F is a ﬁnite set of base facts.

For an FAF A, R, F , the set of base and built-in facts will be denoted by FA = F Arg A. The concept of inclusion deﬁned earlier for AF can be immediately extended to FAF. Given two FAFs Ωand Ω , we write Ω Ω(resp. Ω Ω) if Ω can be obtained from Ω through the deletion of a possibly empty (resp. non-empty) set of arguments (as well as the related base facts) and attacks. That is, Ω Ωiff A A, R R, and F = F A ; moreover, Ω Ωiff Ω Ωand Ω is not equal to Ω.

Semantics. Given a set of (base and built-in) facts F and a set of arguments S, we use F S = {p(a) | p(a) F a S} {p(a, b) | p(a, b) F a S} to denote the projection of F over S. That is, F S contains only the facts in F referring to the arguments in S.

Deﬁnition 2 (Semantics). Given an FAF Ω= A, R, F and a semantics σ, a σ-extension for Ωis any set E σ( A, R ).

As usual, the set of σ-extensions for Ωis denoted by σ(Ω). Thus, we have that σ( A, R, F ) = σ( A, R ). A query is a conjunctive relational calculus query deﬁned over the database FA, that is, it only uses the predicate symbols contained in FA. A query is said to be boolean if all variables are (existentially) quantiﬁed. For instance, the boolean query arg(a) checks the acceptance of argument a.

Deﬁnition 3 (Query acceptance). For any FAF Ω = A, R, F , semantics σ, and boolean query q, we say that q is (i) credulously accepted if there exists a set E σ(Ω) such that F A E |= q,1 and (ii) skeptically accepted if for every set E σ(Ω), F A E |= q holds.

Example 5. Consider the FAF Ω= A, R, F obtained from the AF A, R of Example 1, where F contains the following base facts {author(ai, Alice), author(bi, Bob), author(ci, Carl) | i [1, 3]} {term(x1, short), term(x2, medium), term(x3, long) | x {a, b, c}}. Assume we are interested to know whether there are stable extensions containing at least one short-term argument from Alice, thus we interested in the answer to the query q = X.author(X, Alice) term(X, short). The answer to q is yes as there exists a stable-extension E1 = {a1, b2, a3} for Ωand F A E contains the atoms author(a1, Alice) and term(a1, short). Although q is credulously accepted under stable semantics, it is not skeptically accepted, as there exists a stable-extension E2 = {c1, c2, c3} for Ωs.t. F A E |= q.

1Here F A E denotes the set (F A) E.

We use CAσ (resp. SAσ), to denote the credulous (resp. skeptical) acceptance problem in FAF under semantics σ, that is, the problem of deciding whether a boolean query q is credulously (resp. skeptically) accepted.

Proposition 1. For FAF, it holds that:

CAσ is i) in PTIME for σ = gr, and ii) NP-complete for σ {co, st, pr}; SAσ is i) in PTIME for σ {gr, co}, ii) co NPcomplete for σ = st, and iii) Πp 2-complete for σ = pr.

Thus, the complexity of acceptance problems in FAF and AF coincides.

4 Extended FAF

We now introduce the Extended Featured Argumentation Framework (EFAF), that extends FAF with a FOL formula to be satisﬁed. The formula, deﬁned on the argument features and the topology of the underlying AF, is used to deﬁne the subframeworks the user is interested in.

Syntax. Given an FAF Ω= A, R, F , we assume to also have the built-in binary predicate att, denoting attacks among arguments, and the derived binary predicates path, even-path and odd-path denoting paths over the argumentation graph A, R ; all these predicates take values from A A. Hereinafter, we use Att R to denote the set {att(a, b) | (a, b) R , and P to denote the set of all predicates (base, built-in, and derived ones). We use λ to denote the ﬁrstorder language using base, built-in and derived predicates, and terms (i.e. arguments, constants and variables).

Deﬁnition 4. An extended FAF (EFAF) is a tuple = A, R, F, C where A, R, F is an FAF and C is a ﬁrst-order formula deﬁned over λ.

We use F AR = F Arg A Att R to denote the set containing base feature facts and built-in facts describing the topology of the underlying graph. Clearly, F AR extends the set F A deﬁned earlier for FAF. In the following, for the sake of presentation, the formula C will be often represented as a set of formulae {c1, ..., cn} corresponding to c1 cn.

Semantics. We start by deﬁning the satisfaction of the formula C with respect to the underlying FAF A, R, F . A base or built-in fact p(a, b) (resp. p(a)) is satisﬁed w.r.t. a EFAF = A, R, F, C if it occurs in FAR. Moreover, a derived fact path(a, b) (resp. even-path(a, b), odd-path(a, b)) is satisﬁed w.r.t. if there exists a path (resp. even simple path, odd simple path) from a to b in the underlying AF A, R . The role of the logical formula C in is to represent a constraint (or a set of constraints) to be satisﬁed by F AR. Intuitively, if the logical formula C is not satisﬁed, then the underlying FAF should be revised by computing subframeworks, that is, by (minimally) modifying the topology of the AF through the deletion of arguments and attacks, so that the formula is satisﬁed. Clearly, when deleting arguments, related features and attacks are deleted as well. In the following, we assume that the formula C is satisﬁable, that is that there exists an FAF A, R, F such that FAR |= C.

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

Deﬁnition 5 (Subframework). Given an EFAF = A, R, F, C , a set-subframework (resp. cardinalitysubframework) for is an FAF A , R , F A, R, F such that, (i) F AR A |= C, and (ii) there is no FAF A , R , F A, R, F such that F AR A |= C and A , R , F A , R , F (resp. |A | + |R | < |A | + |R |).

Thus, a set-subframework (s-subframework for short) is obtained by deleting a minimal set of arguments and attacks, whereas a cardinality subframework (c-subframework) is obtained by deleting a minimum number of arguments and attacks. Observe that, in computing subframeworks, feature facts are implicitly deleted through the deletion of the related arguments. This is line with repairing strategies exploited in databases, where the inconsistency of an attribute leads to the deletion of an entire tuple [Arenas et al., 1999]. It is worth noting that the cardinality-based distance is able to discriminate between arguments and attacks, in the sense that the weight associated with an argument removal is also related to its degree (i.e., incoming/outgoing attacks): removing an argument with degree d has weight d + 1.

Example 6. Consider the EFAF = A, R, F, C obtained from the FAF A, R, F of Example 5, where the FOL formula C = X.term(X, short), captures the subframeworks containing only short-term policies. The unique subframework (under set or cardinality semantics) is obtained by deleting every argument x such that term(x, short) is false, and its unique stable extension is {c1}. Assume now we want to ﬁx exactly one term policy (either short, medium, or long), independently of the actual term s value. The FOL formula C = X, Y, Z, Z term(X, Z) term(Y, Z ) Z = Z allows to identify three ssubframeworks obtained by keeping only the arguments sharing the same term s value.

The set of s-subframeworks (resp. c-subframeworks) for an EFAF is denoted by S( ) (resp. C( )). The semantics of is given by the set of its (FAF) subframeworks. We say that a subframework for is obtained under set or cardinality semantics if it belongs to S( ) or C( ), respectively. Notice that EFAF without base predicates is similar to correlated/constrained incomplete AF [Fazzinga et al., 2021a; Fazzinga et al., 2021b; Mailly, 2020], though the formulae deﬁned in those works are propositional and allow only built-in predicates. However, the aim is different, as we are interested in dealing with subframeworks (which minimally differ from the original framework), whereas in the abovementioned works all completions are ﬁrst-class citizens.

5 Computational Complexity

We investigate the complexity of fundamental reasoning problems for EFAF. In particular, we study the veriﬁcation, existence, and credulous/skeptical acceptance problems, that are usually considered for analyzing the complexity of argumentation frameworks. We start with a lemma stating that the satisfaction of the logical formula C can be checked in PTIME in the size of the active domain consisting of constant values and arguments.

AF i AF ci AF EFAF σ Vσ PVσ NVσ PVσ NVσ c-PVσ s-PVσ c-NVσ s-NVσ gr P P P NP-c co NP-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c co P P P NP-c co NP-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c st P P P NP-c co NP-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c pr co NP-c Σp 2-cco NP-c Σp 2-c co NP-c Θp 2-h,Σp 2 Σp 2-c Θp 2-c Πp 2-c

Table 1: Complexity of the veriﬁcation problems for AF, i AF, ci AF, and EFAF under semantics σ {gr, co, pr, st}. For any complexity class C, C-c (resp. C-h) means C-complete (resp. C-hard). An interval C-h, C means C-hard and in C .

Notice that our results refer to data complexity, where a common assumption is that the number of variables in a formula is constant and thus the grounding is still in PTIME. Lemma 1. Given an EFAF = A, R, F, C and a set A A, checking whether (FAR) A |= C can be done in PTIME.

Observe that a given EFAF may admit zero, one, or multiple subframeworks. Subframework existence, veriﬁcation, and acceptance problems can be deﬁned analogously to those deﬁned for i AF [Baumeister et al., 2018; Baumeister et al., 2021]. In fact, roughly speaking, the main differences with respect to i AF is that subframeworks correspond to completions which must satisfy a minimality criteria (either set or cardinality subframeworks semantics).

5.1 Existence Problems We start by introducing the existence problems under set and cardinality subframeworks semantics. We use δ {c, s} to refer a subframeworks semantics: c standing for cardinality and s for set. Deﬁnition 6. Let δ {c, s}, δ-EX is the problem of checking whether there exists a δ-subframework for a given EFAF. In our running example, it is easy to see that both problems are true. In general, deciding subframework existence is hard. Theorem 1. s-EX and c-EX are NP-complete.

5.2 Veriﬁcation Problems We now characterize the complexity of the veriﬁcation problems for EFAF, which are formally deﬁned in what follows. Deﬁnition 7. Let = A, R, F, C be an EFAF, S A a set of arguments, σ {gr, co, pr, st} an argumentation semantics, and δ {c, s} a subframeworks semantics. Then: the δ-possible veriﬁcation problem, denoted as δ-PVσ, is the problem of checking whether S is a σ-extension in any δ-subframework for ; the δ-necessary veriﬁcation problem, denoted as δ-NVσ, is the problem of checking whether S is a σ-extension in all δ-subframeworks for . Observe that for an EFAF of the form A, R, , , that semantically coincides with the AF A, R , s-PVσ = c-PVσ = s-NVσ = c-NVσ, which in turns coincide with the standard veriﬁcation problem for AF, that is checking whether a given set S is a σ-extension of (the subframework) A, R . The following theorem states that the complexity of the veriﬁcation problem for EFAF is generally harder than that

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

for AF, whose complexity is summarized in the second column of Table 1 [Dvorak and Dunne, 2017]. Moreover, the results for the cardinality-based semantics are generally lower than those for the set-based semantics. Theorem 2. c-PVσ is i) Θp 2-complete for σ {gr, co, st}, and ii) Θp 2-hard and in Σp 2 for σ = pr; s-PVσ is Σp 2-complete for σ {gr, co, st, pr}; c-NVσ is Θp 2-complete for σ {gr, co, st, pr}; s-NVσ is Πp 2-complete for σ {gr, co, st, pr}. Notably, the veriﬁcation problem for EFAF is computationally harder than that for constrained i AF (ci AF) [Mailly, 2020] (and thus i AF) under all the considered (argumentation and subframework) semantics, except for δ-PVpr (with δ {c, s}) for which the veriﬁcation problems for EFAF and ci AF belong to the same class (Σp 2). On the other side, it can be shown that the complexity of veriﬁcation for FAF is as that of AF, as any FAF coincides with its unique subframework and thus FAF veriﬁcation collapses to AF veriﬁcation.

5.3 Acceptance Problems For AFs, the complexity of the credulous and skeptical acceptance problems has been investigated in [Dung, 1995] for the grounded semantics, in [Dimopoulos and Torres, 1996] for the stable semantics, and in [Dimopoulos and Torres, 1996; Dunne and Bench-Capon, 2002] for the preferred semantics. The complexity results for AFs are summarized in the second and third column of Table 2. The following deﬁnition generalizes that of the credulous and skeptical acceptance problems for AF to the case of EFAF, analogously to what is done for (c)i AF. Deﬁnition 8. Let = A, R, F, C be an EFAF, q a boolean query, σ {gr, co, pr, st} an argumentation semantics, and δ {c, s} a subframework semantics. Then: the δ-possible credulous acceptance problem, denoted as δ-PCAσ, is the problem of checking whether q is credulously accepted in at least one δ-subframework for ; the δ-possible skeptical acceptance problem, denoted as δ-PSAσ, is the problem of checking whether q is skeptically accepted in at least one δ-subframework for ; the δ-necessary credulous acceptance problem, denoted as δ-NCAσ, is the problem of checking whether q is credulously accepted in all δ-subframeworks for ; the δ-necessary skeptical acceptance problem, denoted as δ-NSAσ, is the problem of checking whether q is skeptically accepted in all δ-subframeworks for . The next theorem provides a tight characterization of the complexity for all the above-deﬁned acceptance problems. Theorem 3. c-PCAσ is Θp 2-complete for any σ {gr, co, st, pr}; s-PCAσ is Σp 2-complete for any σ {gr, co, st, pr}; c-NCAσ is i) Θp 2-complete for σ = gr, and ii) Πp 2-complete for any σ {co, st, pr}; s-NCAσ is Πp 2-complete for any σ {gr, co, st, pr}; c-PSAσ is i) Θp 2-complete for any σ {gr, co}, and ii) Σp 2-complete for any σ {st, pr};

Figure 2: i AF of Example 7 (dashed elements are uncertain).

s-PSAσ is i) Σp 2-complete for any σ {gr, co, st}, and ii) Σp 3-complete for σ = pr; c-NSAσ is i)Θp 2-complete for any σ {gr, co, st}, and ii) Πp 2-complete for σ = pr. s-NSAσ is Πp 2-complete for any σ {gr, co, st, pr}.

In brief, except for the 7 cases highlighted with an asterisk ( ) in Table 2 for which the complexity of EFAF is the same as that of (c)i AF, for all the other 25 cases considered the complexity of EFAF is higher than that of (c)i AF, even under cardinality subframework semantics whose complexity is systematically lower than or equal to that of the set semantics.

6 EFAF versus i AF-based Frameworks

As observed earlier, there are some connections between EFAF and i AF [Baumeister et al., 2021]. Acceptance problems are deﬁned similarly, in the sense that the semantics of i AF is deﬁned by the set of completions, whereas that of EFAF is deﬁned by the set of subframeworks (that can be viewed as a subset of completions by assuming arguments/attacks of EFAF to be uncertain). Moreover, EFAF without base features is similar to correlated/constrained i AF [Fazzinga et al., 2021a; Fazzinga et al., 2021b; Mailly, 2020], though the formulae deﬁned in the latter frameworks are propositional and allow only built-in predicates. We investigate the relationship between EFAF and those frameworks, showing that i AF, as well as constrained and correlated i AF, are special cases of EFAF.

6.1 Incomplete Argumentation Framework 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 [Baumeister et al., 2018]. An i AF compa-ctly represents alternative AF scenarios, called completions.

Deﬁnition 9 (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 ).

Observe that there may be completions that do not contain the attacks in R involving uncertain arguments, since those arguments do not belong to the considered completion. The set of completions of i AF Ψ is denoted by comp(Ψ). Veriﬁcation and acceptance problems, originally introduced in [Baumeister et al., 2018; Baumeister et al., 2021], are deﬁned analogously to the ones of EFAF, with the only difference that instead of considering subframeworks and queries, completions and arguments are taken into account.

Example 7. Consider the i AF Ψ = {b, c, d}, {a}, {(a, c), (b, c), (c, d)}, {(a, b)} shown in Figure 2, where arguments b, c, d and attacks (a, c), (b, c) and (c, d) are certain, whereas argument a and attack (a, b) are uncertain. Ψ has 3 completions, that are:

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

AF/FAF i AF/ci AF EFAF σ CAσ SAσ PCAσ NCAσ PSAσ NSAσ c-PCAσ s-PCAσ c-NCAσ s-NCAσ c-PSAσ s-PSAσ c NSAσ s NSAσ

gr P P NP-c co NP-c NP-c co NP-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c co NP-c P NP-c Πp 2-c NP-c co NP-c Θp 2-c Σp 2-c Πp 2-c Πp 2-c Θp 2-c Σp 2-c Θp 2-c Πp 2-c st NP-c co NP-c NP-c Πp 2-c Σp 2-c co NP-c Θp 2-c Σp 2-c Πp 2-c Πp 2-c Σp 2-c Σp 2-c Θp 2-c Πp 2-c pr NP-c Πp 2-c NP-c Πp 2-c Σp 3-c Πp 2-c Θp 2-c Σp 2-c Πp 2-c Πp 2-c Σp 3-c Σp 3-c Πp 2-c Πp 2-c

Table 2: Complexity of possible and necessary credulous/skeptical acceptance under semantics σ {gr, co, pr, st} for AF, FAF, i AF, ci AF, and EFAF. For any complexity class C, C-c means C-complete. All results for EFAF (and FAF) are new. The results with asterisk ( ) refer to cases where the complexity of EFAF is the same as that of (c)i AF; for the other cases, the complexity of EFAF is higher than that of (c)i AF.

Λ1 = {a, b, c, d}, {(a, b), (a, c), (b, c), (c, d)} ; Λ2 = {a, b, c, d}, {(a, c), (b, c), (c, d)} ; and Λ3 = {b, c, d}, {(b, c), (c, d)} . For σ {gr, co, st, pr}, Λ1 (resp. Λ2; and Λ3) has only one extension E1 = {a, d} (resp. E2 = {a, b, d}, E3 = {b, d}). Thus, a, b, d are possibly credulously/skeptically accepted, while only d is necessarily credulously/skeptically accepted.

6.2 Relationship between EFAF and i AF

We start showing that every i AF can be rewritten into an extensions-equivalent EFAF, modulo meta-elements. The equivalence between an i AF Ψ = A, B, R, T and an EFAF = A , R , F, C derived from Ψ is in the sense that (i) A B A and R T R (i.e. arguments and attacks in Ψ also occur in , but may contain additional meta-arguments and meta-attacks), and (ii) for every completion Λ comp(Ψ) there exists an s-subframework Λ S( ) (resp. c-subframework Λ C( )) such that σ(Λ) = σ(Λ ) A B, and vice versa. Such equivalence under the set subframework (resp. cardinality subframework) semantics between an i AF Ψ and a (derived) EFAF is denoted by Ψ s (resp. Ψ c ).

Theorem 4. For any i AF Ψ = A, B, R, T , the EFAF Ψ = AΨ, RΨ, , c1 c2 c3 is such that both Ψ s Ψ and Ψ c Ψ hold, with AΨ = A B {b|b B} {ab|(a, b) R ({a, b} B = )} {ab|(a, b) T}, RΨ = R T; and

a A arg(a) V

(a,b) R, {a,b} A att(a, b);

a B (arg(a) arg(a)) V

(a,b) T att(a, b) arg(ab) V

(a,b) R, {a,b} B = att(a, b) arg(ab);

(a,b) R, a B, b A (arg(a) att(a, b)) V

(a,b) R, a A, b B (arg(b) att(a, b)) V

(a,b) R, {a,b} B (arg(a) arg(b) att(a, b)) V

(a,b) T (att(a, b) arg(a) arg(b)).

Herein, c1 states that certain arguments and certain attacks must belong to all subframeworks. Moreover, c2 states that for any uncertain argument a B (resp. attack (a, b) T), exactly one between a and a (resp. between att(a, b)

and arg(ab)) appears in any subframework (in the formulae above, denotes the XOR operator); the same condition holds for the certain attacks (a, b) such that at least one of its arguments is uncertain in Ψ. Finally, c3 states that certain attacks (a, b) of Ψ such that either a or b is uncertain must belong to a subframework iff both a and b belong to it; also, if an uncertain attack (a, b) T belongs to a subframework then both arguments a and b must belong to it as well.

Example 8. Consider the i AF Ψ of Example 7 (see Figure 2). The EFAF derived from Ψ is Ψ = {a, b, c, d, a, ab, ac}, R T, , c1 c2 c3 where: c1 = arg(b) arg(c) arg(d) att(b, c) att(c, d); c2 = (arg(a) arg(a)) (att(a,b) arg(ab)) (att(a,c) arg(ac)); c3 = arg(a) att(a, c); Ψ has 3 s-subframeworks (being also c-subframeworks): Λ 1 = {a, b, c, d}, {(a, b), (b, c), (a, c), (c, d)} , Λ 2 = {a, b, c, d, ab}, {(b, c), (a, c), (c, d)} , Λ 3 = {a, b, c, d, ab, ac}, {(b, c), (c, d)} , It it easy to see that the set of σ-extensions (with σ {gr, co, st, pr}) of every Λ i is the same as that of Λi (of Example 7), modulo the meta-arguments a, ab, and bc, introduced in the rewriting, for i [1, 3].

6.3 Constrained and Correlated i AF Two extensions of i AF related to our proposals are correlated i AF [Fazzinga et al., 2021a; Fazzinga et al., 2021b] and constrained i AF [Mailly, 2020]. Both frameworks extend i AF by adding a propositional formula which must be satisﬁed by completions, so that instead of considering the whole set of completions, only the ones satisfying the formula (called valid completions) are taken. The main difference between the two proposals is that while correlated i AF considers different fragments of propositional logic (PL), with the aim of studying complexity and expressivity of those fragments, constrained i AF considers general PL formulae. As propositional formulae can be rewritten using minimal sets of operators (e.g. and , or and ), the two proposals are equivalent in the sense that, although constrained i AF is more general, there are fragments of correlated i AF that have the same expressivity of general PL. Thus, hereafter we focus on constrained i AF. Let γA denote the propositional language built over the propositional atoms in {arg(a) | a A} {att(a, b) | a, b, A}, a constrained i AF can be deﬁned as follows.

Deﬁnition 10. A Constrained i AF (ci AF) is a tuple Ψ = A, B, R, T, C , where A, B, R, T is an i AF, and C γA B is a propositional formula (called constraint).

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

The constraint C is used to select a subset of the completions of i AF Ψ. The valid completions are those which satisfy C. The set of valid completions of Ψ is denoted by valid-comp(Ψ). Extending the equivalence relations s and c to ci AF in the obvious way, we have the following. Theorem 5. For any ci AF Ψ = A, B, R, T, C , the EFAF Ψ = AΨ, RΨ, , c1 c2 c3 C is such that both Ψ s Ψ and Ψ c Ψ hold, where AΨ, RΨ, c1, c2, and c3 are as given in Theorem 4.

Example 9. Consider the ci AF Ψ = A, B, R, T, C where A, B, R, T is the i AF of Example 7, and C = arg(a) att(a, b). The EFAF derived from Ψ is Ψ = {a, b, c, d,a, ab, ac}, R T, , c1 c2 c3 C where cis are given in Example 8. The subframeworks of Ψ are Λ 1 and Λ 3 given in Example 8, which correspond one-to-one to the valid completions of ci AF Ψ, modulo meta-elements.

7 Related Work We have already mentioned the relationships between EFAF and KBs repairs [Arenas et al., 1999; Bertossi, 2011; Calautti et al., 2022a; Calautti et al., 2022b]. Computing repairs for AFs which are inconsistent, in the sense that they do not have any accepted argument, has been investigated in [Ulbricht and Baumann, 2019], where restoring consistency is achieved via dropping a minimal set of arguments or attacks. A similar approach has been deﬁned for Assumption-Based Argumentation Frameworks in [Rapberger and Ulbricht, 2024]. In [Takahashi and Miwa, 2023] it is discussed how to make an AF with no stable extensions into one with a stable extension by adding a new argument (called repair ). The connection between Consistent Query Answering for DBs/KBs and argumentation has been investigated in [Croitoru and Vesic, 2013; Mahmood et al., 2025; Bienvenu and Bourgaux, 2020; Mahmood et al., 2024]. [Mahmood et al., 2025] indicates that classical AF semantics can be reduced to DB repairs with functional and inclusion dependencies. It would be interesting to build on [Mahmood et al., 2025] to map FAF to DB, thus storing additional argument features in such a DB and emulating subframeworks. Further related approaches in AF concern those addressing the so-called enforcing problem and minimal change problem dealing with the question of whether it is possible to add (minimal) new information so that a desired set of arguments becomes an extension or at least a subset of one [Baumann, 2012; Kim et al., 2013; Wallner et al., 2017]. These works are all based on the addition of new information. We do not allow modiﬁcations that result in the addition of arguments and attacks, but we are interested in (minimal) removals ensuring satisfaction of user-deﬁned constraints. Finally, the impact of adding or removing an argument on the set of extensions has been studied in [Cayrol et al., 2010]. Extending AF by associating a claim to each argument representing its conclusion has been investigated in [Dvor ak and Woltran, 2020; Dvor ak et al., 2023] where claim-augmented AFs are introduced. A claim-augmented AF can be modeled by a FAF whose set of facts contains assertions associating arguments to claims. Two approaches have been considered for deﬁning claim-augmented AF semantics. The

inherited semantics considers the extensions of the underlying AF before interpreting arguments by their claims, while the claim-level semantics redeﬁnes argumentation semantics in terms of the arguments claims. We follow the inherited approach in deﬁning FAF semantics, as often done in structured argumentation [Modgil and Prakken, 2014; Bondarenko et al., 1993]. As a result, FAF generalizes claimaugmented AF under inherited semantics, as backed by our complexity analysis. Interestingly, also Preference-based AF (PAF) under the preference reduction approach [Amgoud and Cayrol, 2002; Amgoud and Vesic, 2014; Kaci et al., 2021; Bernreiter et al., 2024a; Bernreiter et al., 2024b] can be reduced to EFAF where PAF s critical attacks are tackled similarly to VAF s unsuccessful attacks [Dunne and Bench-Capon, 2004], as shown in what follows. Any VAF A, R, V, VAL, VALPREF can be seen as an EFAF A, R, F, C s.t. F={value(a, VAL(a)) | a A} {pref(u, v) | {u, v} V VALPREF(u, v)}, and C= x,y,u,v. att(x, y) value(x, u) value(y, v) pref(v, u). This way the only subframework corresponds to the AF without unsuccessful attacks, thus emulating VAF semantics. Conversely, VAF cannot encode general FOL constraints of EFAF, as backed by the complexity analysis.

8 Conclusion

We have introduced the Featured AF, which extends AF by allowing arguments features represented as a set of facts and queries allowing us to ask general questions concerning both arguments and features. We have further extended the framework by introducing EFAF that allows FOL constraints to be satisﬁed by subframeworks. For several argumentation semantics, EFAF turns out to be more expressive that i AFbased frameworks such as correlated and constrained AF. In a sense, EFAF can be seen as a general formalism that allows us to express features of well-known frameworks extending AF, such as i AF, correlated and constrained i AF, as well as features that cannot be expressed in AF or even in the extending frameworks, as backed by our complexity analysis. As future work we plan to extend our investigation to other semantics, such as semi-stable [Caminada, 2006] and to further extend the framework by also allowing the use of polynomial time functions in formulae (in both queries and constraints).

Acknowledgments

We acknowledge ﬁnancial support from PNRR MUR projects FAIR (PE0000013) and SERICS (PE00000014), project Tech4You (ECS0000009), and MUR project PRIN 2022 EPICA (H53D23003660006).

References [Alfano et al., 2023a] G. Alfano, M. Calautti, S. Greco, F. Parisi, and I. Trubitsyna. Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks. Artif. Intell., 323:103967, 2023. [Alfano et al., 2023b] G. Alfano, S. Greco, F. Parisi, and I. Trubitsyna. Abstract argumentation framework with

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

conditional preferences. In Proc. of AAAI Conf., pages 6218 6227, 2023. [Alfano et al., 2023c] G. Alfano, S. Greco, F. Parisi, and I. Trubitsyna. Preferences and constraints in abstract argumentation. In Proc. of International Joint Conference on Artiﬁcial Intelligence, pages 3095 3103, 2023. [Alfano et al., 2024a] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, and G. R. Simari. Credulous acceptance in high-order argumentation frameworks with necessities: An incremental approach. Artif. Intell., 333:104159, 2024. [Alfano et al., 2024b] G. Alfano, S. Greco, D. Mandaglio, F. Parisi, and I. Trubitsyna. Abstract argumentation frameworks with strong and weak constraints. Artif. Intell., 336:104205, 2024. [Amgoud and Cayrol, 1998] L. Amgoud and C. Cayrol. On the acceptability of arguments in preference-based argumentation. In Proc. of UAI Conf., pages 1 7, 1998. [Amgoud and Cayrol, 2002] L. Amgoud and C. Cayrol. Inferring from inconsistency in preference-based argumentation frameworks. J. Autom. Reason., 29(2):125 169, 2002. [Amgoud and Vesic, 2014] L. Amgoud and S. Vesic. Rich preference-based argumentation frameworks. Int. J. Approx. Reason., 55(2):585 606, 2014. [Arenas et al., 1999] M. Arenas, L. E. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In Proc. of PODS Conf., pages 68 79, 1999. [Arieli, 2015] O. Arieli. Conﬂict-free and conﬂict-tolerant semantics for constrained argumentation frameworks. J. Appl. Log., 13(4):582 604, 2015. [Atkinson et al., 2017] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter, H. Prakken, C. Reed, G. R. Simari, M. Thimm, and S. Villata. Towards artiﬁcial argumentation. Artiﬁcial Intelligence Magazine, 38(3):25 36, 2017. [Baumann, 2012] R. Baumann. What does it take to enforce an argument? minimal change in abstract argumentation. In Proc. of ECAI Conf., pages 127 132, 2012. [Baumeister et al., 2018] D. Baumeister, D. Neugebauer, J. Rothe, and H. Schadrack. Veriﬁcation in incomplete argumentation frameworks. Artif. Intell., 264:1 26, 2018. [Baumeister et al., 2021] D. Baumeister, M. J arvisalo, D. Neugebauer, A. Niskanen, and J. Rothe. Acceptance in incomplete argumentation frameworks. Artif. Intell., page 103470, 2021. [Bench-Capon and Dunne, 2007] T. Bench-Capon and P. E. Dunne. Argumentation in artiﬁcial intelligence. Artif. Intell., 171:619 641, 2007. [Bernreiter et al., 2024a] M. Bernreiter, W. Dvor ak, A. Rapberger, and S. Woltran. The effect of preferences in abstract argumentation under a claim-centric view. J. Artif. Intell. Res., 81:203 262, 2024. [Bernreiter et al., 2024b] M. Bernreiter, W. Dvor ak, and S. Woltran. Abstract argumentation with conditional preferences. Argument Comput., 15(2):161 189, 2024.

[Bertossi, 2011] L. E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. [Bienvenu and Bourgaux, 2020] M. Bienvenu and C. Bourgaux. Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation. In Proc. of KR Conf., pages 141 151, 2020. [Bondarenko et al., 1993] A. Bondarenko, F. Toni, and R. A. Kowalski. An assumption-based framework for nonmonotonic reasoning. In Proc. of LPNMR Workshop, pages 171 189, 1993. [Brewka et al., 2013] G. Brewka, H. Strass, S. Ellmauthaler, J. P. Wallner, and S. Woltran. Abstract dialectical frameworks revisited. In Proc. of IJCAI Conf., pages 803 809, 2013. [Calautti et al., 2022a] M. Calautti, S. Greco, C. Molinaro, and I. Trubitsyna. Preference-based inconsistency-tolerant query answering under existential rules. Artif. Intell., 312:103772, 2022. [Calautti et al., 2022b] M. Calautti, S. Greco, C. Molinaro, and I. Trubitsyna. Query answering over inconsistent knowledge bases: A probabilistic approach. Theor. Comp. Sci., 935:144 173, 2022. [Caminada, 2006] M. Caminada. Semi-stable semantics. In Proc. of COMMA Conf., pages 121 130, 2006. [Cayrol et al., 2010] C. Cayrol, F. D. de Saint-Cyr, and M. Lagasquie-Schiex. Change in abstract argumentation frameworks: Adding an argument. J. Artif. Intell. Res., 38:49 84, 2010. [Cayrol et al., 2018] C. Cayrol, J. Fandinno, L. F. del Cerro, and M. Lagasquie-Schiex. Structure-based semantics of argumentation frameworks with higher-order attacks and supports. In Proc. of COMMA Conf., pages 29 36, 2018. [Cohen et al., 2015] A. Cohen, S. Gottifredi, A. J. Garcia, and G. R. Simari. An approach to abstract argumentation with recursive attack and support. J. Appl. Log., 13(4):509 533, 2015. [Coste-Marquis et al., 2006] S. Coste-Marquis, C. Devred, and P. Marquis. Constrained argumentation frameworks. In Proc. of KR Conf., pages 112 122, 2006. [Croitoru and Vesic, 2013] M. Croitoru and S. Vesic. What can argumentation do for inconsistent ontology query answering? In Proc. of SUM Conf., volume 8078, pages 15 29, 2013. [Dimopoulos and Torres, 1996] Y. Dimopoulos and A. Torres. Graph theoretical structures in logic programs and default theories. Theor. Comp. Sci., 170(1-2):209 244, 1996. [Dimopoulos et al., 2019] Y. Dimopoulos, J. Mailly, and P. Moraitis. Argumentation-based negotiation with incomplete opponent proﬁles. In Proc. of the AAMAS Conf., pages 1252 1260, 2019. [Dung and Thang, 2010] P. M. Dung and P. M. Thang. Towards (probabilistic) argumentation for jury-based dispute

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)

resolution. In Proc. of COMMA Conf., pages 171 182, 2010. [Dung, 1995] P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell., 77:321 358, 1995. [Dunne and Bench-Capon, 2002] P. E. Dunne and T. J. M. Bench-Capon. Coherence in ﬁnite argument systems. Artif. Intell., 141(1/2):187 203, 2002. [Dunne and Bench-Capon, 2004] P. E. Dunne and T. J. M. Bench-Capon. Complexity in value-based argument systems. In Proc. of JELIA Conf., pages 360 371, 2004. [Dvorak and Dunne, 2017] W. Dvorak and P. E. Dunne. Computational problems in formal argumentation and their complexity. FLAP, 4(8), 2017. [Dvor ak and Woltran, 2020] W. Dvor ak and S. Woltran. Complexity of abstract argumentation under a claimcentric view. Artif. Intell., 285:103290, 2020. [Dvor ak et al., 2023] W. Dvor ak, A. Greßler, A. Rapberger, and S. Woltran. The complexity landscape of claimaugmented argumentation frameworks. Artif. Intell., 317:103873, 2023. [Fazzinga et al., 2021a] B. Fazzinga, S. Flesca, and F. Furfaro. Reasoning over argument-incomplete aafs in the presence of correlations. In Proc. of IJCAI Conf., pages 189 195, 2021. [Fazzinga et al., 2021b] B. Fazzinga, S. Flesca, and F. Furfaro. Reasoning over attack-incomplete aafs in the presence of correlations. In Proc. of KR Conf., pages 301 311, 2021. [Fazzinga et al., 2022a] B. Fazzinga, S. Flesca, and F. Furfaro. Abstract argumentation frameworks with marginal probabilities. In Proc. of IJCAI, pages 2613 2619, 2022. [Fazzinga et al., 2022b] B. Fazzinga, S. Flesca, F. Furfaro, and L. Pontieri. Process mining meets argumentation: Explainable interpretations of low-level event logs via abstract argumentation. Inf. Syst., 107:101987, 2022. [Gottifredi et al., 2018] S. Gottifredi, A. Cohen, A. J. Garcia, and G. R. Simari. Characterizing acceptability semantics of argumentation frameworks with recursive attack and support relations. Artif. Intell., 262:336 368, 2018. [Greco et al., 2001] G. Greco, S. Greco, and E. Zumpano. A logic programming approach to the integration, repairing and querying of inconsistent databases. In Proc. of ICLP Conf., pages 348 364, 2001. [Hunter, 2012] A. Hunter. Some foundations for probabilistic abstract argumentation. In Proc. of COMMA Conf., pages 117 128, 2012. [Kaci et al., 2021] S. Kaci, L. W. N. van der Torre, S. Vesic, and S. Villata. Preference in abstract argumentation. In Handbook of Formal Argumentation, volume 2, chapter 3. College Publications, 2021. [Kim et al., 2013] E. J. Kim, S. Ordyniak, and S. Szeider. The complexity of repairing, adjusting, and aggregating

of extensions in abstract argumentation. In Proc. of TAFA Workshop, pages 158 175, 2013. [Li et al., 2011] H. Li, N. Oren, and T. J. Norman. Probabilistic argumentation frameworks. In Proc. of TAFA Workshop, pages 1 16, 2011. [Mahmood et al., 2024] Y. Mahmood, J. Virtema, T. Barlag, and A. N. Ngomo. Computing repairs under functional and inclusion dependencies via argumentation. In Proc. of Fo IKS Symp., volume 14589, pages 23 42, 2024. [Mahmood et al., 2025] Y. Mahmood, M. Hecher, and A. N. Ngomo. Dung s argumentation framework: Unveiling the expressive power with inconsistent databases. In Proc. of AAAI Conf., pages 15058 15066, 2025. [Mailly, 2020] J. Mailly. Possible controllability of control argumentation frameworks. In Proc. of COMMA Conf., pages 283 294, 2020. [Mailly, 2024] J. Mailly. Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement. AI Commun., 37(3):299 322, 2024. [Modgil and Prakken, 2013] S. Modgil and H. Prakken. A general account of argumentation with preferences. Artif. Intell., 195:361 397, 2013. [Modgil and Prakken, 2014] S. Modgil and H. Prakken. The ASPIC+ framework for structured argumentation: A tutorial. Argument & Computation, 5(1):31 62, 2014. [Nouioua and Risch, 2011] F. Nouioua and V. Risch. Argumentation frameworks with necessities. In Proc. of SUM Conf., 2011. [Nouioua, 2013] F. Nouioua. Afs with necessities: Further semantics and labelling characterization. In Proc. of SUM Conf., pages 120 133, 2013. [Prakken, 2009] H. Prakken. Models of persuasion dialogue. In Argumentation in AI, pages 281 300. 2009. [Rapberger and Ulbricht, 2024] A. Rapberger and M. Ulbricht. Repairing assumption-based argumentation frameworks. In Proc. of KR Conf., 2024. [Simari and Rahwan, 2009] G. R. Simari and I. Rahwan, editors. Argumentation in Artiﬁcial Intelligence. Springer, 2009. [Takahashi and Miwa, 2023] K. Takahashi and H. Miwa. Topological conditions and solutions for repairing argumentation frameworks. In Proc. of CLAR Conf., pages 101 118, 2023. [Ulbricht and Baumann, 2019] M. Ulbricht and R. Baumann. If nothing is accepted - repairing argumentation frameworks. J. Artif. Intell. Res., 66:1099 1145, 2019. [Villata et al., 2012] S. Villata, G. Boella, D. M. Gabbay, and L. W. N. van der Torre. Modelling defeasible and prioritized support in bipolar argumentation. Ann. Math. Artif. Intell., 66(1-4), 2012. [Wallner et al., 2017] J. P. Wallner, A. Niskanen, and M. J arvisalo. Complexity results and algorithms for extension enforcement in abstract argumentation. J. Artif. Intell. Res., 60:1 40, 2017.

Proceedings of the Thirty-Fourth International Joint Conference on Artiﬁcial Intelligence (IJCAI-25)