Dung's Argumentation Framework (AF) has been extended in several directions. An interesting extension, among others, is the Epistemic Argumentation Framework (EAF) which allows representing the agent's belief by means of epistemic constraints. An epistemic constraint is a propositional formula over labeled arguments (e.g. in(a)) extended with the modal operators K and M that intuitively state that the agent believes that a given formula is certainly or possibly true, respectively. In this paper, we discuss interesting results recently presented in [1] concerning the complexity of three canonical argumentation problems (i.e. verification , existence, and non-empty existence) in the context of EAF as well as the relationship between EAF and incomplete AF, an extension of AF where arguments and attacks may be uncertain.
In the last decades, Formal Argumentation has become an important research field in AI [
Argumentation semantics can also be defined in terms of labelling [
Despite the expressive power and generality of Dung’s framework, in some cases it is difficult
to accurately model domain knowledge by an AF in a natural and easy-to-understand way; this
is somehow related to the fact that AF is often viewed as a tool for acceptability evaluation,
rather than for directly model domain knowledge as in structured formalisms like ASPIC+ and
DeLP [
In the following we focus on an interesting extension of Dung’s framework with epistemic
constraints called Epistemic Argumentation Framework (EAF) [
In the previous example we have a single -epistemic labelling sets. However, in general, an EAF may have multiple -epistemic labelling sets as shown in the following example. Example 3. Consider the AF Λ3 = ⟨A3, R3⟩ shown in Figure 1 (center), where A3 = A1, R3 = R1 ∪ {(b, a)}, and A1 and R1 are as defined in Example 1. The set of its -labellings with ∈ {st, pr, sst} is {ℒ1, ℒ2, ℒ3}, where ℒ1 and ℒ2 are the -labellings for AF Λ1 of Example 1 and ℒ3 = {out(a), in(b), out(c), in(d)}. Then, EAF Δ3 = ⟨A3, R3, Kin(a) ∨ Kin(d)⟩ has two -epistemic labelling sets, {ℒ1, ℒ2} and {ℒ2, ℒ3}, representing the scenarios compliant with the belief of the party planner that Alice or David will certainly join the party. □
Moreover, the existence of a -labelling is not guaranteed in EAF. That is, even for semantics prescribing at least one -labelling for the underlying AF (e.g. ∈ {gr, co, pr, sst}), we can have EAFs having no non-empty -epistemic labelling set.
Example 4. The EAF Δ4 = ⟨A3, R3, K(in(a) ∧ in(b))⟩ (that differs from the EAF Δ3 of Example 3 in the epistemic constraint only) has no grounded, complete, preferred, stable, and semi-stable labelling, meaning that any -epistemic labelling set is empty for any ∈ {gr, co, st, pr, sst}. □
Besides the problem of deciding the existence of a -labelling, two additional fundamental
problems investigated in AF are i) non-empty existence, that is deciding if there is a -labelling
prescribing a non-empty set of accepted arguments, and ii) verification , that is deciding whether
a given assignment of labels in {in, out, und} to each argument is a -labelling. In general,
the (non-empty) existence and verification problems are important to understand the behavior of
argumentation semantics. For this reason, the complexity of these problems have been explored
in detail for AF [
In this paper, we investigate the complexity of the verification , existence, and non-empty existence problems in EAF and explore the relationship between EAF and iAF. Contributions. Our main contributions are as follows.
• We first present the possible and necessary variants of the verification, existence, and non-empty existence problems in EAF by taking into account the fact that an EAF may have multiple -epistemic labelling sets. Intuitively, given an EAF, the possible (resp. necessary) verification problem consist in deciding whether a candidate labelling—a given assignment of the labels in {in, out, und} to each argument—belongs to any (resp. every) -epistemic labelling set, with ∈ {gr, co, st, pr, sst}. The possible (resp. necessary) existence problem consists in deciding whether there is -labelling in any (resp. every) -epistemic labelling set. Moreover, the possible (resp. necessary) non-empty existence problem consists in deciding whether there is a -labelling prescribing a non-empty set of accepted arguments in any (resp. every) -epistemic labelling set. • We discuss the complexity of the possible and necessary variants of the verification, existence, and non-empty existence problems for EAF, showing that in most cases these problems are harder than those for AF. In particular, the complexity of the verification problems for EAF increases of one level in the polynomial hierarchy w.r.t. that for AF (cf. Table 1). Moreover, the complexity of the possible and necessary existence problems for EAF increase of at least one level (in the polynomial hierarchy) w.r.t. that for AF, except for the stable semantics for which it remains the same. The complexity of the possible and necessary non-empty existence problems for EAF increase of one level w.r.t. that for AF for both the preferred and semi-stable semantics, while it remains the same for the complete and stable semantics. A complete picture of the complexity of the (non-empty) existence problems is given in Table 2, where the results for iAF are reported as well. • Finally, we analyze the relationship between EAF and iAF, showing that (possible and necessary) verification in iAF can be reduced to (possible and necessary) verification in EAF under complete, preferred, stable and semi-stable semantics.
In this section, we review the AF-based frameworks considered in the paper.
An abstract Argumentation Framework (AF) is a pair ⟨A, R⟩, where A is a set of arguments and R ⊆ A × A is a set of attacks. If (, ) ∈ R then we say that attacks .
Given an AF Λ = ⟨A, R⟩ and a set ⊆ A of arguments, an argument ∈ A is said to be i) defeated w.r.t. iff ∃ ∈ such that (, ) ∈ R, and ii) acceptable w.r.t. iff for every argument ∈ A with (, ) ∈ R, there is ∈ such that (, ) ∈ R. The sets of defeated and acceptable arguments w.r.t. are as follows (where Λ is understood): ∙ Def() = { ∈ A | ∃(, ) ∈ R . ∈ }; ∙ Acc() = { ∈ A | ∀(, ) ∈ R . ∈ Def()}.
Given an AF ⟨A, R⟩, a set ⊆ A of arguments is said to be conflict-free iff ∩ () = ∅; and admissible iff it is conflict-free and ⊆ ().
Different argumentation semantics have been proposed to characterize collectively acceptable
sets of arguments, called extensions [
Given an AF ⟨A, R⟩, a set ⊆ A is an extension called: • complete (co) iff it is an admissible set and = (); • preferred (pr) iff it is a ⊆ -maximal complete extension; • stable (st) iff it is a total preferred extension, i.e. a preferred extension s.t. ∪ () = A; • semi-stable (sst) iff it is a preferred extension s.t. ∪ () is maximal (w.r.t. ⊆ ); • grounded (gr) iff it is a ⊆ -minimal complete extension.
The set of complete (resp. preferred, stable, semi-stable, grounded) extensions of an AF Λ will be denoted by co(Λ) (resp. pr(Λ), st(Λ), sst(Λ), gr(Λ)). It is well-known that 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 AF Λ the following inclusion relations hold: i) st(Λ) ⊆ sst(Λ) ⊆ pr(Λ) ⊆ co(Λ), ii) gr(Λ) ∈ co(Λ), and iii) st(Λ) ̸= ∅ implies that st(Λ) = sst(Λ). Arguments occurring in an extension are said to be accepted, whereas arguments attacked by accepted arguments are said to be rejected; the remaining arguments are said to be undecided (w.r.t. the considered extension).
Labelling
The argumentation semantics can be also defined in terms of labelling [
Let in(ℒ) = { | ∈ A ∧ ℒ() = in}, out(ℒ) = { | ∈ A ∧ ℒ() = out}, and und(ℒ) = { | ∈ A ∧ ℒ() = und}, a labelling ℒ can be represented by means of a triple ⟨in(ℒ), out(ℒ), und(ℒ)⟩. We also use the notation in() (resp. out(), und()) to denote that ∈ in(ℒ) (resp. ∈ out(ℒ), ∈ und(ℒ)).
Given an AF Λ = ⟨A, R⟩, a labelling ℒ for A is said to be admissible (or legal) if ∀ ∈ in(ℒ) ∪ out(ℒ) it holds that: i) ℒ() = out iff ∃ (, ) ∈ R such that ℒ() = in; and ii) ℒ() = in iff ∀(, ) ∈ R, ℒ() = out holds.
Moreover, ℒ is a complete labelling iff conditions (i) and (ii) hold for all arguments ∈ A.
Between complete extensions and complete labellings there is a bijective mapping defined as follows: for each extension there is a unique labelling ℒ() = ⟨, Def(), A ∖ ( ∪ Def())⟩ and for each labelling ℒ there is a unique extension, that is in(ℒ). We say that ℒ() is the labelling corresponding to . Moreover, we say that ℒ() is a -labelling for a given AF Λ and semantics ∈ {co, pr, st, sst, gr} iff is a -extension of Λ.
In the following, we say that the status of an argument w.r.t. a labelling ℒ (or its corresponding extension in(ℒ)) is in (resp. out, und) iff ℒ() = in (resp. ℒ() = out, ℒ() = und). We will avoid to mention explicitly the labelling (or the extension) whenever it is understood. Example 5. Let Λ5 = ⟨A5, R5⟩ be an AF where A5 = {a, b, c} and R5 = {(a, b), (b, a), (b, c), (c, c)} whose graph is shown in Figure 1 (right). AF Λ5 has three complete extensions: 1 = ∅, 2 = {a}, 3 = { }
b , whose corresponding complete labellings are ℒ1 = ⟨∅, ∅, {a, b, c}⟩, ℒ2 = ⟨{a}, {b}, {c}⟩, and ℒ3 = ⟨{b}, {a, c}, ∅⟩. Also, the set of preferred extensions is {2, 3}, whereas the set of stable (and semi-stable) extensions is {3}, and the grounded extension is 1. Correspondingly, the pr-labelling set is {ℒ2, ℒ3}, the st- and sst-labelling set is {ℒ3}, while the gr-labelling set is {ℒ1}. □
Three fundamental problems in AF are verification , existence and non-empty existence. Given an AF Λ = ⟨A, R⟩, a set ⊆ of arguments, and a semantics ∈ {gr, co, st, pr, sst}: • the verification problem (denoted as V ) is the problem of deciding whether ∈ (Λ), that is, deciding whether is a -extension of Λ; • the existence problem (denoted as EX ) is the problem of deciding whether (Λ) ̸= ∅, that is, deciding whether there exists at least one -extension of Λ; • the non-empty existence problem (denoted as EX¬∅) is the problem of deciding whether there exists ∈ (Λ) s.t. ̸= ∅, i.e. deciding whether there exists a non-empty extension of Λ.
Clearly, for the grounded, complete, preferred and semi-stable semantics, which always admit
at least one extension, the existence problem is trivial—this is not the case of deciding the
nonempty existence problem. The complexity of (non-empty) existence and verification problems for
AF has been thoroughly investigated (see [
We now recall the incomplete argumentation framework [
Definition 1 (iAF). An incomplete AF (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.
Certain arguments in A are definitely known to exist, while uncertain arguments in B are not known for sure: they may occur or may not. Analogously, certain attacks in R are definitely known to exist if their incident arguments exist, while for uncertain attacks in T it is not known for sure if they hold, even if the incident arguments exist.
An iAF ⟨A, B, R, T⟩ is said to be an arg-iAF iff T = ∅, i.e. it does not contain uncertain attacks. We may omit the empty set T and use a triple ⟨A, B, R⟩ to denote an arg-iAF.
An iAF compactly represents alternative AF scenarios, called completions. A completion for an iAF Δ = ⟨A, B, R, T⟩ is an AF Λ = ⟨A′, R′⟩ such that A ⊆ A′ ⊆ A ∪ B and R ∩ (A′ × A′) ⊆ R′ ⊆ (R ∪ T) ∩ (A′ × A′).
Existence problems in iAF have been investigated in [42]. Given an iAF Δ and a semantics ∈ {gr, co, pr, st, sst}, 1. the possible existence problem under , denoted as PEX , consists in deciding whether there exists a completion Λ of Δ that has at least one -extension; 2. the possible non-empty existence problem under , denoted as PEX¬∅, consists in deciding whether there exists a completion Λ of Δ that has a non-empty -extension; 3. the necessary existence problem under , denoted as NEX , consists in deciding whether all completions Λ of Δ have a -extension; 4. the necessary non-empty existence problem under , denoted as NEX¬∅, consists in deciding whether all completions Λ of Δ have a non-empty -extension.
As the completions of (any) iAF prescribe at least one -extension for ∈ {gr, co, pr, sst}, PEX and NEX are trivial under [42].
However, under stable semantics, the existence of at least one extension for any completion is not guaranteed.
Example 6. Let Δ6 = ⟨A5 ∖ {b}, {b}, R5, ∅⟩ be an iAF, where ⟨A5, R5⟩ is the AF of Example 5. The completion ⟨A5, R5⟩ has the stable extension {b} (as observed in Example 5), while the completion ⟨{a, c}, {(c, c)}⟩ has no stable extension. □
It is worth noting that, for any iAF, PEXst is NP-complete and NEXst is Π2-complete. These results follow from Proposition 18 and Theorem 21 in [42] by observing that PEXst(Δ) (resp. NEXst(Δ)) is true iff PEX¬s∅t(Δ) (resp. NEX¬s∅t(Δ)) is true. The complexity of the existence problems for iAF is reported in Table 2.
The following verification problems for iAF have been investigated in [
Example 7. Consider the AF of Example 1 and assume that the participation of Carl is uncertain. This can be modeled by the (arg-)iAF Δ7=⟨{a, b, d}, {c}, {(a, b), (b, c), (c, d), (d, c)}, ∅⟩ whose graph is shown in Figure 2 (left), where the uncertain argument is represented by a dotted circle. Δ7 has 2 completions: Λ′7= ⟨{a, b, c, d}, {(a, b), (b, c), (c, d), (d, c)}⟩ and Λ′7′= ⟨{a, b, d}, {(a, b)}⟩, also shown in Figure 2. Under semantics ∈ {st, pr, sst}, AF Λ′7 has two extensions, 1={a, d} and 2={a, c}, while AF Λ′7′ has only one extension, that is 1. Thus, given iAF Δ7 and either 1 or 2 we have that PV is true, while NV is true for 1 only. That is, 1 and 2 are possible extensions, but only 1 is a necessary one. □
The complexity of PV and NV for iAF has been investigated in [
In this section, we review the Epistemic Argumentation Framework [
Given an AF Λ = ⟨A, R⟩, an epistemic atom over Λ is of the form K or M , where K and M are called modal operators, and is a propositional formula built from = {in(), out(), und() | ∈ A} by using the connectives ¬, ∨, and ∧. Moreover, an epistemic literal is an epistemic atom or its negation. An epistemic formula (over ) is a propositional formula constructed over epistemic literals and connectives ∧ and ∨. Epistemic formulae introduce subjective knowledge of agents, whereas the AF encodes the objective knowledge. Intuitively, K (resp. M ) means that the considered agent believes that is certainly true (resp. is possibly true).
The satisfaction of a propositional formula over w.r.t. a labelling ℒ (denoted as ℒ() |= ) holds if the formula obtained from by replacing every atom occurring in ℒ() with t (true), and every atom not occurring in ℒ() with f (false), evaluates to true.
A set ℒ of labellings satisfies an epistemic formula , denoted as ℒ |= , if one of the following conditions holds: co st pr sst V P
P coNP-c coNP-c
PV NP-c NP-c iAF
NV coNP-c coNP-c that ℒ |= ; otherwise, is inconsistent. The following basic properties hold: ∙ = K and ℒ |= for every ℒ ∈ ℒ , ∙ = 1 ∧ 2 and ( |= 1 and ℒ ℒ ∙ = M and ℒ |= for some ℒ ∈ ℒ , ∙ = 1 ∨ 2 and (ℒ |= 1 or ℒ An epistemic formula is consistent if there exists a (non-empty) set ℒ of labellings such |= 2), |= 2). ∙ ℒ ∙ ℒ |= ¬M iff ℒ |= K¬ , ∙ ℒ |= ¬K iff ℒ |= M¬ , ∙ ℒ |= M( 1 ∨ 2) iff ℒ |= M 1 or ℒ |= M 2, |= K( 1 ∧ 2) iff ℒ |= K 1 and ℒ | = K 2. is an epistemic formula to be satisfied, also called epistemic constraint.
Definition 2 (EAF). An Epistemic AF (EAF) is a triple ⟨A, R, ⟩ where ⟨A, R⟩ is an AF and Let Δ = ⟨A, R, ⟩ be an EAF and
∈ {gr, co, pr, st, sst} be a semantics. A set ℒ of (ii) ℒ labellings is a -epistemic labelling set of Δ if (i) each ℒ ∈ ℒ
is a ⊆ -maximal set of -labellings of ⟨A, R⟩ that satisfies .
As discussed in Section 1, an EAF may have multiple -epistemic labelling sets. In fact, a -epistemic labelling set is a collection of -labellings that represent the belief of an agent. In particular, EAF Δ = ⟨A, R, t⟩ has a unique -epistemic labelling set that coincides with the set of -labellings of the underlying AF ⟨A, R⟩. By definition, an EAF always has a -epistemic labelling set (possibly ∅). For instance, the EAF ⟨A, R, f⟩ has the -epistemic labelling set ∅. is a -labelling of ⟨A, R⟩, and ℒ ̸|= (Kin(a) ∨ Kin(d)).
Example 8. Consider the EAF Δ3 = ⟨
semi-stable)-epistemic labelling sets are given in Example 3. We have that the only grounded epistemic labelling set for Δ3 is ∅, as the grounded labelling ℒ = {und(a), und(b), und(c), und(d)} of the underlying AF Λ3 = ⟨A1, R1 ∪ {(b, a)}⟩ does not satisfy the epistemic constraint, that is, □ In the following, we assume that epistemic constraints are of form = 1 ∨ · · · ∨ , where is a general propositional formula. = K ,0 ∧ · · · ∧
K , ∧ M ,+1 ∧ · · · ∧
We first introduce the possible and necessary verification problems for EAF, and then discuss their complexity.
M , and each , (with ∈ [1..], ∈ [0..])
NP-c NP-c
EX¬∅ NP-c NP-c NP-c NP-c
PEX NP-c
T T T
NEX
T iAF stable (st), preferred (pr), and semi-stable (sst) semantics. For any complexity class , -c means -complete. T stands for trivial. New results are highlighted in grey.
Definition 3
(Possible/Necessary Verification) . Given an EAF Δ, a semantics co, st, pr, sst}, and a labelling ℒ, ∈ {gr, 1. the possible verification problem under (denoted as PV ) consists in deciding whether there is a -epistemic labelling set ℒ of Δ such that ℒ ∈ ℒ ; all -epistemic labelling sets ℒ
of Δ it holds that ℒ ∈ ℒ . 2. the necessary verification problems under (denoted as NV ) consists in deciding whether for PV (resp. NV ) over such instance.
Given a pair (Δ, ℒ), we use PV (Δ, ℒ) (resp. NV (Δ, ℒ)) to denote the output of problem Δ3. That is, PV is true for ℒ1, ℒ2, and ℒ3, while NV is true for ℒ2 only.
Example 9. Let Δ3 = ⟨
has two -epistemic labelling sets (under semantics ∈ {pr, st, sst}): {ℒ1, ℒ2} and {ℒ2, ℒ3}. Then ℒ1, ℒ2, and ℒ3 are possible -labellings of Δ3, while only ℒ2 is a necessary -labelling of □
As shown in Table 1, that summarizes the complexity of the possible and necessary verification
problems for EAF [
The existence of solutions in EAF corresponds to determine the existence of -epistemic labelling sets. As there could be several -epistemic labelling sets, we consider two problems, namely possible existence and necessary existence, respectively checking whether i) there exists a not empty -epistemic labelling set, and ii) all -epistemic labelling sets are not empty. Moreover, for each problem, we also consider the non-empty labelling variant, namely possible non-empty existence and necessary non-empty existence, respectively checking whether i) there exists a not empty -epistemic labelling set containing a non-empty -labelling, and ii) all -epistemic labelling sets contain a non-empty -labelling. Herein, for an empty labelling we mean a labelling where all arguments are labelled as undecided. Observe that if a labelling prescribes that an argument is not labelled as undecided, then it must also prescribe that there is an argument (not necessarily distinct from ) which is labelled in. Therefore, we say that a labelling ℒ is empty iff und(ℒ) is the whole set of arguments, which in turn means that in(ℒ) is empty. Definition 4 (Possible/Necessary Existence). Let Δ = ⟨A, R, ⟩ be an EAF and ∈ {gr, co, st, pr, sst} a semantics, 1. the possible existence problem, denoted as PEX , consists in deciding whether there exists a -epistemic labelling set ℒ for Δ such that ℒ ̸= ∅; 2. the possible non-empty existence problem, denoted as PEX¬∅, consists in deciding whether there exists a -epistemic labelling set for Δ having at least one -labelling ℒ such that in(ℒ) ̸= ∅; 3. the necessary existence problem, denoted as NEX , consists in deciding whether for all -epistemic labelling set ℒ for Δ it holds that ℒ ̸= ∅; 4. the necessary non-empty existence problem, denoted as NEX¬∅, consists in deciding whether all -epistemic labelling sets for Δ have at least one -labelling ℒ such that in(ℒ) ̸= ∅.
Given an EAF Δ, we use PEX (Δ) (resp. PEX¬∅(Δ), NEX (Δ), NEX¬∅(Δ)) to denote the output of problem PEX (resp. PEX¬∅, NEX , NEX¬∅) over such instance.
In the rest of this section, we discuss the complexity of the existence problems in EAF [
Moreover, it is worth noting that the grounded-epistemic labelling set is unique, that is, for any EAF ⟨A, R, ⟩ the gr-epistemic labelling set is {ℒ(gr(⟨A, R⟩))} if ℒ(gr(⟨A, R⟩))|= ; ∅ otherwise. Although the presence of constraints in EAF breaks the meet-semilattice of complete extensions, reasoning under the grounded semantics remains tractable. Indeed, checking whether a given labelling set satisfies a given epistemic formula can be decided in polynomial time, and checking whether an EAF admits a non-empty grounded-epistemic labelling set can be done in polynomial time as well.
Therefore, since if a grounded-epistemic labelling set for an EAF exists then it is unique, deciding the possible existence problem in EAF under the grounded semantics is still polynomial.
As shown in Table 2, that summarizes the complexity of the possible and necessary non-empty existence problems for EAF, deciding the possible or necessary existence problem in EAF is harder than in iAF (and AF), except for stable semantics for which deciding existence in EAF behaves as in AF. Moreover, it turns out that non-emptiness is not a source of complexity in EAF (i.e. deciding non-empty existence is not harder than deciding existence), while for iAF deciding non-empty existence is generally harder than deciding existence (except for stable semantics where the existence of a solution is not guaranteed in AF).
In this section, we analyze the relationship between EAF and iAF. We focus on multiple status
semantics only, avoiding considering the grounded semantics that behaves differently in the
two frameworks. Indeed, differently from EAF where the grounded semantics remains unique
status as in AF, for iAF the grounded semantics prescribes multiple extensions (one for each
completion). Thus comparing EAF and iAF under grounded semantics would mean comparing
a deterministic semantics with a non-deterministic one, that, in our opinion, does not fit well
with our current setting where semantics prescribing multiple solutions are meant to represent
uncertain information.
(Δ) [
The following result states that EAF can be used to decide possible and necessary verification
over iAF. Although the result is given for a special class of iAF (i.e. arg-iAF), we recall that
∈ B}; R* = R ∪ {(, ), (, ), (, ) | ∈ B}; and = K︁( ⋀︀
arg-iAF is as expressive as (general) iAF [
Let Δ = ⟨A, B, R⟩ be an iAF, ⊆ a semantics. For any completion Λ = ⟨
AΛ, RΛ⟩ of Δ, it holds that ∈ (Λ) iff ℒ() ∪ {out(), in() | ∈ B ∩ AΛ} ∪ {in(), out(), out() | ∈ B ∖ AΛ} is a -labelling for whose underlying AF is shown in Figure 3. For Example 10. Consider the iAF Δ7 of Example 7 and the corresponding EAF Δ10 = (Δ7) = ⟨{a, b, c, d, xc, xc}, {(a, b), (b, c), (c, d), (d, c), (xc, xc), (xc, xc), (xc, c)}, = K¬und(xc)⟩, ∈ {st, pr, sst}, Δ10 has the -epistemic whose labellings correspond (modulo arguments xc and xc) to -labellings of Δ7. labelling set {ℒ′1 = {in(a), out(b), out(c), in(d), out(xc), in(xc)}, ℒ′2 = {in(a), out(b), in(c), out(d), out(xc), in(xc)}, ℒ′1′ = {in(a), out(b), out(c), in(d), in(xc), out(xc)}, □
From the above-mentioned result, we have that EAF can encode iAF possible/necessary verification. In fact, according to the results of Section 3, verification in EAF is more expressive than in iAF for each considered semantics (cf. Table 2).
Work on epistemic logic dates back to the early 1860s. Since then epistemic logic has played an important role also in computer science. This field is very active and important results are reported in a recent book surveying state-of-the-art research [44]. Epistemic Logic extends propositional logic by allowing to also express knowledge of agents, also called subjective knowledge. The idea of extending logic with epistemic constructs has been investigated also in the field of Answer Set Programming (ASP) [ 45, 46]. Epistemic logic programs, firstly proposed in [45], extend disjunctive logic programs under the stable model semantics with modal constructs called subjective literals [47, 48, 49, 46]. In such a context, several problems are still open and they regard the support required by stable models, as well as splitting properties that are satisfied by classical ASP semantics, but not satisfied by epistemic ASP-based semantics [50, 49, 51].
Constraints have been also used in the context of dynamic AFs to refer to the enforcement of
some change [52]. In this context, extension enforcement aims at modifying an AF to ensure that
a given set of arguments becomes (part of) an extension for the chosen semantics [53, 54, 55, 56].
This is different from the EAF approach [
AF with epistemic attacks (EAAF) has been recently introduced in [
It turns out that verification in iAF can be reduced to verification in EAF, providing a connection between these two AF-based frameworks. It is worth noting that the connections between AF, iAF and EAF carry over to other AF-based frameworks that can be mapped to AF [61], such as Bipolar AF [62] and AF with recursive attacks and supports [63]. However, despite the relationship concerning verification, the complexity analysis also shows that possible and necessary (nonempty) existence behave quite differently for iAF and EAF—this is intuitively due to the different semantics of the two frameworks. For instance, under standard complexity assumption, for some semantics, necessary non-empty existence in iAF cannot be reduced to the corresponding problem in EAF, while possible existence in EAF cannot be reduced to the corresponding problem in iAF. Acknowledgement. The research reported in the paper was partially supported by the PNRR project “Tech4You (ECS00000009) - Spoke 6”, under the NRRP MUR program funded by the NextGenerationEU, and by the PNRR project FAIR - Future AI Research (PE00000013). [42] K. Skiba, D. Neugebauer, J. Rothe, Complexity of nonempty existence problems in incomplete argumentation frameworks, IEEE Intell. Syst. 36 (2021) 13–24. [43] B. Fazzinga, S. Flesca, F. Furfaro, Revisiting the notion of extension over incomplete abstract argumentation frameworks, in: Proc. of IJCAI, 2020, pp. 1712–1718. [44] H. van Ditmarsch, J. Y. Halpern, W. van der Hoek, B. P. Kooi (Eds.), Handbook of Epistemic
Logic, kings College Pubn, 2015. [45] M. Gelfond, Strong introspection, in: Proc. of AAAI, 1991. [46] J. Fandinno, W. Faber, M. Gelfond, Thirty years of epistemic specifications, CoRR abs/2108.07669 (2021). [47] M. Gelfond, New semantics for epistemic specifications, in: Proc. of LPNMR Conf., volume 6645, 2011, pp. 260–265. [48] P. Cabalar, J. Fandinno, L. F. del Cerro, Autoepistemic answer set programming, Artif.
Intell. 289 (2020) 103382. [49] P. Cabalar, J. Fandinno, L. F. del Cerro, Splitting epistemic logic programs, Theory Pract.
Log. Program. 21 (2021) 296–316. [50] Y. Shen, T. Eiter, Constraint monotonicity, epistemic splitting and foundedness are too strong in answer set programming, CoRR abs/2010.00191 (2020). [51] A. Herzig, A. Yuste-Ginel, On the epistemic logic of incomplete argumentation frameworks, in: Proc. of KR, 2021, pp. 681–685. [52] S. Doutre, J. Mailly, Constraints and changes: A survey of abstract argumentation dynamics,
Arg. & Comp. 9 (2018) 223–248. [53] R. Baumann, G. Brewka, Expanding argumentation frameworks: Enforcing and monotonicity results, in: Proc. of COMMA, 2010, pp. 75–86. [54] R. Baumann, Normal and strong expansion equivalence for argumentation frameworks,
Artif. Intell. 193 (2012) 18–44. [55] J. P. Wallner, A. Niskanen, M. Järvisalo, Complexity results and algorithms for extension enforcement in abstract argumentation, J. of Artif. Intell. Res. 60 (2017) 1–40. [56] A. Niskanen, J. P. Wallner, M. Järvisalo, Extension enforcement under grounded semantics in abstract argumentation, in: Proc. KR, 2018, pp. 178–183. [57] L. Amgoud, C. Cayrol, Inferring from inconsistency in preference-based argumentation frameworks, J. Aut. Reas. 29 (2002) 125–169. [58] S. Modgil, Reasoning about preferences in argumentation frameworks, Artif. Intell. 173 (2009) 901–934. [59] L. Amgoud, S. Vesic, Rich preference-based argumentation frameworks, Int. J. Approx.
Reason. 55 (2014) 585–606. [60] S. Kaci, L. W. N. van der Torre, S. Villata, Preference in abstract argumentation, in: Proc.
COMMA, 2018, pp. 405–412. [61] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On the semantics of abstract argumentation frameworks: A logic programming approach, Theory and Practice of Logic Programming 20 (2020) 703–718. [62] A. Cohen, S. Gottifredi, A. J. García, G. R. Simari, A survey of different approaches to support in argumentation systems, Knowl. Eng. Rev. 29 (2014) 513–550. [63] A. Cohen, S. Gottifredi, A. J. Garcia, G. R. Simari, An approach to abstract argumentation with recursive attack and support, J. Appl. Log. 13 (2015) 509–533.