Featured Argumentation Framework: Semantics and Complexity

1 Introduction

Formal argumentation has emerged as one of the important fields in Artificial 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 specifies 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 defined 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}.

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 [CosteMarquis 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 (iAF), where arguments and attacks may be uncertain [Baumeister et al., 2018; Baumeister et al., 2021], and probabilistic AF (PrAF), 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 traffic 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 first letter of the experts' name. These 9 arguments can be summarized as follows:

• a1: Impose immediate fines and sanctions on industries exceeding pollution limits;
• a2: Enforce stricter industrial regulations with compliance mechanisms;

• 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 defined 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 (first-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, traffic 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 traffic limitations. For reasoning about the first 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 traffic 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 defined by means of the FOL formula ∀X.term(X, short), whereas the subframework considering only arguments denoting policies regarding both pollution regulation and traffic limitation can be defined by means of the FOL formula ∀X.policy(X, pollution regulation) ∨ policy(X, traffic limitation). On the other side, the formula ∀X.policy(X, pollution regulation) ∨ ∀X.policy(X, traffic 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) field 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 satisfies 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 specifically, a subframework is obtained by deleting a minimal set or a minimal number of arguments and attacks, so that the FOL formula is satisfied 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 defined 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 as possible worlds. Thus, classical verification 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 verification, as well as possible and necessary credulous/skeptical acceptance (cf. Definitions 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 defined 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 verification and acceptance problems for EFAF and thoroughly investigate the complexity of these problems. A summary of our results for the verification 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 iAF [Fazzinga et al., 2021a; Fazzinga et al., 2021b] and constrained iAF [Mailly, 2024].
• Consistently with our complexity results, we show that incomplete AF, correlated and constrained iAF 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 fixed):

• 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 conflict-free iff S ∩ Def(S) = ∅. Moreover, S ⊆ A is said to be a complete (co) extension iff it is conflict-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 specified 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 predefined (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 ArgA to denote the set of built-in facts {arg(a) | a ∈ A}.

Definition 1. A Featured AF (FAF) is a triple Ω = 〈A, R, F 〉 where 〈A, R〉 is an AF and F is a finite set of base facts.

For an FAF 〈A, R, F 〉, the set of base and built-in facts will be denoted by FA = F ∪ ArgA.

The concept of inclusion defined 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.

Definition 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 defined 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) quantified. For instance, the boolean query arg(a) checks the acceptance of argument a.

Definition 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. □

1 Here 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) coNPcomplete for σ = st, and iii) Πp2 -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 satisfied. The formula, defined on the argument features and the topology of the underlying AF, is used to define 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 AttR 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 firstorder language using base, built-in and derived predicates, and terms (i.e. arguments, constants and variables).

Definition 4. An extended FAF (EFAF) is a tuple ∆ = 〈A, R, F, C〉 where 〈A, R, F 〉 is an FAF and C is a first-order formula defined over λ.

We use F AR = F ∪ArgA∪AttR 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 defined 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 defining 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 satisfied 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 satisfied 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 satisfied by F AR. Intuitively, if the logical formula C is not satisfied, 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 satisfied. Clearly, when deleting arguments, related features and attacks are deleted as well. In the following, we assume that the formula C is satisfiable, that is that there exists an FAF 〈A, R, F 〉 such that FAR |= C.

Definition 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 fix 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 defined 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 first-class citizens.

5 Computational Complexity

We investigate the complexity of fundamental reasoning problems for EFAF. In particular, we study the verification, 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.

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, verification, and acceptance problems can be defined analogously to those defined for iAF [Baumeister et al., 2018; Baumeister et al., 2021]. In fact, roughly speaking, the main differences with respect to iAF 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.

Definition 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 Verification Problems

We now characterize the complexity of the verification problems for EFAF, which are formally defined in what follows.

Definition 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 verification problem, denoted as δ-PVσ, is the problem of checking whether S is a σ-extension in any δ-subframework for ∆;
• the δ-necessary verification 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 verification 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 verification problem for EFAF is generally harder than that 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) Θp2 -complete for σ ∈ {gr, co, st}, and ii) Θp2 -hard and in Σp2 for σ = pr;
• s-PVσ is Σp2 -complete for σ ∈ {gr, co, st, pr};
• c-NVσ is Θp2 -complete for σ ∈ {gr, co, st, pr};
• s-NVσ is Πp2 -complete for σ ∈ {gr, co, st, pr}.

Notably, the verification problem for EFAF is computationally harder than that for constrained iAF (ciAF) [Mailly, 2020] (and thus iAF) under all the considered (argumentation and subframework) semantics, except for δ-PVpr (with δ ∈ {c, s}) for which the verification problems for EFAF and ciAF belong to the same class (Σp2 ). On the other side, it can be shown that the complexity of verification for FAF is as that of AF, as any FAF coincides with its unique subframework and thus FAF verification collapses to AF verification.

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 definition generalizes that of the credulous and skeptical acceptance problems for AF to the case of EFAF, analogously to what is done for (c)iAF.

Definition 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-defined acceptance problems.

Theorem 3.

• c-PCAσ is Θp2 -complete for any σ ∈ {gr, co, st, pr};
• s-PCAσ is Σp2 -complete for any σ ∈ {gr, co, st, pr};
• c-NCAσ is i) Θp2 -complete for σ = gr, and ii) Πp2 -complete for any σ ∈ {co, st, pr};
• s-NCAσ is Πp2 -complete for any σ ∈ {gr, co, st, pr};
• c-PSAσ is i) Θp2 -complete for any σ ∈ {gr, co}, and ii) Σp2 -complete for any σ ∈ {st, pr};
• s-PSAσ is i) Σp2 -complete for any σ ∈ {gr, co, st}, and ii) Σp3 -complete for σ = pr;
• c-NSAσ is i)Θp2 -complete for any σ ∈ {gr, co, st}, and ii) Πp2 -complete for σ = pr.
• s-NSAσ is Πp2 -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)iAF, for all the other 25 cases considered the complexity of EFAF is higher than that of (c)iAF, even under cardinality subframework semantics whose complexity is systematically lower than or equal to that of the set semantics.

6 EFAF versus iAF-based Frameworks

As observed earlier, there are some connections between EFAF and iAF [Baumeister et al., 2021]. Acceptance problems are defined similarly, in the sense that the semantics of iAF is defined by the set of completions, whereas that of EFAF is defined 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 iAF [Fazzinga et al., 2021a; Fazzinga et al., 2021b; Mailly, 2020], though the formulae defined in the latter frameworks are propositional and allow only built-in predicates. We investigate the relationship between EFAF and those frameworks, showing that iAF, as well as constrained and correlated iAF, are special cases of EFAF.

6.1 Incomplete Argumentation Framework

An incomplete (abstract) Argumentation Framework (iAF) 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 iAF compa-ctly represents alternative AF scenarios, called completions.

Definition 9 (Completion). A completion for an iAF Ψ = 〈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 iAF Ψ is denoted by comp(Ψ).

Verification and acceptance problems, originally introduced in [Baumeister et al., 2018; Baumeister et al., 2021], are defined 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 iAF Ψ= 〈{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:

• Λ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 iAF

We start showing that every iAF can be rewritten into an extensions-equivalent EFAF, modulo meta-elements. The equivalence between an iAF Ψ = 〈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 iAF Ψ and a (derived) EFAF ∆ is denoted by Ψ ≊s ∆ (resp. Ψ ≊c ∆).

Theorem 4. For any iAF Ψ = 〈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

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 iAF Ψ 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 iAF

Two extensions of iAF related to our proposals are correlated iAF [Fazzinga et al., 2021a; Fazzinga et al., 2021b] and constrained iAF [Mailly, 2020]. Both frameworks extend iAF by adding a propositional formula which must be satisfied 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 iAF considers different fragments of propositional logic (PL), with the aim of studying complexity and expressivity of those fragments, constrained iAF 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 iAF is more general, there are fragments of correlated iAF that have the same expressivity of general PL. Thus, hereafter we focus on constrained iAF.

Let γA denote the propositional language built over the propositional atoms in {arg(a) | a ∈ A}∪{att(a, b) | a, b, ∈ A}, a constrained iAF can be defined as follows.

Definition 10. A Constrained iAF (ciAF) is a tuple Ψ = 〈A,B,R, T,C〉, where 〈A,B,R, T〉 is an iAF, and C ∈ γA∪B is a propositional formula (called constraint).

The constraint C is used to select a subset of the completions of iAF Ψ. 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 ciAF in the obvious way, we have the following.

Theorem 5. For any ciAF Ψ = 〈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 ciAF Ψ = 〈A,B,R, T,C〉 where 〈A,B,R, T〉 is the iAF 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 ciAF Ψ, modulo meta-elements. □

7 RelatedWork

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 defined 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 allowmodifications that result in the addition of arguments and attacks, but we are interested in (minimal) removals ensuring satisfaction of user-defined 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 defining 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 redefines argumentation semantics in terms of the arguments' claims. We follow the inherited approach in defining 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 satisfied by subframeworks. For several argumentation semantics, EFAF turns out to be more expressive that iAFbased 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 iAF, correlated and constrained iAF, 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 financial support from PNRR MUR projects FAIR (PE0000013) and SERICS (PE00000014), project Tech4You (ECS0000009), and MUR project PRIN 2022 EPICA (H53D23003660006).