The success and popularity of Dung's abstract Argumentation Framework (AF) is also due to its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. Constraints can be expressed in the so-called Constrained Argumentation Framework (CAF). Although constraints in CAF allow restricting the set of feasible solutions, they can not be used to find “optimal” solutions to problems defined through CAFs. In this paper we present Weak constrained AFs (WAFs) that enhance CAFs with weak constraints, that express some optimal conditions. We discuss the complexity of WAFs under several well-known argumentation semantics, showing that weak constraints increase the expressive power of AFs and CAFs.
x
y z z (a) x z x z (b) y w y w ¯ and ¯ can be accepted and then, as a consequence, at least two arguments among , and can be accepted. □
The meaning of an AF is given in terms of argumentation semantics, which intuitively tell us the sets of arguments (called extensions) that can collectively be accepted. The preferred (and stable) extensions of AF Λ of Example 1 are 1 = {, , ¯}, 2 = {, ¯, }, 3 = {¯, , }, and 4 = {, , }. However, 4 is not feasible as only two seats are available and thus only two people could attend the event. To overcome such a situation, and thus providing a natural and compact way for expressing such kind of conditions, the use of constraints has been proposed [4, 6, 5, 7].
Example 2. Continuing from Example 1, the constraint = ∧ ∧ ⇒ f can be used. It states that the propositional formula ∧ ∧ must be false. That is, feasible solutions must satisfy the condition that the 3 arguments , , and are not jointly accepted, i.e., the three people cannot attend the event together. The effect of using constraint is that 4 is discarded from the set of solutions of our problem. □
We call an AF augmented with constraints a Constrained AF (CAF). Although constraints in a CAF allow restricting the set of feasible solutions, they do not help in finding “best” or preferable solutions. Considering our running example, the three people may agree on the fact that “ and should preferably attend the event whenever there are only two seats available”. To express this kind of conditions, we introduce weak constraints, that is, constraints that are required to be satisfied if possible. Syntactically, they have the same form of (strong) constraints except that the implication symbol → is used (instead of ⇒). Intuitively, these constraints can be used to find “optimal” solutions to a problem defined by means of an AF or a CAF. A CAF with the addition of weak constraints is said to be a Weak constrained Argumentation Framework (WAF). Example 3. Consider a WAF obtained by adding to the CAF of Example 2 the weak constraint t → ∧ , stating that it is desirable that and attend the event together. Herein, t denotes the truth value true. Then, extension 1 = {, , ¯} is selected as the “best” one. □
The use of strong and weak constraints substantially reduces the effort needed to figure out how to define an AF that models a given problem. In fact, as said earlier, constraints facilitate to express knowledge in a more compact and easy to understand way. For instance, the problem presented in Example 1, has been represented through an AF which expresses the condition that “at most one argument among ¯, ¯, ¯ can be accepted” and then, as a consequence, at least two arguments , , can be accepted. However, this condition is not easy to be generalized if we have more than three people. Suppose there is a fourth guy, , who wish to attend the event, and there are again only two available seats. After adding the arguments and ¯ to Λ of Figure 1(a), we cannot use the same reasoning as in Example 1 to model the fact that two of the four people attend the event. In fact, having the attacks between every pair in {¯, ¯, ¯, ¯} does not model this situation (it models that at least three of the four people attend the event). Remarkably, using strong and weak constraints allow for using a common reasoning pattern to generalize to this more complex situation, even starting from an AF having a simpler structure. Example 4. Consider a WAF consisting of AF Λ′ of Figure 1(b) and the sets of strong and weak constraints; = { , ∧ ∧ ⇒ f, ∧ ∧ ⇒ f, ∧ ∧ ⇒ f}; and = {t → , t → , t → , t → }. The strong constraints in (that includes of Example 2) filter out from the (16 preferred) extensions of Λ′ the solutions where more than two people attend the event, whereas the weak constraints maximize the set (or number) of people attending the event. □
In this paper, we present WAFs along with two criteria for interpreting weak constraints, under any argumentation semantics : maximal-set (ms) and maximum-cardinality (mc) according to which the best/optimal -extensions are those satisfying a maximal set, or a maximum number, of weak constraints respectively. Then, we discuss the complexity of credulous and skeptical reasoning for WAFs, showing that the introduction of weak constraints typically increases the complexity of at least one step in the polynomial hierarchy w.r.t. AF.
We briefly review Dung’s framework and discuss Constrained Argumentation Frameworks.
An abstract Argumentation Framework (AF) is a pair ⟨, ℛ⟩, where is a set of arguments and ℛ ⊆ × is a set of attacks. If (, ) ∈ ℛ then we say that attacks . We can think of an AF as a directed graph whose nodes represent arguments and edges represent attacks.
Given an AF Λ = ⟨, ℛ⟩ and a set ⊆ of arguments, an argument ∈ is said to be i) defeated w.r.t. iff ∃ ∈ such that (, ) ∈ ℛ, and ii) acceptable w.r.t. iff for every argument ∈ with (, ) ∈ ℛ, there is ∈ such that (, ) ∈ ℛ. The sets of defeated and acceptable arguments w.r.t. are defined as follows (where Λ is understood): • () = { ∈ | ∃ ∈ . (, ) ∈ ℛ}; • () = { ∈ | ∀ ∈ . (, ) ̸∈ ℛ ∨ ∈ ()}.
Given an AF ⟨, ℛ⟩, a set ⊆ of arguments is said to be: conflict-free iff ∩ () = ∅; ∙ 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 set ⊆ is an extension called: • complete (co) iff it is an admissible set and = (); • preferred (pr) iff it is a maximal (w.r.t. ⊆ ) complete extension; • stable (st) iff it is a total preferred extension, i.e. a preferred extension such that ∪ () = ; • semi-stable (sst) iff it is a preferred extension such that ∪ () is maximal; • grounded (gr) iff it is the smallest (w.r.t. ⊆ ) complete extension.
It is well-known that the set of complete extensions forms a complete semilattice with respect to set inclusion. Arguments occurring in an extension are said to be accepted, whereas arguments attacked by accepted arguments are said to be rejected; remaining arguments are said to be undecided (w.r.t. the considered extension).
Example 5. Let Λ = ⟨, ℛ⟩ be an AF where = {, , } and ℛ = {(, ), (, ), (, ), (, )}. AF Λ has three complete extensions: 1 = ∅, 2 = {}, 3 = {}. 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. □
Constrained Argumentation Framework (CAF) has been introduced in [4] and further investigated in [5, 9]. The constrained argumentation frameworks in [6] and [7] are particular cases of those in [5] as the set of constraints is restricted to atomic formulae only.
Given a set of propositional symbols , ℒ denotes the propositional language defined in the usual inductive way from using the built-in constants f, u, and t denoting the truth values false, undef (undefined ), and true, and the connectives ∧, ∨, ¬, ⇒ and ⇔.
A general form of Constrained Argumentation Framework (CAF) has been considered in [4, 5]. A CAF is a triple Ω = ⟨, ℛ, ⟩ where ⟨, ℛ⟩ is an AF and is a set of (general) propositional formulae built from ℒ.
Given an AF ⟨, ℛ⟩ and a set ⊆ , the truth value of an argument ∈ w.r.t. is denoted by (), or simply () whenever is understood, and () is ) true if ∈ ; ) false if ∃ ∈ such that (, ) ∈ ℛ; or ) undef otherwise.
It is important to note that, regarding the operator ⇒ there is no convergence on its semantics in CAFs (see Section 5 for a discussion). Thus, in the following we consider a simpler yet sufficiently general form of constraints than that in [4, 5] (e.g. we do not deal with constraints with multiple implications) and the classical interpretation of Lukasiewicz’s logic for the implication operator.
Let ℒ′ be the propositional language defined from and the connectives ∧, ∨, ¬, where is a set of arguments.
Definition 1. A (strong) constraint is a formula of one of the following forms: () ⇒ , where is a propositional formula in ℒ ′ and ∈ {f, u, t}.
⇒ , or ()
Checking whether a constraint is satisfied (under the Lukasiewicz’logic) is equivalent to check whether the truth value of the head is greater than or equal to the truth value of the body. For formulae defining constraints we believe that Lucasiewicz interpretation is more appropriate as, for instance, it allows to distinguish ⇒ f from ⇒ u, and avoids problems existing in other interpretations [10].
Example 6. The constraint ∧ ∧ ⇒ f states that at least one of the arguments , and must be false, whereas ∧ ∧ ⇒ u states that , and cannot be all true. □ Clearly, constraints of the forms f ⇒ and ⇒ t are useless because always satisfied.
In the following, we assume that is a set of satisfiable constraints built from ℒ′ and every CAF is a triple Ω = ⟨, ℛ, ⟩.
Definition 2. Given a CAF Ω = ⟨, ℛ, ⟩ (where contains constraints built from ℒ′), a set of arguments ⊆ is a complete (resp., grounded, preferred, stable, semi-stable) extension for Ω if is a complete (resp., grounded, preferred, stable, semi-stable) extension for ⟨, ℛ⟩ and is satisfied by (denoted as |= ).
In this section, we introduce a generalization of CAFs where weak constraints are also considered. Differently from the strong constraints discussed in the previous section, weak constraints are propositional formulae that should be satisfied if possible.
Weak constraints (also called relaxed constraints in some contexts) have been considered in several research areas, including Mathematical Programming with Equilibrium Constraints [11], Answer Set Programming [12, 13], and for modelling and solving optimization problems [14, 15]. In particular, concerning the field of Answer Set Programming, weak constraints have been implemented in DLV [16] and clingo [17]; moreover, learning them from data is also possible [18].
In our setting, weak constraints are logical formulae of the form → (or, equivalently, → ), where is a propositional formula built using the symbols of a given set and the connectives ∧, ∨ and ¬. Herein, → denotes the logical implication connective. Observe that we use the symbol → (instead of ⇒) to have different syntaxes for weak and strong constraints. Definition 3. A Weak constrained Argumentation Framework (WAF) is a tuple Γ = ⟨, ℛ, , ⟩, where ⟨, ℛ, ⟩ is a CAF and is a set of weak constraints built from ℒ′.
The semantics of a WAF is defined by considering two possible criteria for selecting the preferable extensions w.r.t. weak constraints—only weak constraints are considered when selecting the preferable extensions since strong constraints must be all satisfied. The two criteria considered for assessing to which extent an extension satisfies a set of weak constraints are: (i) maximal set criterion, considering as preferable (or “best”) extensions the ones that satisfy a maximal set of weak constraints, and (ii) maximum-cardinality criterion, considering as preferable (or “optimal”) extensions the ones that satisfy a maximal number of weak constraints.
Clearly, the selection of preferable extensions make sense only for semantics admitting multiple extensions, that is, complete, preferred, stable, and semi-stable semantics. Thus, in the following, whenever we consider a generic semantics , we refer to ∈ {co, pr, st, sst}.
In the next subsections, we formally define the meaning of a WAF under the maximal-set and maximum-cardinality semantics and provide two examples.
Definition 4 (Maximal-Set Semantics). Given a WAF Γ = ⟨, ℛ, , ⟩, an -extension for ⟨, ℛ, ⟩ is a maximal-set -extension (ms-extension) for Γ if, let ⊆ be the set of weak constraints that are satisfied by (that is, |= ) , there is no -extension for ⟨, ℛ, ⟩ and ⊆ such that |= and ⊂ .
Given a semantics , ms denotes the maximal-set version of (e.g. msco denotes the ms complete semantics).
Example 7. Consider the WAF Γ = ⟨, ℛ, , ⟩ with = {, , , }, ℛ = {(, ), (, ), (, ), (, )}, = ∅ and = {1 = → f, 2 = ∨ ¬ → u} stating that should preferably be false (1) and should preferably be undefined ( 2). ⟨, ℛ, ⟩ has 9 complete extensions: 0 = {}, 1 = {}, 2 = {}, 3 = {}, 4 = {}, 5 = {, }, 6 = {, }, 7 = {, } and 8 = {, }.
In particular, 0 is the grounded extension, whereas 5, 6, 7, 8 are preferred, stable, and semi-stable extensions of ⟨, ℛ, ⟩. These are also extensions of AF ⟨, ℛ⟩, since = ∅.
Regarding the satisfaction of weak constraints, we have that 0 |= {2}, 4 |= {1, 2}, 6 |= {1}, and 8 |= {1}, whereas the other complete extensions do not satisfy any constraint. Therefore, the maximal-set preferred (stable, semi-stable) extensions are 6 and 8, whereas there is only one maximal-set complete extension, which is 4. □
Maximum-cardinality semantics for WAFs prescribes as preferable extensions those satisfying the highest number of weak constraints. This is similar to the semantics of weak constraints in DLV [16] where, in addition, each constraint has assigned a weight.
Definition 5 (Maximum-Cardinality Semantics). Given a WAF Γ = ⟨, ℛ, , ⟩, an extension for ⟨, ℛ, ⟩ is a maximum-cardinality -extension (mc-extension) for Γ if, let ⊆ be the set of weak constraints in that are satisfied by , there is no -extension for ⟨, ℛ, ⟩ and ⊆ such that |= and | | < | |.
Example 8. Consider the WAF Γ = ⟨, ℛ, , ⟩ with = {, , }, ℛ = {(, ), (, ), (, ), (, )}, = ∅ and = {1 = t → , 2 = t → , 3 = → f} stating that it is desirable that is true, is true, and is false.
⟨, ℛ, ⟩ has three complete extensions: 1 = {}, 2 = {}, and 3 = {}. Herein, 2 and 3 are the preferred extensions of ⟨, ℛ, ⟩, whereas the unique stable (and semi-stable) extension is 3. Regarding the satisfactions of weak constraints we have that 1 |= 0 = ∅, 2 |= 1 = {1}, and 3 |= 3 = {2, 3}. Therefore, the only maximum-cardinality preferred extension of Γ is 3 (as |3| = 2 > |1| = 1 > |0| = 0). Note that, according to the maximal-set semantics, both 2 and 3 are maximal-set preferred extensions. Regarding the stable (and semi-stable) semantics, as there is only one extension, 3 is both a maximal-set and a maximum-cardinality extension. □
In this section we discuss the complexity of the credulous and skeptical acceptance problems. We assume the reader is familiar with the main complexity classes [19], which are briefly recalled in what follows.
Classes Σ , Π and Δ , with ≥ 0 are defined as follows: Σ = Π = Δ0 = ; 0 0 Σ1 = and Π1 = ; Δ = Σ− 1 , Σ = Σ− 1 , and Π = Σ , ∀ > 0. Thus, (resp., ) denotes the class of problems that can be solved in polynomial time using an oracle in the class by a deterministic (resp., non-deterministic) Turing machine. The class Δ [ ] denotes the subclass of Δ containing the problems that can be solved in polynomial time by a deterministic Turing machine by performing a number of calls bounded by ( ) to an oracle in the class Σ− 1. It is known that: Σ ⊂ Δ+1[ ] ⊂ Δ+1 ⊂ Σ+1 ⊆ and Π ⊂ Δ+1[ ] ⊂ Δ+1 ⊂ Π+1 ⊆ .
We now recall the definition of credulous and skeptical acceptance problems. Given an AFbased framework Λ (e.g., AF, CAF, WAF), an argument , and an argumentation semantics ∈ {co, pr, st, sst, gr}, • the credulous acceptance problem, denoted as , is the problem of deciding whether argument is credulously accepted, that is, deciding whether belongs to at least an -extension of Λ. • the skeptical acceptance problem, denoted as , is the problem of deciding whether argument is skeptically accepted, that is, deciding whether belongs to every -extension of Λ.
For AFs, the complexity of the credulous and skeptical acceptance problems has been investigated
in [
As for the complexity of CAFs, it is important to note that, given a CAF Ω = ⟨, ℛ, ⟩, if we consider the corresponding AF Λ = ⟨, ℛ⟩, then the set of complete extensions of Λ that satisfy does not always form a complete meet-semilattice. This means that the constraints break the lattice by marking as unfeasible some extensions. As a result, the complexity of credulous and skeptical acceptance problems in CAF is slightly different from that of AF as co becomes NP-complete and pr is shown to be in Σ2 (and still NP-hard) [9].
Concerning WAFs, given an -extension, checking satisfaction of a maximal-set of weak constraints means ensuring that no any other -extension is better according to that criterion. This is an additional source of complexity that makes, in most cases, credulous and skeptical reasoning in WAFs one level higher in the polynomial-time hierarchy than AFs. Theorem 1. For any WAF ⟨, ℛ, , ⟩, the problem • ms is: () Σ2 -complete for any semantics ∈ {co, st}, () Σ2 -hard and in Σ3 for = pr, and () Σ3 -complete for = sst.
• ms is: () Π2 -complete for ∈ {co, st}, and () Π3 -complete for ∈ {pr, sst}.
It turns out that, under standard complexity assumptions, computing credulous and skeptical acceptance in WAFs under maximum-cardinality semantics is easier than using maximal-set semantics. Roughly speaking, this follows from the fact that a binary search strategy can be used for deciding whether the cardinality of a set of constraints satisfied by an -extension containing a given argument is maximum.
Theorem 2. For any WAF ⟨, ℛ, , ⟩ with | | = , the problems mc and mc are: - Δ2 [log ]-complete for any semantics ∈ {co, st}, - Δ3 [log ]-complete for ∈ {pr, sst}.
Restricted forms of WAFs, that is, Linearly ordered WAFs where constraints are linearly ordered, for which maximal-set and maximum-cardinality semantics coincide, are investigated in [9]: and are Δ2 -complete for the complete and stable semantics and Δ3 -complete for the preferred and semistable semantics. It is also shown that, for the case of WAFs where constraints are expressed by negative constraints (i.e., denials constraints whose body is a conjunction of literals), the complexity of credulous acceptance for the preferred semantics decreases to Σ2 -complete.
The use of constraints in AFs has been firstly proposed in [ 4] and then further investigated in [6, 5, 7]. As mentioned in Section 2.2, there is no convergence on the semantics of operator ⇒ for constraints in CAFs. The semantics proposed in [4] relies on classical 2-valued logic for the evaluation of constraints by making use of the concept of completion of extensions, which converts undefined truth values to negated truth values. More formally, for any set of arguments ⊆ , the completion of is ^ = ∪ {¬ | ∈ ∖ }. Then, satisfies a set of constraints if and only if ^ is a (2-valued) model of . A drawback of this semantics is that in checking whether an extension satisfies a set of constraints it does not distinguish between false and undefined arguments, e.g., a constraint of the form ∧ ¬ ⇒ f is always satisfied, even when () = undef (e.g. assuming an extension = ∅ stating that is undefined, ^ = {¬} and then the 2-valued semantics is applied w.r.t. ^).
The semantics proposed in [5] assumes the standard 3-valued Kleene’s semantics for the connectives ∧, ∨ and ¬, whereas for ⇒ it assumes the Slupecki’s interpretation which is defined as follows: ( ⇒ ) is true if ( ) ∈ {false, undef}, otherwise it is ( ). Thus, while a constraint of the form t ⇒ ∨ ¬ is useless according to [4] (since it is always satisfied), in the Arieli’s 3-valued semantics this constraint indicates that argument cannot have a neutral, undefined, status. The use of 3-valued semantics allows us to distinguish between different conditions on arguments. For instance, the constraint t ⇒ ¬ means that should be rejected, while the constraint ⇒ f is a somewhat weaker demand: should not be accepted, and so its status may be undecided. A drawback of Arieli’s semantics, due to the assumption of the Slupecki’s logic for interpreting the implication operator, is that it does not distinguish two constraints of the form ⇒ f and ⇒ u, though it distinguishes two constraints of the form t ⇒ and u ⇒ . In order to avoid the above-mentioned problems, we considered the interpretation of Lukasiewicz’s logic for the implication operator.
Besides being related to the proposals for CAFs in [4, 5], our work is also related to the approach in [24] that provides a method for generating non-empty conflict-free extensions for CAFs. Constraints have been also used in the context of dynamic AFs to refer to the enforcement of some change [25]. 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 [26, 27, 28, 29, 30]. This is different from our approach where integrity constrains are used to discard unfeasible solutions (extensions), without enforcing that a new set of arguments becomes an extension.
Weak constraints allow for selecting “best” or “optimal” extensions satisfying some conditions on arguments, if possible. This can be viewed as expressing a kind of preference over the set of extensions. Dung’s framework has been extended in several ways for allowing preferences over arguments [31, 32, 33, 34]. In particular, preferences relying to so-called critical attacks, i.e., attacks from a less preferred argument to a more preferred one, can be handled by removing or invalidating such attacks or by “inverting” them [35]. Such kind of preferences can be encoded into AFs, possible through reductions relying on additional (meta)-arguments and attacks [36]. Thus these preferences do not increase expressiveness of AFs from a computational standpoint.
Preferences can be also expressed in value-based AFs [37, 38], where each argument is associated with a numeric value, and a set of possible orders (preferences) among the values is defined. In [39] weights are associated with attacks, and new semantics extending the classical ones on the basis of a given numerical threshold are proposed. [40] extends [39] by considering other aggregation functions over weights apart from sum. Except for weighted solutions under grounded semantics (that prescribes more than one weighted solution), the complexity of credulous and skeptical reasoning in the above-considered AF-based frameworks is lower than that of WAFs, which suggests that WAFs are more expressive and can be used to model those frameworks (we plan to formally investigate these connections in future work).
We have introduced a general argumentation framework where weak constraints can be easily expressed. These constraints impact on the complexity of credulous and skeptical reasoning: it turns out that they generally increase the expressivity of AFs and CAFs. WAFs allow us to model optimization problems such as for instance Min Coloring and Maximum Satisfiability, where some kind of preferences (e.g. use the minimum number of colors) are expressed on solutions. This is not possible for AFs whose expressivity is lower than that of WAFs (AFs can capture simpler problems such as k-coloring and SAT).
We envisage implementations of the proposed WAF semantics by exploiting ASP-based systems and analogies with logic programs with weak constraints [12, 13] (the relationship between the semantics of some frameworks extending AF and that of logic programs has been recently investigated in [41]). For WAFs, DLV system [16] could be used for computing maximumcardinality stable semantics.
Although we considered ground constraints, the framework can be easily extended for general formulae with variables, whose ground version is a propositional set. For instance, the strong and weak constraints in Example 4 could be written by using only one strong constraint ∧ ∧ ∧ ( ̸= ) ∧ ( ̸= ) ∧ ( ̸= ) ⇒ f and only one weak constraint t → , where , and are variables whose domain is the set of arguments. Future work will be also devoted to considering more general forms of constraints, not only using variables ranging on the sets of arguments, but also constraints allowing to express conditions on aggregates (e.g., at least arguments from a given set should be accepted/rejected).
Finally, given the inherent nature of argumentation and the typical high computational complexity of most of the reasoning tasks [42, 43, 44, 45], there have been several recent efforts toward the investigation of incremental techniques that use AF solutions (e.g. extensions, skeptical acceptance) at time to recompute updated solutions at time + 1 after that an update (e.g. adding/ removing an attack) is performed [46, 47, 48, 49, 50, 51, 25]. These approaches have been extended to argumentation frameworks more general than AFs [52, 53, 54, 55]. Following this line of research, we plan to investigate incremental techniques for recomputing WAF semantics after performing updates consisting of changes to the AF component or to the sets of strong and weak constraints. [3] S. Modgil, H. Prakken, A general account of argumentation with preferences, Artif. Intell.
195 (2013) 361–397. [4] S. Coste-Marquis, C. Devred, P. Marquis, Constrained argumentation frameworks, in: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2006, pp. 112–122. [5] O. Arieli, Conflict-free and conflict-tolerant semantics for constrained argumentation frameworks, J. Appl. Log. 13 (2015) 582–604. [6] O. Arieli, Towards constraints handling by conflict tolerance in abstract argumentation frameworks, in: Proc. of International Florida Artificial Intelligence Research Society Conference (FLAIRS), 2013. [7] O. Arieli, On the acceptance of loops in argumentation frameworks, J. Log. Comput. 26 (2016) 1203–1234. [8] M. Caminada, Semi-stable semantics, in: Proc. of Computational Models of Argument (COMMA), 2006, pp. 121–130. [9] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Argumentation frameworks with strong and weak constraints: Semantics and complexity, in: Proc. of AAAI Conference on Artificial Intelligence (AAAI), 2021, pp. 6175–6184. [10] A. Avron, Natural 3-valued logics–characterization and proof theory, The Journal of
Symbolic Logic 56 (1991) 276–294. [11] A. Ramos, Two new weak constraint qualifications for mathematical programs with equilibrium constraints and applications, J. Optim. Theory Appl. 183 (2019) 566–591. [12] F. Buccafurri, N. Leone, P. Rullo, Enhancing disjunctive datalog by constraints, IEEE Trans.
Knowl. Data Eng. 12 (2000) 845–860. [13] S. Greco, Non-determinism and weak constraints in datalog, New Gener. Comput. 16 (1998) 373–396. [14] W. Faber, M. Vallati, F. Cerutti, M. Giacomin, Solving set optimization problems by cardinality optimization with an application to argumentation, in: Proc. of European Conference on Artificial Intelligence (ECAI), 2016, pp. 966–973. [15] M. Li, R. Lv, The binary algorithm for finding the best weak-constraints in contradictory weak-constrained optimization problems, in: Proc. of International Conference on Natural Computation (ICNC), 2014, pp. 475–479. [16] M. Alviano, F. Calimeri, C. Dodaro, D. Fuscà, N. Leone, S. Perri, F. Ricca, P. Veltri, J. Zangari, The ASP system DLV2, in: Proc. of International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), 2017, pp. 215–221. [17] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Multi-shot ASP solving with clingo,
Theory Pract. Log. Program. 19 (2019) 27–82. [18] M. Law, A. Russo, K. Broda, Learning weak constraints in answer set programming, Theory
Pract. Log. Program. 15 (2015) 511–525. [19] C. H. Papadimitriou, Computational complexity., Addison-Wesley, 1994. [20] Y. Dimopoulos, A. Torres, Graph theoretical structures in logic programs and default theories, Theor. Comput. Sci. 170 (1996) 209–244. [21] P. E. Dunne, T. J. M. Bench-Capon, Coherence in finite argument systems, Artif. Intell. 141 (2002) 187–203. [22] P. E. Dunne, M. Caminada, Computational complexity of semi-stable semantics in abstract argumentation frameworks, in: Proc. of European Conference on Logics in Artificial Intelligence (JELIA), volume 5293, 2008, pp. 153–165. [23] W. Dvorák, S. Woltran, Complexity of semi-stable and stage semantics in argumentation frameworks, Inf. Process. Lett. 110 (2010) 425–430. [24] R. Booth, S. Kaci, T. Rienstra, L. W. N. van der Torre, A logical theory about dynamics in abstract argumentation, in: Proc. of International Conference Scalable Uncertainty Management (SUM), 2013, pp. 148–161. [25] S. Doutre, J. Mailly, Constraints and changes: A survey of abstract argumentation dynamics,
Argument & Computation 9 (2018) 223–248. [26] R. Baumann, G. Brewka, Expanding argumentation frameworks: Enforcing and monotonicity results, in: Proc. of Computational Models of Argument (COMMA), 2010, pp. 75–86. [27] R. Baumann, What does it take to enforce an argument? minimal change in abstract argumentation, in: Proc. of the European Conference on Artificial Intelligence (ECAI), 2012, pp. 127–132. [28] S. Coste-Marquis, S. Konieczny, J. Mailly, P. Marquis, Extension enforcement in abstract argumentation as an optimization problem, in: Proc. of International Joint Conference on Artificial Intelligence (IJCAI), 2015, pp. 2876–2882. [29] J. P. Wallner, A. Niskanen, M. Järvisalo, Complexity results and algorithms for extension enforcement in abstract argumentation, J. Artif. Intell. Res. 60 (2017) 1–40. [30] A. Niskanen, J. P. Wallner, M. Järvisalo, Extension enforcement under grounded semantics in abstract argumentation, in: International Conference on Principles of Knowledge Representation and Reasoning (KR), 2018, pp. 178–183. [31] L. Amgoud, C. Cayrol, A reasoning model based on the production of acceptable arguments,
Ann. Math. Artif. Intell. 34 (2002) 197–215. [32] S. Kaci, L. W. N. van der Torre, Preference-based argumentation: Arguments supporting multiple values, Int. J. Approx. Reason. 48 (2008) 730–751. [33] S. Modgil, Reasoning about preferences in argumentation frameworks, Artif. Intell. 173 (2009) 901–934. [34] L. Amgoud, S. Vesic, A new approach for preference-based argumentation frameworks,
Ann. Math. Artif. Intell. 63 (2011) 149–183. [35] L. Amgoud, S. Vesic, Rich preference-based argumentation frameworks, Int. J. Approx.
Reason. 55 (2014) 585–606. [36] S. Kaci, L. W. N. van der Torre, S. Villata, Preference in abstract argumentation, in: Proc.
of Computational Models of Argument (COMMA), 2018, pp. 405–412. [37] T. J. M. Bench-Capon, Persuasion in practical argument using value-based argumentation frameworks, J. Log. Comput. 13 (2003) 429–448. [38] P. E. Dunne, T. J. M. Bench-Capon, Complexity in value-based argument systems, in: Proc.
of European Conference on Logics in Artificial Intelligence (JELIA), 2004, pp. 360–371. [39] P. E. Dunne, A. Hunter, P. McBurney, S. Parsons, M. J. Wooldridge, Weighted argument systems: Basic definitions, algorithms, and complexity results, Artif. Intell. 175 (2011) 457–486. [40] S. Coste-Marquis, S. Konieczny, P. Marquis, M. A. Ouali, Weighted attacks in argumentation frameworks, in: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2012. [41] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On the semantics of abstract argumentation frameworks: A logic programming approach, Theory Pract. Log. Program. 20 (2020) 703–718. [42] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic abstract argumentation: Complexity and approximation, in: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2020, pp. 33–43. [43] G. Alfano, S. Greco, F. Parisi, On scaling the enumeration of the preferred extensions of abstract argumentation frameworks, in: Proc. of ACM Symposium on Applied Computing (SAC), 2019, pp. 1147–1153. [44] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation for structured argumentation over dynamic delp knowledge bases, Artif. Intell. 300 (2021) 103553. [45] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Incomplete argumentation frameworks: Properties and complexity, in: Proc. of AAAI Conference on Artificial Intelligence (AAAI), 2022, p. (to appear). [46] S. Greco, F. Parisi, Efficient computation of deterministic extensions for dynamic abstract argumentation frameworks, in: Proc. of European Conference on Artificial Intelligence (ECAI), 2016, pp. 1668–1669. [47] S. Greco, F. Parisi, Incremental computation of deterministic extensions for dynamic argumentation frameworks, in: Proc. of European Conference on Logics in Artificial Intelligence (JELIA), 2016, pp. 288–304. [48] G. Alfano, S. Greco, F. Parisi, Efcfiient computation of extensions for dynamic abstract argumentation frameworks: An incremental approach, in: Proc. of International Joint Conference on Artificial Intelligence (IJCAI), 2017, pp. 49–55. [49] G. Alfano, S. Greco, F. Parisi, An efficient algorithm for skeptical preferred acceptance in dynamic argumentation frameworks, in: Proc. of International Joint Conference on Artificial Intelligence (IJCAI), 2019, pp. 18–24. [50] G. Alfano, S. Greco, Incremental skeptical preferred acceptance in dynamic argumentation frameworks, IEEE Intell. Syst. 36 (2021) 6–12. [51] G. Alfano, S. Greco, F. Parisi, Incremental computation in dynamic argumentation frameworks, IEEE Intelligent Systems (2021). doi:10.1109/MIS.2021.3077292. [52] G. Alfano, S. Greco, F. Parisi, Computing skeptical preferred acceptance in dynamic argumentation frameworks with recursive attack and support relations, in: Proc. of Computational Models of Argument (COMMA), 2020, pp. 67–78. [53] G. Alfano, A. Cohen, S. Gottifredi, S. Greco, F. Parisi, G. R. Simari, Dynamics in abstract argumentation frameworks with recursive attack and support relations, in: Proc. of European Conference on Artificial Intelligence (ECAI), 2020, pp. 577–584. [54] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, An incremental approach to structured argumentation over dynamic knowledge bases, in: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR), 2018, pp. 78–87. [55] G. Alfano, S. Greco, F. Parisi, G. I. Simari, G. R. Simari, Incremental computation of warranted arguments in dynamic defeasible argumentation: the rule addition case, in: Proc. of ACM Symposium on Applied Computing (SAC), 2018, pp. 911–917.