Extensions of Dung's abstract Argumentation Framework (AF) include the general class of Recursive Bipolar AFs (Rec-BAFs), i.e., AFs with recursive attacks and supports. Although the relationships between AF semantics and Partial Stable Models (PSMs) of logic programs has been deeply investigated, this is not the case for Rec-BAFs. In this paper we explore this relationship, showing that a Rec-BAF can be translated into a logic program P so that the extensions of under different argumentation semantics coincide with subsets of the PSMs of P . We provide a logic programming approach that characterizes, in an elegant and uniform way, the semantics of several AF-based frameworks which belong to the class of Rec-BAFs. This result allows also to define the semantics for new AF-based frameworks, such as AFs with recursive attacks and recursive deductive supports.
Formal argumentation has emerged as one of the important fields in Artificial Intelligence [10, 36]. In particular, Dung’s abstract Argumentation Framework (AF) is a simple, yet powerful formalism for modelling disputes between two or more agents [22]. An AF consists of a set of arguments and a binary attack relation over the set of arguments that specifies the interactions between arguments: intuitively, if argument a attacks argument b, then b is acceptable only if a is not. Hence, arguments are abstract entities whose role is entirely determined by the interactions specified by attacks.
Dung’s framework has been extended in many different ways, including the introduction of new kinds of interactions between arguments and/or attacks. In particular, the class of Bipolar Argumentation Frameworks (BAFs) is an interesting extension of the AF which allows for also modelling the support between arguments [32, 37]. Different interpretations of the notion of support have been proposed [15, 18]. Deductive support [37] is intended to capture the following intuition: if argument a supports argument b, then the acceptance of a implies the acceptance of b; thus, the non-acceptance of b implies the non-acceptance of a. On the other hand, necessary support [32, 9] is interpreted in a dual way [15]: if a supports b, then the acceptance of a is necessary to ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). get the acceptance of b; equivalently, accepting b implies accepting a. An AFN (AF with Necessities) is a BAF where supports are interpreted as necessities [32]; an AFD (AF with Deductive supports) is a BAF where supports are interpreted as deductions [37]. Clearly, the way the support is interpreted changes the set of extensions, i.e. the set of acceptable elements of an argumentation framework.
Further extensions of the Dung framework consider second-order interactions [37], e.g., attacks to attacks/supports, as well as more general forms of interactions such as recursive AFs where attacks can be recursively attacked [9, 16] and recursive BAFs, where attacks/supports can be recursively attacked/supported [27, 17].
Following Dung’s approach, the meaning of recursive AF-based frameworks is still given by relying on the concept of extension. However, the extensions of an AF with
(ASAF) [19, 27] also include the (names of) attacks and supports that intuitively contribute to determine the set of accepted arguments. Particularly, the acceptability of an attack is related to the acceptability of its source argument: an attack in the AFRA is defeated even when its source argument is defeated. This is not the case for Recursive
fer a different semantics for recursive AFs and recursive BAFs with necessary supports, respectively. From a syntax standpoint all the argumentation frameworks mentioned above can be viewed as (possibly restricted forms of) Recursive Bipolar Argumentation Frameworks (Rec-BAFs), though semantically different because having different interpretations of support and different ways of determining the status of attacks.
Recently there has been an increasing interest in studying the relationships between argumentation frameworks and logic programming (LP). In particular, the semantic equivalence between complete extensions in AF and 3-valued stable models in LP was first established in [38]. Then, the relationships of LP with AF have been further studied in [13], whereas those with Assumption-Based Argumentation [12, 20] have been considered in [14], and those with Abstract Dialectical Frameworks have been investigated in [1]. Efficient mappings from AF to Answer Set Programming (i.e. LP with Stable Model semantics [26]) have been investigated as well [35, 24]. The well-know AF system ASPARTIX is implemented by rewriting the input AF into an ASP program and using an ASP solver to compute extensions. Although the ASPARTIX system allows also to reason on some extensions of AF, such as Extended AF (EAF) [31] and AFRA, so far the relationships between LP and more general frameworks extending AF such as Rec-BAFs has not been adequately studied. Thus, in this paper, we investigate these relationships by generalizing the work in [13] and providing relationships between LP and different recently proposed generalizations of the Dung’s framework. Contributions. The main contributions of this paper are as follows: – We introduce a general approach for characterizing the extensions of different AFbased frameworks (e.g. AFRA, RAF, ASAF, RAFN) under several well-known argumentation semantics in terms of Partial Stable Models (PSMs) of logic programs. This is achieved by providing a modular definition of the sets of defeated and acceptable elements (i.e., arguments, attacks and supports) for each AF-based framework, and by leveraging on the connection between argumentation semantics and subsets of PSMs. In particular, for any argumentation framework belonging to the class of Rec-BAFs, our formulation of acceptable elements allow us to easily and systematically derive a propositional program whose PSMs corresponds to the extensions (under a given semantics) of the given framework. – Our approach is used to define new semantics for AFs with recursive attacks and supports under deductive interpretation of supports, where the status of an attack is considered independently from the status of its source. We call these frameworks
mentation Framework with Recursive Attacks and Deductive supports (AFRAD). It turns out that AFDs are special cases of these frameworks.
Our results can be used i) for better understanding the semantics of several AFbased frameworks, ii) to easily define new semantics for extended frameworks, and iii) to provide additional tools for computing stable semantics using answer set solvers [25] and even other complete-based semantics using classical program rewriting [30] (see also [35, 24]).
An extended version of this paper can be found in [6]. Proofs are available in [7]. 2
We first recall Dung’s framework and then introduce the general class of recursive bipolar argumentation frameworks. 2.1
Argumentation Frameworks An abstract Argumentation Framework (AF) is a pair hA; i, where A is a set of arguments and A A is a set of attacks. An AF can be seen as a directed graph, whose nodes represent arguments and edges represent attacks; an attack (a; b) 2 from a to b is represented by a ! b.
Different semantics notions have been defined leading to the characterization of collectively acceptable sets of arguments, called extensions [22]. Given an AF =hA; i and a set S A of arguments, an argument a 2 A is said to be i) defeated w.r.t. S iff 9b 2 S such that (b; a) 2 , and ii) acceptable w.r.t. S iff for every argument b 2 A with (b; a) 2 , there is c 2 S such that (c; b) 2 . The sets of defeated and acceptable arguments w.r.t. S are defined as follows (where is understood): – Def (S) = fa 2 A j 9 b 2 S : (b; a) 2 – Acc(S) = fa 2 A j 8 b 2 A : (b; a) 2 g;
) b 2 Def (S)g.
Given an AF hA; i, a set S A of arguments is said to be i) conflict-free iff S \ Def (S) = ;, and ii) admissible iff it is conflict-free and S Acc(S).
Given an AF hA; i, a set S A is an extension called: – complete iff it is conflict-free and S = Acc(S); – preferred iff it is a maximal (w.r.t. ) complete extension; – stable iff it is a total preferred extension, i.e. a preferred extension s.t. S[Def (S) =
A; – semi-stable iff it is a preferred extension such that S [ Def (S) is maximal; – grounded iff it is the smallest (w.r.t. ) complete extension; – ideal iff it is the biggest (w.r.t. ) complete extension contained in every preferred extension.
The set of complete (resp., preferred, stable, semi-stable, grounded, ideal) extensions of a framework will be denoted by CO( ) (resp., PR( ), ST ( ), SST ( ), GR( ), ID( )).
Example 1. Let = hA; i be an AF where A = fa; b; c; dg and = f(a; b); (b; a); (a; c); (b; c); (c; d); (d; c)g. The set of complete extension is CO( ) = f;; f g d ; fa; dg; fb; dgg. Consequently, PR( ) = ST ( ) = SST ( ) = ffa; dg; fb; dgg, GR( ) = f;g, ID( ) = ffdgg. 2.2
Recursive Bipolar Argumentation Frameworks A Recursive Bipolar Argumentation Framework (Rec-BAF) is a tuple hA; ; ; s; ti, where A is a set of arguments, is a set of attack names, is a set of necessary support names, s (resp., t) is a function from [ to A (resp., to A [ [ ) mapping each attack/support to its source (resp., target). In the following, given a set such that either or , we denote by i) = f(s( ); t( )) j 2 g the set of pairs connected by an attack/support edge, and ii) + the transitive closure of . It is assumed that is acyclic.
Two different semantics have been defined under necessary interpretation of supports, as recalled in what follows.
cessities (RAFN) has been proposed in [17]. The semantics combines the RAF interpretation of attacks [16] with that of BAF under the necessity interpretation of supports (i.e., AFN) [32]. Here we consider a simplified version where supports have a single source and the support relation is acyclic. Formally, given an RAFN hA; ; ; s; ti, X 2 (A [ [ ), a 2 A, and S A [ [ , we say that argument a recursively attacks X given S (denoted as a attS X) if either (a; X) 2 ( \ S) or there exists b 2 A such that (a; b) 2 ( \ S) and (b; X) 2 ( \ S)+.
For any RAFN and S A [ [ , the defeated and acceptable sets (given S) are defined as follows: – Def (S) = fX 2 A [ – Acc(S) = fX 2 A [ [ [ j 9b 2 A \ S : b attS Xg; j 8b 2 A : b attS X ) b 2 Def (S)g.
Attack-Support AF. The Attack-Support Argumentation Framework (ASAF) has been proposed in [19, 27]. The semantics combines the AFRA interpretation of attacks [9] with that of BAF under the necessary interpretation of supports (i.e., AFN). For the sake of presentation, we consider a slight generalization of ASAF, where attack and support names are first-class citizens, giving the possibility to represent multiple attacks and supports from the same source to the same target.1 1 In the original work [19, 27] an ASAF is a tuple hA; ; i where A is a set of arguments, is a set of attacks : A ! (A [ ), and is a set of supports : A ! (A [ ).
Formally, given an ASAF hA; ; ; s; ti, X 2 (A [ [ ), 2 , and S A [ [ , we say that i) (directly or indirectly) attacks X (denoted by def X) if either t( ) = X or t( ) = s(X), and ii) extendedly defeats X given S (denoted as defS X) if either def X or there exists b 2 A such that t( ) = b and either (b; X) 2 ( \ S)+ or (b; s(X)) 2 ( \ S)+. For any ASAF and S A [ [ , the defeated and acceptable sets (given S) are: – Def (S) = fX 2 A [ – Acc(S) = fX 2 A [
The notions of conflict-free, admissible sets, and the different types of extensions can be defined in a standard way (see Section 2.1) by considering S A [ [ and by using the definitions of defeated and acceptable sets reported above.
AFs with high-order interactions can be mapped to AFs, though the mapping is not trivial because extensions also contain attacks and supports. In particular, an equivalent AF for an ASAF can be obtained by translating it into an AFN [19] that in turns can be translated into an AF [32] (see also [27]).
Example 2. Consider a situation where we want to decide whether to play tennis on the
basis of some information. Assume we have the following arguments: r (it is raining),
p (play tennis), o (the tennis court is outside), and the logical implications: (
It is important to observe that different frameworks extending AF share the same structure, although they have different semantics. Thus we distinguish between framework and class of frameworks. Two frameworks sharing the same syntax (i.e. the structure) belong to the same (syntactic) class. For instance, BAF is a syntactic class, whereas AFN and AFD are two specific frameworks sharing the same BAF syntax; their semantics differ because they interpret supports in different ways. Recursive AF (Rec-AF) is another syntactic class, where AFs are extended by allowing recursive attacks: AFRA and RAF are frameworks belonging to this class, which differ only in the determination of the status of attacks. Finally, ASAF and RAFN are two frameworks belonging 2 For the sake of presentation, we consider a slight generalization of AFRA, where attack names are first-class citizens, allowing to also represent more than one attack from the same source to the same target. In the original work an AFRA is a tuple hA; i where A is a set of arguments and is a set of attacks : A ! (A [ ) [9].
Acronym Framework AF abstract Argumentation Framework [Dung,1995] BAF Bipolar AF AFN AF with Necessities [Nouia and Risch,2011] AFD AF with Deductive supports [Villata et al.,2012] Rec-AF Recursive-AF AFRA AF with Recursive Attacks [Baroni et al.,2011] RAF Recursive AF [Cayrol et al.,2017] Rec-BAF Recursive-BAF ASAF Attack-Support AF [Gottifredi et al.,2018] RAFN Recursive AF with Necessities [Cayrol et al.,2018] AFRAD AF with Rec. Attacks and Deductive supports
RAFD Recursive AF with Deductive supports to the general class Rec-BAF presented in this section, consisting in the extension of BAF with recursive attacks and supports. The differences between ASAF and RAFN semantics are not in the way they interpret supports (both based on the necessity interpretation), but in a different determination of the status of attacks as they extend AFRA and RAF, respectively. In Section 3.2 we will present two new frameworks that also belong to the Rec-BAF class: Recursive Argumentation Framework with Deductive supports (RAFD) and Argumentation Framework with Recursive Attacks and Deductive supports (AFRAD). AFDs are special cases of these frameworks.
Thus, the class of Rec-BAF includes the sub-classes BAF and Rec-AF, and thus the 9 frameworks discussed above, ASAF, RAFN, AFRAD, and RAFD, and their specializations AF, AFRA, RAF, AFN, and AFD. We use F to denote the set of these 9 frameworks. Table 1 lists the frameworks in F. With a little abuse of notation, we will use the same symbol to denote any framework in F. In this section, we review the basic concepts which underly the notion of PSMs [34].
A (normal, logic) program is a set of rules of the form A B1 ^ ^ Bn, with n 0, where A is an atom, called head, and B1 ^ ^ Bn is a conjunction of literals, called body. We consider programs without function symbols. Given a program P , ground(P ) denotes the set of all ground instances of the rules in P . The Herbrand Base of a program P , i.e. the set of all ground atoms which can be constructed using predicate and constant symbols occurring in P , is denoted by BP , whereas :BP denotes the set f:A j A 2 BP g. Analogously, for any set S BP [ :BP , :S denotes the set f:A j A 2 Sg, where ::A = A. Given I BP [ :BP , pos(I) (resp., neg(I)) stands for I \ BP (resp., :I \ BP ). I is consistent if pos(I) \ :neg(I) = ;, otherwise
Given a program P , I BP [:BP is an interpretation of P if I is consistent. Also, I is total if pos(I) [ neg(I) = BP , partial otherwise. A partial interpretation M of a program P is a partial model of P if for each :A 2 M every rule in ground(P ) having as head A contains at least one body literal B such that :B 2 M . Given a program P and a partial model M , the positive instantiation of P w.r.t. M , denoted by P M , is obtained from ground(P ) by deleting: (a) each rule containing a negative literal :A such that A 2 pos(M ); (b) each rule containing a literal B such that neither B nor :B is in M ; (c) all the negative literals in the remaining rules. Clearly, all the rules in P are definite clauses and hence the minimal Herbrand model of P can be obtained as the least fixpoint of its immediate consequence operator TP M , denoted by TP!M (;). For any partial model M of a logic program P , TP!M (;) M [34].
Let P be a program and M a partial model for P . Then M is (a) founded if TP!M (;) = pos(M ); (b) stable if it is founded and it is not a proper subset of any other founded model. The set of partial stable models of a logic program P , denoted by PM(P ), define a meet semi-lattice. The well-founded model (denoted by WF (P )) and the maximal-stable models MS(P )3, are defined by considering -minimal and -maximal elements. The set of (total) stable models (denoted by SM(P )) is obtained by considering the maximal-stable models which are total, whereas the least-undefined models (denoted by LM(P )) are obtained by considering the maximal-stable models with a -minimal set of undefined atoms (i.e., atoms which are neither true or false). The max-deterministic model (denoted by MD(P )) is the -maximal PSM contained in every maximal-stable model [33, 29].
Example 3. Consider the program P consisting of the following four rules fa :b; b :a; c :a ^ :b ^ :d; d :cg. The set of partial stable models of P is PS(P ) = f ;; f:c; dg; fa; :b; :c; dg; f:a; b; :c; dg g. Consequently, WF ( ) = f ; g, MD( ) = f f:c; dg g, MS = ST ( ) = LS( ) = ffa; :b; :c; dg; f:a; b; :c; dgg.
Propositional Programs. Given a set of symbols = fa1; :::; ang, a (propositional) program over is a set of j j rules ai bodyi (1 i n), where every bodyi is a propositional formula defined over . The semantics of a propositional program P , defined over a given alphabet , is given in terms of the set PS(P ) of its Partial Stable Models (PSMs) that are obtained as follows: i) P is first rewritten into a set of standard (ground) logic rules P 0, whose bodies contain conjunction of literals (even by adding fresh symbols to the alphabet)4; ii) next, the set of PSMs of P 0 is computed; iii) finally, fresh literals added to in the first step are deleted from the models. It is worth noting that for propositional programs we can assume as Herbrand Base the set of (ground) atoms occurring in the program. 3
In this section we present a new way to define the semantics of AF-based frameworks by considering propositional programs and partial stable models. In order to compare extensions E of a given framework (containing acceptable elements) with PSMs of 3 Corresponding to the preferred extensions of [21]. 4 A rule a (b_c)^(d_e) is rewritten as a :d^:e. a given program P (containing true and false atoms), we denote as Eb = E [ f:a j a 2 Def (E)g the completion of E. Moreover, for a collection of extensions E, Eb denotes the set fEb j E 2 Eg.
Observe also that for any framework and complete extension E for , elements not occurring in E [ Def (E) are said to be undecided (or undefined), whereas for any program P and PSM M for P , atoms not occurring in pos(M ) [ neg(M ) are said to be undefined. Thus, to compare complete extensions and PSMs it is sufficient to consider the completion of extensions.
The next proposition states the relationship between the argumentation frameworks (e.g. AF, BAF, Rec-BAF) and logic programs with partial stable models.
C\O( ) = PS(P ) it holds that P\R( ) = MS(P ), S\T( ) = ST (P ), SS\T( ) = LM(P ), G\R( ) = WF (P ), and I\D( ) = MD(P ).5
The result of Proposition 1 derives from the fact that preferred, stable, semi-stable, grounded, and ideal extensions are defined by selecting a subset of the complete extensions satisfying given criteria (see Section 2). On the other side, the maximal, stable, least-undefined, well-founded, and max-deterministic (partial) stable models are obtained by selecting a subset of the PSMs satisfying criteria coinciding with those used to restrict the set of complete extensions.
Given a framework and an extension E, for any element a which could occur in some extension of , the truth value vE (a), or simply v(a) whenever E is understood, is equal to true if a 2 E, false if a 2 Def (E), undec (undecided) otherwise. Hereafter, we assume that false < undec < true and :undec = undec.
The strict relationship between the semantics of AFs (given in terms of subset of complete extensions) and the semantics of logic programs (given in terms of subset of PSMs) has been shown in [38, 13]. The relationship is based on the observation that the meaning of an attack a ! b is that the condition v(b) :v(a) must hold. On the other side, the satisfaction of a logical rule a b1; :::; bn implies that v(a) minfv(b1); :::; v(bn); trueg.
Definition 1. Given an AF = hA; i, we denote as P
= fa
V (b;a)2 :b j a 2
The semantics of an AF can be obtained by considering PSMs of the logic program P . Particularly, for any AF , C\O( ) = PS(P ).
In the rest of this section, we show how the semantics defined for frameworks extending AF can be captured by means of PSMs of logic programs. We propose a general method that can be applied to all the discussed frameworks, and even to new frameworks in Section 3.2. Specifically, to model frameworks extending Dung’s framework by logic programs under PSM semantics, we provide new definitions of defeated and acceptable sets that, for a given set S, will be denoted by DEF(S) and ACC(S), respectively. These definitions will be used to derive rules in P , the propositional program for 2 F. For AFs we have that for every set S A, DEF(S) = Def (S) and ACC(S) = Acc(S). 5 For the novel frameworks 2 fAFRAD, RAFDg, the set CO( ) of the complete extensions, and the sets of extensions prescribed by the other semantics, are defined in Section 3.2. In this section we study the relationship between partial stable models and the semantics of Rec-BAFs. Particularly, we first present results for RAFN semantics, and then we discuss results for the ASAF framework. We remand to the next section the presentation of two novel semantics for recursive bipolar AFs with deductive interpretation of supports.
RAFN. We next provide the definitions of defeated and acceptable sets for an RAFN.
and an extension S 2 CO( ), then Def (S) = DEF(S)
Theorem 1 states that in order to define the semantics for an RAFN we can use acceptable sets S = ACC(S). This is captured by the following definition, that shows how to derive a propositional program from an RAFN from Definition 2. Definition 3. Given an RAFN = hA; ; ; s; ti, then P (the propositional program derived from ) contains, for each X 2 A [ [ , a rule
X
^ 2 ^t( )=X (:
The previous theorem states that the set of complete extensions of an RAFN coincides with the set of PSMs of the derived logic program P . Consequently, using Proposition 1, also the others argumentation semantics turns out to be characterized in terms of subsets of PSMs. Moreover, previous results also apply to restricted frameworks such as RAF, where = ;, and AFN, where t : [ ! A.
ASAF. We next provide definitions of defeated and acceptable sets for an ASAF. They will be used in a way similar to that described above in order to obtain a semanticallyequivalent propositional program for ASAFs.
Analogously to what has been done RAFNs, since it can be shown that for any complete extension S of an ASAF it is the case that Acc(S) = ACC(S), the propositional program for an ASAF can be derived by looking at the definition ACC(S) of acceptable elements. In this case, the three conjuncts in the acceptance condition for an element X will correspond to three (group of) conjuncts, respectively, in the rule for X of the program P . Specifically, the last two conjuncts in the definition of ACC(S) can be mapped by reasoning similarly to the RAFN case, whereas the first one entails a rule’s body conjunction stating that if X is an attack then all of its sources must be true.
Definition 5. For any ASAF = hA; ; ; s; ti, P (the propositional program derived from ) contains, for each X 2 A [ [ , a rule of the form
X
Example 4. Consider a Rec-BAF 0 obtained by adding to the Rec-BAF of Example 2 argument s (it is sunny). Argument r and s attack each other through attacks 2 and 3, as shown in Figure 2. As shown below, 0 has different extensions when viewed as an RAFN or an ASAF.
s 3 2 r 1 1 p s 3 2 r o 1 1 p 2 z Fig. 3: Rec-BAF of Example 6
Under RAFN semantics 0 has the following two complete extensions: fo; s; p;
1; 2; 3; 1g and fo; r 1; 2; 3; 1g. Differently, under ASAF semantics 0 has
the following complete extensions: fo; s; p; 3; 1g and fo; r 1; 2; 1g. Note that
attacks 1 and 2 (resp., 3) do not belong to fo; s; p; 3; 1g since their source, r,
is defeated. Similarly, 3 does not belong to fo; r 1; 2; 1g since its source, s, is
defeated. The propositional program under the RAFN semantics is the following:
P 0 = f(o ); (r : 3 _ :s); (p : 1 _ :r); (s : 2 _ :r); ( 1 : 1 _ o);
(
Analogously, the propositional program for 0 under the ASAF semantics is:
P 0 = f(o ); (r : 3); (p : 1); (s : 2); ( 1 r ^ (: 1 _ o));
( 2 r); ( 3 s); (
Recursive BAFs with Deductive Supports In this section we study two new frameworks both belonging to the Rec-BAF class and both extending AFD by allowing recursive attacks and deductive supports. The first one, called Recursive Argumentation Framework with Deductive supports (RAFD), extends RAF, whereas the second one, called Argumentation Framework with Recursive
is acyclic.
As we shall define the semantics by defining directly the sets DEF(S) and ACC(S), differently from the previous section, we do not have any results regarding the equivalence between the sets Acc(S) and ACC(S) for S = ACC(S).
RAFD. As usual, we first define the sets of defeated and acceptable elements, and then the propositional logic program for an RAFD.
The sets of extensions prescribed by the different semantics are based on the defeated and acceptable sets defined above. That is, given an RAFD = hA; ; ; s; ti, a set S A [ [ of elements is a complete extension of iff it is conflict-free (i.e., S \ DEF(S) = ;) and S = ACC(S). As done for the other frameworks, we use CO( ) to denote the set of complete extensions of . Moreover, the set of preferred (resp., stable, semi-stable, grounded, ideal) extensions is defined in the standard way (see Section 2.1) by using again DEF(S) and ACC(S).
Using ACC(S), we define the propositional program for an RAFD .
Definition 7. Given an RAFD = hA; ; ; s; ti, then P (the propositional program derived from ) contains, for each X 2 A [ [ , a rule of the form X
^
Thus, the semantics of an RAFD can be carried out by using the PSMs of P . The result also applies to restricted frameworks such as RAF, where = ;, and AFD, where t : ! A.
[ AFRAD. The following definition formalizes defeated and acceptable sets for an AFRAD.
Similarly to what done for RAFDs, the set CO( ) of complete extensions of an AFRAD , and the sets of extensions prescribed by the other semantics, are defined by using the defeated and acceptable sets defined above.
Definition 9. For any AFRAD = hA; ; ; s; ti, P (the propositional program derived from ) contains, for each X 2 A [ [ , a rule of the form X
The result also apply to restricted frameworks such as AFRA and AFD.
Example 5. Consider now the Rec-BAF 0 of Example 4 and assume that supports
are interpreted as deductive. The propositional program under RAFD semantics is as
follows: P 0 = f(o : 1 _ 1); (r : 3 _:s); (p : 1 _:r); (s : 2 _:r);
(
On the other hand, the propositional program for 0 under AFRAD semantics is:
P 0 = f(o : 1 _ 1); (r : 3); (p : 1); (s : 2); ( 1 r); ( 2
r); ( 3 s); (
Note that the RAFD (resp., AFRAD) program differs from the RAFN (resp., ASAF) program given in Example 4 only in rules having as head 1 and o, respectively.
Considering Example 4 and Example 5, we note that the set of PSMs of the propositional programs for the RAFN and RAFD (resp., ASAF and AFRAD) frameworks coincide, meaning that these argumentation frameworks have the same sets of extensions. However, in general, RAFNs and RAFDs (resp., ASAFs and AFRADs) prescribe different sets of extensions as shown in the following example.
Example 6. Consider a Rec-BAF 00 obtained by adding to the Rec-BAF 0 of Example 5 a new argument z and a new support 2 from argument p to z (see Figure 3).
We first revise the propositional programs given in Example 4 to take into account argument z and support 2. The propositional program P 00 under RAFN (resp., ASAF) semantics is obtained by adding to the propositional program P 0 under RAFN (resp., ASAF) semantics of Example 4 the rules z : 2 _ p and 2 (cf. Definitions 3 and 5). Then, the set of partial stable models of P 00 under RAFN semantics is: PS(P 00 ) = fN1 = M1 [ fz; 2g; N2 = M2 [ f:z; 2gg, where M1 and M2 are the models given in Example 4 that, as said above, coincide with those of Example 5. The set of partial stable models of P 00 under ASAF semantics is as follows: PS(P 00 ) = fN3 = M3 [ fz; 2g; N4 = M4 [ f:z; 2gg, where M3 and M4 are the models given in Example 4 which, again, coincide with those of Example 5.
Now consider how we have to revise the propositional programs of Example 5 to take into account the new elements z and 2. In this case, the propositional program P 00 under RAFD (resp., AFRAD) semantics is obtained by adding to the propositional program P 0 under RAFD (resp., AFRAD) semantics of Example 5 the rules z and 2 and by replacing the rule having as head p with the rule p (: 1 _:r)^(: 2 _ z) (resp., p : 1 ^ (: 2 _ z)). Thus, set of partial stable models of P 00 under RAFD semantics is PS(P 00 ) = fN1 = M1 [ fz; 2g; N20 = M2 [ fz; 2gg, while under AFRAD semantics we obtain PS(P 00 ) = fN3 = M3 [ fz; 2g; N40 = M4 [ fz; 2gg.
Hence, here we have that PSM N2 (resp., N4) derived from RAFN (resp., ASAF) 00 differs from PSM N20 (resp., N40 ) derived from RAFD (resp., AFRAD) 00. Consequently, the sets of the extensions of the four frameworks differ as well. 4
By exploring the connection between formal argumentation and logic programming, we have proposed a simple but general logical framework which is able to capture, in a systematic and succinct way, the different features of several AF-based frameworks under different argumentation semantics and interpretation of the support relation. The proposed approach can be used for better understanding the semantics of extended AF frameworks (sometimes a bit involved), and is flexible enough for encouraging the study of other extensions. Our approach can be used to provide additional tools for computing complete extensions using answer set solvers [25] and classical program rewriting [30, 35, 24]. For instance, ASP-based tools like DLV and Potassco can be used to compute stable models, and XSB can be used to compute well founded semantics.
Other extensions of the Dung’s framework not explicitly discussed in this paper are also captured by our technique as they are special cases of some of those studied in this paper. This is the case of Extended AF (EAF) and hierarchical EAF, which extend AF by allowing second order and stratified attacks, respectively [31].
Future work will be devoted to further generalize our logical approach in order to
deal also with AF-based framework considering probabilities [23], weights [11], and
preferences [8, 31], and frameworks considering supports with multiple sources [17].
Finally, we plan to investigate incremental techniques tailored at using our approach
to compute extensions of dynamic AF-based frameworks, where the sets of arguments
and interactions change over the time [28, 3, 4, 2, 5].
15. Cayrol, C., Lagasquie-Schiex, M.: Bipolarity in argumentation graphs: Towards a better
understanding. IJAR 54(
ICLP. pp. 3–17 (1991)
22. Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming and n-person games. AI 77, 321–358 (1995)
23. Fazzinga, B., Flesca, S., Parisi, F.: On the complexity of probabilistic abstract argumentation
frameworks. TOCL 16(
pp. 1070–1080 (1988)
27. Gottifredi, S., Cohen, A., Garcia, A.J., Simari, G.R.: Characterizing acceptability semantics
of argumentation frameworks with recursive attack and support relations. AI 262, 336–368
(2018)
28. Greco, S., Parisi, F.: Incremental computation of deterministic extensions for dynamic
argumentation frameworks. In: JELIA. pp. 288–304 (2016)
29. Greco, S., Sacca`, D.: Complexity and expressive power of deterministic semantics for
datalog:. Inf. Comput. 153(
In: PODS. pp. 205–217 (1990)
35. Sakama, C., Rienstra, T.: Representing argumentation frameworks in answer set
programming. Fundam. Inform. 155(