General Epistemic Abstract Argumentation Framework: Semantics and Complexity

1 Introduction

In the last decades, Argumentation has become an important research field of Artificial Intelligence [Bench-Capon and Dunne, 2007; Simari and Rahwan, 2009]. 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].

Abstract Argumentation Framework (AAF) is a simple yet powerful formalism for modeling disputes between two or more agents [Dung, 1995]. An AAF 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 status is entirely determined by the attack relation. An AAF 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 AAF, leading to the characterization of σ-extensions, that intuitively consist of the sets of arguments that can be collectively accepted under semantics σ ∈ {gr, co, pr, st} (accepted arguments then determine rejected ones as well as those which remain undecided).

Example 1. Consider an AAF Λ=〈{a, b}, {(a, b), (b, a)}〉 whose corresponding graph is shown in Figure 1 (left). Λ describes the following scenario. A party planner invites Alice (a) and Bob (b) to join a party. Alice replies that she will not join the party if Bob does, whereas Bob replies that he will not join the party if Alice does. This situation can be modeled by AAF Λ, where an argument x states that "(the person whose initial is) x joins the party". Under the preferred semantics, there are two extensions E1 = {a, ¬b} and E2 = {¬a, b} stating that only Alice or only Bob will attend the party, respectively. Herein, an extension is a set of argument literals, where the occurrence of a positive literal x means that argument x is accepted, while the occurrence of a negative literal ¬x means that argument x is rejected-the remaining arguments, if any, are said to be undecided. ✷

Thus, as prescribed by E1 and E2, in the previous example we have that the participation of Alice and Bob to the party is uncertain. However, AAF does not allow to represent situations where there is some person stating that they will attend the party if another given person surely (or possibly) will not attend the party. That is, uncertain information in AAF under multiple-status semantics proposed so far cannot be exploited to determine the status of arguments (which in turn influences the status of other arguments) by taking into account the information given by the whole set of extensions. To overcome such a situation, and thus provide a natural and compact way for expressing such kind of conditions, the Epistemic AAF (EAAF) has been recently proposed in [Alfano et al., 2023d], where the concept of epistemic arguments and attacks is introduced. Informally, epistemic attacks allow considering all extensions and not only the current one. Therefore, a strong (resp. weak) epistemic attack from a to b is such that a defeats b if a occurs in at least one extension (resp. all extensions).

Example 2. Consider the AAF Λ of Example 1 and assume there are two more people: Carol (c) and David (d). Carol's answer is that she will not attend the party if it is sure (i.e. it is skeptically true) that Alice will, whereas David answers that he will not attend the party if the participation of Bob is possible (i.e. it is credulously true). Intuitively, the party planner should conclude that, as the participation of both Alice and Bob is uncertain, Carol will attend the party, whereas David will not. This situation can be modeled by means of the EAAF shown in Figure 1 (center) where a attacks c with a weak epistemic attack, whereas b attacks d with a strong epistemic attack (we use the two kinds of edges represented in the figure to denote weak and strong epistemic attacks).

Under the preferred semantics, there are two extensions: E1 = {a, ¬b, c, ¬d} modeling the fact that Alice and Carol will attend the party, whereas Bob and David will not; and E2 = {¬a, b, c, ¬d} modeling the fact that Bob and Carol will attend the party, whereas Alice and David will not. Observe that the epistemic arguments c and d (i.e. the arguments attacked by an epistemic attack) are deterministic, that is, they have the same acceptance status in all extensions (true for c and false for d). ✷

So far, the semantics of EAAF has been defined and investigated only for acyclic EAAF. This is a strong limitation as cycles involving epistemic attacks are as natural as those involving standard attacks, which are common in reallife argumentation frameworks [Baroni and Giacomin, 2003; Bench-Capon, 2016; Bodanza et al., 2016; Baumann and Ulbricht, 2021; Dvor´ak et al., 2021; Lagasquie-Schiex, 2023].

Example 3. Continuing with our running example, assume now that Bob changes his mind and says that he will not join the party if Alice or David do. The corresponding (cyclic) EAAF representing the updated situation is shown in Figure 1 (right), where the addition of the standard attack from argument d towards argument b leads to the cycle (b, d, b) involving the epistemic attack (b, d). ✷

In this paper, we investigate general (possibly cyclic) EAAFs and introduce a natural, declarative semantics that extends that of AAF as well as that of acyclic EAAF.

Contributions. Our main contributions are as follows.

• We introduce a new general, declarative semantics extending the (procedural) one defined for acyclic EAAFs.
• We introduce an algorithm that enables the computation of EAAF semantics by relying on state-of-the-art AAFsolvers [Bistarelli et al., 2021; J¨arvisalo et al., 2023].
• We investigate the complexity of two canonical argumentation problems, i.e. verification and acceptance, under four well-known argumentation semantics. Since EAAF may have multiple world views (see Section 3), we introduce the possible and necessary variants of both problems. Our complexity results are summarized in Table 2 (in Section 5).

To the best of our knowledge, this is the first work providing i) a declarative semantics for general EAAF; ii) a detailed complexity analysis of the verification and acceptance problems under the most popular semantics.

2 Abstract Argumentation Framework

An Abstract Argumentation Framework (AAF) is a pair 〈A, Ω〉, where A is a (finite) set of arguments and Ω ⊆ A×A is a set of attacks. For any set P of pairs, we use P[1] (resp. P[2]) to denote the projection of P on the first (resp. second) element. Thus, Ω[1] (resp. Ω[2]) denotes the set of attacking (resp. attacked) arguments.

In the following, we consider the acceptability of argument literals (or simply literals). A literal is either an argument a or its negation ¬a; we have that ¬¬a ≡ a. A set S of literals is said to be consistent if it does not contain two literals a and ¬a. Hereafter we assume that sets of literals are consistent. We use ¬S to denote the set {¬a | a ∈ S}, and S∗ to denote S ∪ ¬S. Moreover, for any set of literals S ⊆ A∗ , we use S+ = {a | a ∈ S}, S- = {a | ¬a ∈ S}, and Su = {a | a ∈ A\(S+ ∪S-)} to denote the set of arguments that occur as positive, negative, and neither positive nor negative in S, respectively. We also say that the arguments in S+ (resp. S-, Su ) are true (resp. false, undefined) w.r.t. S.

Given an AAF Λ = 〈A, Ω〉 and a (consistent) set S ⊆ A∗ of literals, an argument a ∈ A is said to be i) defeated w.r.t. S iff ∃b ∈ S+ such that (b, a) ∈ Ω; ii) acceptable w.r.t. S iff ∀b ∈ A with (b, a) ∈ Ω, ∃c ∈ S+ such that (c, b) ∈ Ω. The sets of defeated and acceptable arguments w.r.t. S are defined as follows (where Λ is understood):

• Def(S) = {a ∈ A | ∃b ∈ S+ . (b, a) ∈ Ω};
• Acc(S)={a ∈ A | ∀b∈A . (b, a) ∈ Ω implies b ∈ Def(S)}. Given an AAF 〈A,Ω〉, a set S ⊆ A∗ of literals is said to be: i) conflict-free iff S+ ∩Def(S) = ∅; ii) admissible iff it is conflict-free, S+ ⊆ Acc(S) and S- ⊆ Def (S).

Given an AAF 〈A, Ω〉, a set S⊆A∗ is an extension called:

• complete (co) iff it is conflict-free, S+ = Acc(S) and S- = Def (S);
• preferred (pr) iff it is a ⊆-maximal complete extension;
• stable (st) iff it is a total complete extension, i.e. a complete extension such that S+ ∪ S- = A;
• grounded (gr) iff it is the ⊆-minimal complete extension.
• Observe that, for complete extensions, to check ⊆- maximality/minimality of S, it is sufficient to check ⊆- maximality/ minimality of S+ only.

The set of complete (resp. preferred, stable, grounded) extensions of an AAF Λ will be denoted by co(Λ) (resp. pr(Λ), st(Λ), gr(Λ)). 1 The set of complete extensions forms a complete semilattice w.r.t. ⊆, where gr(Λ) is the meet element, whereas the greatest elements are the preferred extensions. All the above-mentioned semantics except the stable admit at least one extension. The grounded semantics, that admits exactly one extension, is said to be a unique-status semantics, while the others are said to be multiple-status semantics. With a little abuse of notation, in the following we also use gr(Λ) to denote the grounded extension. For any AAF Λ, st(Λ) ⊆ pr(Λ) ⊆ co(Λ) and gr(Λ) ∈ co(Λ).

Given an AAF Λ = 〈A, Ω〉, a semantics σ ∈ {gr, co, pr, st} and a σ-extension E, an argument g ∈ A is said to be: accepted if g ∈ E+; rejected if g ∈ E-; undecided otherwise (g ∈ Eu ). Moreover, as it holds that E+ = Acc(E), E- =

1 For E ∈ co(Λ), E+ (resp. E-, Eu ) is also known as the set of arguments labelled as in (resp. out, undecided) [Caminada, 2006a].

Def(E) and Eu = A \ (Acc(E)∪Def(E)), hereafter we use the term accepted (resp. rejected, undecided) argument as synonym of true (resp. false, undefined) argument.

The verification problem (denoted as Verσ) is deciding whether a set S ⊆ A∗ is a σ-extension of Λ. Moreover, for g ∈ A, the credulous (resp. skeptical) acceptance problem, denoted as CAσ (resp. SAσ) is deciding whether g is credulously (resp. skeptically) accepted, that is deciding whether g belongs to any (resp. every) σ-extension of Λ. Clearly, CAgr and SAgr coincide. For a semantics σ, an argument is said to be deterministic if all σ-extensions assign the same status (either accepted, rejected, or undecided) to it [Alfano et al., 2022a]. The complexity of the verification and acceptance problems, showed in the left-hand-side part of Table 2, has been thoroughly investigated [Dvorak and Dunne, 2017].

3 Semantics of General Epistemic AAF

In this section, after reviewing the syntax of EAAF [Alfano et al., 2023d; Alfano et al., 2024c], we formally introduce the semantics of general (possibly cyclic) EAAF and provide some fundamental properties of EAAF.

3.1 Syntax

Definition 1 (Epistemic AAF). An Epistemic AAF is a quadruple ∆ = 〈A, Ω, Ψ, Φ〉 where A is a set of arguments, Ω ⊆ A×A is a set of (standard) attacks, Ψ ⊆ A×A is a set of weak (epistemic) attacks, and Φ ⊆ A×A is a set of strong (epistemic) attacks such that Ω ∩ Ψ = Ω ∩ Φ = Ψ ∩ Φ = ∅ and Ω[2] ∩ (Ψ[2] ∪ Φ[2]) = ∅.

Hence, the set of attacks are pairwise disjoint, and arguments cannot be jointly attacked through standard and epistemic attacks. The latter ensures that epistemic arguments, i.e. arguments attacked through epistemic attacks, are deterministic. We use ϵ(∆) to denote the set of epistemic arguments of EAAF ∆ and represent attacks (a, b) ∈ Ω by a → b, (a, b) ∈ Ψ by a ⇒ b, and (a, b) ∈ Φ by a →⇒ b.

An EAAF 〈A,Ω,Ψ,Φ〉 can be seen as a directed graph, where A denotes the set of nodes and Ω,Ψ, and Φ denote three different kinds of edges. We say that an EAAF is in plain form if each of its epistemic argument is attacked through a single (epistemic) attack.

In the following, we assume that EAAFs are in plain form. Note that there is no loss of generality in making such an assumption as we will show that every EAAF can be rewritten into an equivalent one in plain form (see Proposition 5).

Example 4. The EAAF ∆ = 〈A = {a, b, c, d},Ω = {(a, b), (b, a), (d, b)}, Ψ = {(a, c)},Φ = {(b, d}〉 introduced in Example 3, whose graph is shown in Figure 1 (right), is in plain form. ✷

3.2 Semantics

We provide a declarative EAAF semantics by extending the AAF one. For any EAAF ∆ = 〈A,Ω,Ψ,Φ〉, a set W of (consistent) sets of literals in A∗ such that all S ∈ W assign the same status (either true, false, or undefined) to every epistemic argument is called world view of ∆. Intuitively, we can think of a world view as a set of candidate extensions where we take a decision on the status of epistemic arguments (as they are intended to be deterministic [Alfano et al., 2022a]).

The definitions of defeated and acceptable arguments for EAAF extends that of AAF by taking into account the additional concept of world view that is used to decide if an argument is epistemically defeated/acceptable.

Given an EAAF ∆, a world view W of ∆, and a (consistent) set S ∈ W, the sets of arguments defeated (resp. accepted) w.r.t. S and W are defined as follows:

• Acc(W, S) = {b ∈ A | ∀a ∈ A . ((a → b) implies a ∈ Def(W, S)) ∧ ((a→⇒ b) implies ∀T ∈W . a ∈ Def(W, T)) ∧ ((a ⇒ b) implies ∃T ∈W . a ∈ Def(W, T)) }.

Example 5. Considering the EAAF ∆ of Example 4 and the world view W = {S1 = {c, ¬d}, S2 = {a, ¬b, c, ¬d}, S3 = {¬a, b, c, ¬d}}, we have that:

• Def(W, S1) = {d} and Acc(W, S1) = {c};
• Def (W, S2) = {b, d} and Acc(W, S2) = {a, c};
• Def (W, S3) = {a, d} and Acc(W, S3) = {b, c}. ✷

The semantics of EAAF is given by relying on the concept of σ-world view in Definition 3 (see below). Intuitively, a σworld view represents a possible scenario that could be modeled by an AAF. It is worth noting that the concept behind that of world view has been used not only for defining the semantics of epistemic reasoning in e.g. ASP [Faber et al., 2019; Fandinno et al., 2022], but also in AAF-based frameworks such as Probabilistic and Incomplete AAF [Dung and Thang, 2010; Li et al., 2011; Thimm, 2012; Hunter, 2013; Hunter et al., 2020; Baumeister et al., 2021; Fazzinga et al., 2022a; Alfano et al., 2023a] by relying on the notions of possible worlds and completions, respectively.

Before defining the semantics we introduce some notation. Given a world view W for EAAF ∆, we use τW to denote an assignment of truth values to the epistemic arguments of ∆ w.r.t. W, that is, τW = S ∩ ϵ(∆)∗ where S is any element of W. In the following, we simply write τ whenever W is understood. Since τ is a set of literals, we use the notation τ +, τ -, and τ u to denote the set of arguments that are true, false, and undefided w.r.t. τ, respectively. Moreover, we say that τ is total iff τ + ∪ τ - = ϵ(∆).

The last ingredient we need to introduce the semantics of EAAF is the concept of reduct. Intuitively, the reduct of an EAAF is an AAF which is determined by a choice of the truth values (i.e. acceptance statuses) of the epistemic arguments.

Definition 2 (Reduct). Given an EAAF ∆ and a truth value assignment τ for the epistemic arguments ϵ(∆), the reduct of ∆ w.r.t. τ (denoted by ∆τ ) is the AAF obtained from ∆ by i) deleting all epistemic attacks and every argument in τ -, and ii) adding a self-attack to every argument in τ u .

Given an EAAF ∆, a semantics σ, and a truth assignment τ for the epistemic arguments ϵ(∆) of ∆, we use σ(∆, τ) = {S ∪ τ | S ∈ σ(∆τ )} to denote the set of σ-extensions of ∆ under assignment τ. That is, σ(∆, τ) extends the σextensions of the reduct ∆τ with the acceptance status τ of epistemic arguments.

Definition 3 (EAAF Semantics). Let σ ∈ {gr, co, pr, st} be a semantics and W a world view for a given EAAF ∆. Then, W is a σ-world view for ∆ if for every S ∈ W there exists a unique set T ∈ σ(∆, τW) such that Def(W, S) = T - and Acc(W, S) = T +, and vice versa. Moreover, for σ = st, τW has to be total.

Thus, a σ-world view W can be obtained by i) fixing a truth value assignment τW for the epistemic arguments, ii) determining the set of σ-extensions entailed by the reduct W = σ(∆, τW), and iii) checking that for every S ∈ W, the conditions Def(W, S) = S- and Acc(W, S) = S+ hold, that is each extension in W is confirmed by the defeated and accepted sets.

Example 6. Consider the EAAF ∆ = 〈A={a, b, c, d, e, f}, Ω={(a, b), (b, a), (a, e), (d, f), (d, b), (e, f), (f, e)}, Ψ={(a, c)}, Φ={(b, d)}〉 shown in Figure 2 (left), and the truth assignment τ = {c, ¬d}. The reduct ∆τ is shown in Figure 2 (center). The set of preferred extensions of the reduct are pr(∆τ ) = {{a, ¬b, c, ¬e, f}, {¬a, b, c, e, ¬f}, {¬a, b, c, ¬e, f}}. Thus, we have that pr(∆, τ) = W = {S1 = {a, ¬b, c, ¬d, ¬e, f}, S2 = {¬a, b, c, ¬d, e, ¬f}, S3 = {¬a, b, c, ¬d, ¬e, f}}. As Def(W, Si) = Siand Acc(W, Si) = Si+, for i ∈ [1..3], we have that W = {S1, S2, S3} is a pr-world view. Consider now τ ′ = {c, d}. The reduct ∆τ ′ is shown in Figure 2 (right). Here, pr(∆τ ′ ) = {{a, ¬b, c, d, ¬e, ¬f}}. Therefore, pr(∆, τ ′ ) = W ′ = {S′1 = {a, ¬b, c, d, ¬e, ¬f}}. Since c is epistemically attacked by a, we have that c ̸∈ Acc(W ′ , S′1 ) (i.e. S′1 ̸= Acc(W ′ , S1)), entailing that W ′ is not a pr-world view. ✷

For any EAAF ∆ and semantics σ ∈ {gr, co, pr, st}, we use σ(∆) to denote the set of σ-world views of ∆.

3.3 Properties of EAAF

We now present some results concerning properties of EAAF. We start with the following proposition that states that each truth assignment τ can lead to at most one σ-world view.

Proposition 1. For any EAAF ∆, semantics σ ∈ {gr, co, pr, st}, and W1,W2 ∈ σ(∆), τW1 = τW2 implies W1 = W2.

Clearly, as σ-world views assign the same status to epistemic arguments, the converse of the implication in Proposition 1 trivially holds, i.e. W1 = W2 implies τW1 = τW2 .

Our second result concerns the generalization of AAF semantics. Note that whenever Ψ = Φ = ∅, we have that the definitions of defeated and acceptable arguments coincide with the ones defined for AAF, that is Def({S}, S) = Def(S) and Acc({S}, S) = Acc(S). This lead to the following result that states that any EAAF without epistemic attacks has a single world view consisting of the extensions of the AAF encoded by the given EAAF.

Proposition 2. For any EAAF ∆ = 〈A, Ω, ∅, ∅〉 and semantics σ ∈ {gr, co, pr, st}, σ(∆) = {σ(〈A, Ω〉)} holds.

Another case where we have a single world view is when the EAAF is acyclic, which is the restricted form considered in [Alfano et al., 2023d; Alfano et al., 2023f]. An EAAF is acyclic if none of its epistemic attacks is involved in a cycle. Hence, cycles consisting of non-epistemic attacks only are allowed in acyclic EAAF.

Theorem 1. Any acyclic EAAF has a unique σ-world view under semantics σ∈{gr, co, pr} and at most one for σ = st. The following proposition states that the proposed semantics

generalizes that defined in the literature for acyclic EAAF.

Proposition 3. For any acyclic EAAF ∆, σ(∆) coincides with the world view defined i) in [Alfano et al., 2023d] for σ ∈ {gr, co, pr}, and ii) in [Alfano et al., 2023f] for σ = st.

We now provide results concerning the relationship between extensions under different semantics. Given two sets W1 and W2 of sets of elements, we say that W1 is subsumed by W2 (denoted as W1 ⊑ W2) if ∀S1 ∈ W1, ∃S2 ∈ W2 such that S1 ⊆ S2. As stated next, differently from AAF, where grounded, stable and preferred extensions are guaranteed to be complete extensions (that is, st(Λ) ⊆ pr(Λ) ⊆ co(Λ) and gr(Λ) ∈ co(Λ) for any AAF Λ), an analogous relationship does not hold for EAAF in general.

Proposition 4. There exist EAAFs ∆1, ∆2, ∆3, ∆4 such that: i) pr(∆1) ̸⊑ co(∆1); ii) st(∆2) ̸⊑ co(∆2); iii) gr(∆3) ̸⊑ co(∆3); iv) st(∆4) ̸⊑ pr(∆4).

With reference to the result of Proposition 4, it is worth noting that, even in AAF credulous and skeptical acceptance may give different results under different semantics, and this inherently carries on over the semantics of EAAF.

4 Computation

In this section, we present an algorithm for computing EAAF semantics. We start by showing that there is no loss of generality in making the assumption that EAAFs are in plain form. In fact, any EAAF ∆ can be rewritten into an "equivalent" one ̂∆ in plain form such that complete (resp. grounded, preferred, and stable) world views of ∆ can be obtained from those of ̂∆, as stated in the following proposition.

Proposition 5. For any EAAF ∆ = 〈A,Ω,Ψ,Φ〉 and a semantics σ ∈ {gr, co, pr, st}, there exists an EAAF ̂∆ in plain form such that, let σ(̂∆) = {̂ W1, . . . , ̂ Wn} and let Wi = {̂ S ∩ A∗ | ̂ S ∈ ̂ Wi} ∀i ∈ [1, n], it holds that σ(∆) = {W1, ...,Wn}.

Thus, Proposition 5 ensures that, given any EAAF, we can build an EAAF in plain form whose world views are in a oneto-one correspondence with those of the original one, modulo some meta-arguments that need to be removed by restricting the world views to the literals of the original EAAF. An example of application of Proposition 5 is the following.

Example 7. Consider the EAAF ∆ = 〈A = {a, b, c, d, e}, Ω = {(a, b), (b, a)}, Ψ = {(a, c), (a, e), (b, d)}, Φ = {(b, c)}, shown in Figure 3 (left), and its preferred-world view W = {{a, ¬b, ¬c, d, e}, {¬a, b, ¬c, d, e}}. Let ̂∆ = 〈 ̂ A, ̂Ω, ̂Ψ, ̂Φ〉 be the EAAF shown in Figure 3 (right), where ̂ A = A ∪ {aw, aw, bw, bw, bs, bs}; ̂Ω = Ω ∪ {(aw, aw), (aw, c), (aw, e), (bw, bw), (bw, d), (bs, bs), (bs, c)}; ̂Ψ = {(a, aw), (b, bw)}; and ̂Φ = {(b, bs)}. The pr-world view for ̂∆ is ̂ W = {{a, ¬b, ¬c, d, e, aw, ¬aw, bw, ¬bw, bs, ¬bs} {¬a, b, ¬c, d, e, aw, ¬aw, bw, ¬bw, bs ¬bs}}. As prescribed by Proposition 5, W = { ̂ S ∩A∗ | ̂ S ∈ ̂ W}. ✷

Thus, as previously stated in Section 3.1, w.l.o.g. we can assume that EAAFs are in plain form. From the previous example, it can be easily understood that the size of such a plain-form EAAF ̂∆ is linear in the size of the source EAAF ∆ and can be computed in linear time in the size of ∆.

We now present Algorithm 1 that computes the world views of an EAAF ∆ under semantics σ. The algorithm makes use of an external function Solveσ that computes the set of σ-extensions of a given AAF if it exists, otherwise it returns ⊥ (recall that the set of extensions may not exist for the stable semantics only). More in detail, Algorithm 1 works as follows. First, the set Υ of all truth assignments for ϵ(∆) is computed at Line 1 (total truth assignments are considered in the case of stable semantics). Then, for any truth assignment τ ∈ Υ, Algorithm 1 checks whether τ induces a σ-world view for ∆ according to Definition 3 (Lines 3-6). In particular, this is verified by first i) augmenting the extensions of the reduct σ(∆τ ) with τ , thus obtaining W = σ(∆, τ) at Line 4 (herein, σ(∆τ ) is computed through function Solveσ; we assume that ⊥ ∪ τ gives ⊥, where ⊥ denotes the non-existence of extensions), and then ii) checking that for every S ∈ W, Def (W, S) = S- and Acc(W, S) = S+ (Line 5). Whenever the above check is positive, Algorithm 1 extends σ(∆) with W (Line 6) as it represents a σ-world view of ∆.

An example of the execution of Algorithm 1 is given below.

Example 8. Consider the EAAF ∆ = 〈A,Ω,Ψ,Φ〉 of Example 6 (see Figure 2, left) and the semantics σ = pr. Table 1 reports, for each of the nine truth assignments τi (with i ∈ [1..9]) for ϵ(∆) = {c, d} computed at Line 1 of Algorithm 1, the reduct ∆τi and the set of its preferred extensions σ(∆τi ) expanded with τi. Moreover, cyan-colored cells high-

Algorithm 1 SolveEAAF

Require: EAAF ∆ = 〈A,Ω,Ψ,Φ〉; σ ∈{gr, co, pr, st}; sound and complete function Solveσ(Λ) returning the set of σ-extensions of an AAF Λ if it exits, ⊥ otherwise.

Ensure: The set σ(∆) of σ-world views of ∆.

• 1: LetΥbe a set of (total if σ=st) truth assignments for ϵ(∆);
• 2: Let σ(∆) = ∅;
• 3: for τ ∈ Υ do
• 4: Let W = {E ∪ τ | E ∈ Solveσ(∆τ )};
• 5: if W̸=⊥∧ ∀S ∈W. Def (W, S)=S-∧Acc(W, S)=S+
• 6:
• σ(∆) = σ(∆) ∪ W ;

return σ(∆);

light the truth assignments τi such that the condition of Line 5 of Algorithm 1 holds. Thus, Algorithm 1 ends by returning the set of preferred world views of ∆, that is pr(∆) = {{{a, ¬b, c, ¬d, ¬e, f}, {¬a, b, c, ¬d, e, ¬f}, {¬a, b, c, ¬d, ¬e, f}}, {{a, ¬b, d, ¬e, ¬f}}}, obtained through assignments τ3 and τ4, respectively. ✷

As stated next, Algorithm 1 is sound and complete.

Theorem 2. Let ∆=〈A, Ω, Ψ, Φ〉 be an EAAF, and σ ∈{gr, co, pr, st} a semantics. Then, Algorithm 1 returns all and only the σ-world views of ∆.

5 Complexity

We investigate the complexity of two fundamental reasoning problems for EAAF. We study the verification and credulous/skeptical acceptance problems, that are usually considered for analyzing the computational complexity of argumentation frameworks [Alfano et al., 2023b; Baumeister et al., 2021; Alfano et al., 2023e; Fazzinga et al., 2023; Alfano et al., 2024b]. To deal with multiple world views, the possible and necessary variants of those problems are introduced in what follows-this is somehow analogous to the approach adopted for instance in incomplete AAF [Baumeister et al., 2021] where multiple completions may exist, each corresponding to a possible materialization of uncertain arguments and attacks.

Given an EAAF ∆ = 〈A, Ω, Ψ, Φ〉 and a semantics σ ∈ {gr, co, pr, st}, we can define the following problems:

• the possible (resp. necessary) verification problem for EAAF, denoted as PVerσ (resp. NVerσ), consists in deciding whether a given set of literals S ⊆ A∗ is in any (resp. every) σ-world view of ∆;

• the possible (resp. necessary) credulous acceptance problem, denoted as PCAσ (resp. NCAσ), consists in deciding whether a given goal argument g ∈ A belongs to any σextension of any (resp. every) world view of ∆.
• the possible (resp. necessary) skeptical acceptance problem, denoted as PSAσ (resp. NSAσ), consists in deciding whether a given goal argument g ∈ A belongs to every σextension of any (resp. every) world view of ∆.

Observe that if argument g is epistemic, then credulous and skeptical reasoning coincide. In fact, since epistemic arguments are deterministic, their acceptance status does not change in different extensions of a world view (though may change in different world views). Thus, possible (resp. necessary) credulous and skeptical acceptance problems coincide, and we can simply call this problem possible (resp. necessary) epistemic acceptance, denoted as PEAσ (resp. NEAσ).

Concerning acceptance of non-epistemic arguments, we have that the epistemic acceptance problem is able to capture the credulous and skeptical acceptance problems also for non-epistemic arguments, as shown in what follows.

Fact 1. For any EAAF ∆ = 〈A,Ω,Ψ,Φ〉, semantics σ ∈ {gr, co, pr, st}, and argument g ∈ A, it holds that:

• PCAσ(∆, g) = PEAσ(∆′ , gw) and NCAσ(∆, g) = NEAσ(∆′ , gw) with: ∆′ = 〈A ∪ {g, gw}, Ω ∪ {(g, g)}, Ψ ∪ {(g, gw)}, Φ〉;
• PSAσ(∆, g) = PEAσ(∆′ , gs) and NSAσ(∆, g) = NEAσ(∆′ , gs) with: ∆′ = 〈A ∪ {g, gs}, Ω ∪ {(g, g)}, Ψ, Φ ∪ {(g, gs)}〉.

Thus, asking for the credulous and skeptical acceptance of an argument g w.r.t. an EAAF ∆ is equivalent to asking for the epistemic acceptance of a fresh epistemic argument (i.e. gw or gs, respectively) w.r.t. an EAAF ∆′ that is obtained from ∆ by adding only two arguments and two attacks. For this reason and for the fact that epistemic arguments are deterministic, w.l.o.g. we study the complexity of verification and epistemic acceptance problems in EAAFs.

Results for Acyclic EAAF

For acyclic EAAF, the possible and necessary variants of the verification and acceptance problems coincide (as a single world view is prescribed). Hence, we use simply Verσ and EAσ to denote the verification and acceptance problems in acyclic EAAF, respectively.

The following two theorems provide new results for Verσ and EAσ. These results are of interest from two standpoints.

First, they provide some tight bounds for the complexity of the verification and acceptance problems in acyclic EAAF. Second, they turn out to be useful to provide lower bounds on the complexity of the problems considered for general EAAF.

Theorem 3. For acyclic EAAF, Verσ is: i) Θp2 -complete for σ ∈ {co, st}, and ii) Θp2 -hard and in Θp3 for σ = pr.

Theorem 3 strengthens the complexity upper bounds for the verification problem under complete and preferred semantics, which are shown to be in ∆p2 and in ∆p3 , respectively, in [Alfano et al., 2023d]. Moreover, it provides tight lowerand upper-bounds for the complexity of the the verification problem under stable semantics, which is shown to be DPhard in [Alfano et al., 2023f]. Finally, the next theorem provides novel complexity bounds for the acceptance problem under stable semantics.

Theorem 4. For acyclic EAAF, EAst is Θp2 -hard and in ∆p2 .

A summary of the results for acyclic and general EAAF is reported in Table 2, where new results are highlighted in cyan.

Results for General EAAF

We now consider general EAAF and investigate the complexity of the verification and acceptance problems under the possible and necessary perspectives. The complexity of the possible and necessary verification problems, PVerσ and NVerσ, for σ ∈ {gr, co, pr, st} is stated in the next two theorems.

Theorem 5. PVerσ is: i) in P for σ = gr, ii) Θp2 -complete for σ ∈ {co, st}, and iii) Θp2 -hard and in Θp3 for σ = pr.

Theorem 6. NVerσ is: i) coNP-complete for σ = gr, ii) Θp2 -hard and in Πp2 for σ = co, iii) Πp2 -complete for σ = st, and iv) Σp2 -hard and in Πp3 for σ = pr.

Interestingly, while the complexity lower- and upperbounds provided for PVerσ are the same of those for Verσ (i.e. for acyclic EAAF), the complexity bounds for NVerσ suggest that necessary verification turns out to be computationally more expensive. This is evident for the grounded and stable semantics, where NVergr and NVerst become coNPcomplete and Πp2 -complete, respectively.

The complexity of epistemic acceptance is as follows.

Theorem 7. PEAσ is: i) NP-complete for σ = gr, ii) Θp2 - hard and in Σp2 for σ ∈ {co, st}, and iii) Πp2 -hard and in Σp3 for σ = pr.

Theorem 8. NEAσ is: i) coNP-complete for σ = gr, ii) Θp2 -hard and in Πp2 for σ = co, iii) Πp2 -complete for σ = st, and iv) Πp2 -hard and in Πp3 for σ = pr.

Thus, considering the results for the grounded and stable semantics, it turns out that the acceptance problem is harder than in case of acyclic EAAF. Overall, our complexity analysis confirms the intuition that general EAAF is more expressive than acyclic EAAF.

6 RelatedWork

Several proposals have been made to extend Dung's framework with the aim of better modeling the knowledge to be represented. The extensions include Bipolar AAF [Villata et al., 2012], AAF with recursive attacks and supports [Alfano et al., 2024a; Cayrol et al., 2018], Dialectical framework [Brewka et al., 2013], AAF with collective attacks, namely SETAF [Nielsen and Parsons, 2006; Dvoˇr´ak et al., 2024; Dimopoulos et al., 2023], AAF with preferences [Amgoud and Cayrol, 2002; Modgil and Prakken, 2013; Alfano et al., 2022b; Alfano et al., 2023c] and constraints [Coste-Marquis et al., 2006; Arieli, 2015], as well as extensions for representing uncertain information, e.g. incomplete AAF [Baumeister et al., 2021; Fazzinga et al., 2021a; Fazzinga et al., 2021b] and probabilistic AAF [Dung and Thang, 2010; Li et al., 2011; Thimm, 2012; Hunter, 2013; Hunter et al., 2020]. In this regard, in the epistemic approach to probabilistic AAF [Thimm, 2012; Hunter, 2013; Hunter et al., 2020] a probability function over sets of arguments represents an epistemic state of an agent that has uncertain beliefs; herein, uncertainty about the fact that arguments are justifiable by an agent is modeled.

Work on epistemic logic dates back to the early 1860s. Since then epistemic logic has played an important role in computer science. This field is very active and important results are reported in [van Ditmarsch et al., 2015]. Epistemic logic extends propositional logic by allowing to also express knowledge of the agents, also called subjective knowledge. In particular, it allows writing formulae of the formKaϕ stating that agent a knows that formula ϕ is true. Thus, while a formula p∨q expresses the (objective) knowledge that p or q are true (i.e. the formula is satisfied if a is true or b is true), a formula Ka(p ∨ q) expresses the (subjective) knowledge that agent a knows that p is true or q is true. On the other side, the formula KaKbp states that agent a knows that agent b knows that p holds, i.e. it is satisfied if agent a knows that agent b knows that p holds [van Ditmarsch et al., 2015].

The idea of extending logic with epistemic constructs has been investigated also in the field of Answer Set Programming (ASP) [Fandinno et al., 2022]. Epistemic logic programs, firstly proposed in [Gelfond, 1991], extend disjunctive logic programs under the stable model semantics by introducing epistemic or subjective atoms of the form K ℓ or M ℓ, where ℓ is a literal, whereas K and M are the epistemic operators of certainty ('known' or 'provably true') and possibility ('maybe', 'possible', or 'not provably false') [Gelfond, 1991; Gelfond, 1994]. Epistemic extensions of ASP have received renewed interest and several semantics have been studied [Gelfond, 2011; del Cerro et al., 2015; Kahl et al., 2020; Shen and Eiter, 2016; Cabalar et al., 2019; Cabalar et al., 2020; Faber et al., 2019]. There is a tight connection between the concept of reduct introduced in this paper and those proposed for epistemic ASP. Specifically, the one introduced in this paper can be seen as an extension for three-valued semantics of that proposed in [Gelfond, 1994]. Notably, in our case no problems concerning unfoundedness of world views arise. Indeed, as stable world-views could be computed by rewriting EAAFs into ASP programs, since there is no cyclic positive dependency through epistemic literals, the world-views computed using the reduct proposed in [Gelfond, 1994] are founded [Cabalar et al., 2020].

An Epistemic Argumentation Framework (EAF) has been proposed in [Sakama and Son, 2020]. In EAF the epistemic constraint plays a role similar to the one played by constraints in Constrained AAF (CAF) [Coste-Marquis et al., 2006; Arieli, 2015] or to the one played by preferences in Preference-based AAF (PAF) [Amgoud and Cayrol, 2002; Amgoud and Vesic, 2014; Kaci et al., 2018], that is, restrict the set of feasible extensions. However, while in CAF and PAF the subset obtained is unique, in EAF we can have alternative subsets. It is worth noting that, according to our complexity analysis, EAAF cannot be fully captured in EAF. Indeed, the verification problem, that is, given an EAF and a set S of arguments, checking whether there is a complete epistemic labelling set containing S is in P for EAF. In contrast, as shown earlier, the verification problem for complete semantics is Θp2 -hard even for acyclic EAAF. Similar differences arise for other semantics, entailing a different expressive power of the two frameworks.

7 Conclusion

We have presented the Epistemic Abstract Argumentation Framework, a generalization of Dung's framework where epistemic attacks and arguments can be expressed. We have provided an intuitive, declarative semantics for (general) EAAF that naturally extends that for AAF as well as that for acyclic EAAF. We believe that our results could be of interest to the logic community. In fact, by exploiting the correspondence between AAF and Logic Programming [Caminada et al., 2015], the proposed EAAF semantics could be seen as an alternative semantics for a special class of epistemic logic programs whose complexity and computation can be characterized by using our results. Future work will be devoted to considering other argumentation semantics, such as semistable semantics [Caminada, 2006b], and developing efficient algorithms specifically tailored to EAAF.

Acknowledgments

We acknowledge financial support from PNRR MUR project PE0000013-FAIR and project Tech4You ECS0000009, and MUR project PRIN 2022 EPICA (CUP H53D23003660006).