Defining the Semantics of Abstract Argumentation Frameworks through Logic Programs and Partial Stable Models (Extended Abstract)

1 Introduction

Dung's abstract Argumentation Framework (AF) [Dung, 1995] is a simple yet powerful formalism for modelling disputes between two or more agents which 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 AF which allows for modelling the support between arguments [Nouioua and Risch, 2011; Villata et al., 2012]. Different interpretations of the notion of support have been proposed [Cayrol and LagasquieSchiex, 2013; Cohen et al., 2014]. Deductive support [Villata et al., 2012] 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 nonacceptance of b implies the non-acceptance of a. On the other hand, necessary support [Nouioua and Risch, 2011; Baroni et al., 2011] is interpreted in a dual way [Cayrol and Lagasquie-Schiex, 2013]: if a supports b, then the acceptance of a is necessary to 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 [Nouioua and Risch, 2011]; an AFD (AF with Deductive supports) is a BAF where supports are interpreted as deductions [Villata et al., 2012]. 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 AF consider recursive AFs and recursive BAFs where attacks/supports can be recursively attacked/supported [Baroni et al., 2011; Cayrol et al., 2017; Gottifredi et al., 2018; Cayrol et al., 2018].

∗This paper is based on the work "On the semantics of abstract argumentation frameworks: A logic programming approach", that was presented at the 36th International Conference on Logic Programming [Alfano et al., 2020c], awarded as best technical paper.

Following Dung's approach, the meaning of recursive AFbased frameworks is still given by relying on the concept of extension. However, the extensions of an AF with Recursive Attacks (AFRA) [Baroni et al., 2011] and of an AttackSupport Argumentation Framework (ASAF) [Cohen et al., 2015; Gottifredi et al., 2018] 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 AFRA is defeated even when its source argument is defeated. This is not the case for Recursive AF (RAF) [Cayrol et al., 2017] and Recursive AF with Necessities (RAFN) frameworks [Cayrol et al., 2018], which offer 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 the supports and different ways of determining the status of attacks.

Example 1 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), s (it is sunny), and the implications: (α1) if it is raining, then we do not play tennis, and (β1) if the tennis court is outside, then α1 should hold. Notice that arguments r and s are mutually conflicting. The scenario can be modelled using the Rec-BAF ∆ of Figure 1 where α1, as well as α2 and α3 modelling the mutual conflicts between r and s, are attacks (denoted by →) and β1 is a support (denoted by ⇒).

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 [Wu et al., 2009]

and further studied in [Caminada et al., 2015]. Efficient mappings from AF to Answer Set Programming (i.e. LP with Stable Model semantics [Gelfond and Lifschitz, 1988]) have been investigated as well [Sakama and Rienstra, 2017; Gaggl et al., 2015]. However, the relationships between LP and more general frameworks extending AF such as RecBAFs has not been adequately studied. Thus, in this paper, by generalizing the work in [Caminada et al., 2015], we introduce a general approach for characterizing the extensions of different AF-based 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 framework belonging to the class of Rec-BAFs, our formulation of acceptable elements allows us to easily and systematically derive a propositional program whose PSMs corresponds to the extensions (under a given semantics) of the given framework.

2 Preliminaries

We first recall Dung's framework and then introduce the general class of recursive bipolar argumentation frameworks. We also briefly recall logic programs and partial stable semantics.

2.1 Argumentation Framework

An abstract Argumentation Framework (AF) is a pair 〈A, Ω〉, 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.

Different semantics notions have been defined leading to the characterization of collectively acceptable sets of arguments, called extensions [Dung, 1995]. Given an AF ∆ =〈A,Ω〉 and a set S ⊆ A of arguments, an argument a ∈ A is said to be i) defeated w.r.t. S iff ∃b ∈ S such that (b, a) ∈ Ω, and ii) acceptable w.r.t. S iff for every argument b ∈ A with (b, a) ∈ Ω, there is c ∈ S such that (c, b) ∈ Ω. The sets of defeated and acceptable arguments w.r.t. S are defined as follows (where ∆ is understood):

• ·Def(S) = {a ∈ A | ∃ b ∈ S . (b, a) ∈ Ω};
• ·Acc(S) = {a ∈ A | ∀ b ∈ A . (b, a) ∈ Ω ⇒ b ∈ Def(S)}.

Given an AF 〈A,Ω〉, 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 〈A,Ω〉, a set S ⊆ A is an extension called: complete iff it is conflict-free and S = Acc(S); preferred iff it is a ⊆-maximal complete extension; stable iff it is a total preferred extension, i.e. a preferred extension such that 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 complete extension; ideal iff it is the ⊆-biggest complete extension contained in every preferred extension.

We use CO(∆) (resp., PR(∆), ST (∆), SST (∆), GR(∆), ID(∆)) to denote the set of complete (resp., preferred, stable, semi-stable, grounded, ideal) extensions of a framework ∆.

2.2 Recursive Bipolar AFs

A Recursive Bipolar Argumentation Framework (Rec-BAF) is a tuple 〈A, Σ, Π, s, t〉, where A is a set of arguments, Σ is a set of attack names, Π is a set of 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) Φ∗ = {(s(γ), t(γ)) | γ ∈ Φ} 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 the necessary interpretation of supports, as recalled in what follows.

Recursive AF with Necessities. The Recursive Argumentation Framework with Necessities (RAFN) has been proposed in [Cayrol et al., 2018]. The semantics combines the RAF interpretation of attacks [Cayrol et al., 2017] with that of BAF under the necessity interpretation of supports (i.e. AFN) [Nouioua and Risch, 2011]. Here we consider a simplified version where supports have a single source and the support relation is acyclic. Formally, given an RAFN 〈A, Σ, Π, s, t〉, X ∈ (A∪Σ∪Π), a ∈ A, and S ⊆ A∪Σ∪Π, we say that argument a recursively attacks X given S (denoted as a attS X) if either (a, X) ∈ (Σ∩S)∗ or there exists b ∈ A such that (a, b) ∈ (Σ ∩ S)∗ and (b, X) ∈ (Π ∩ S)+.

For any RAFN ∆ and S ⊆ A ∪ Σ ∪ Π, the defeated and acceptable sets (given S) are defined as follows:

• ·Def (S) = {X ∈ A ∪ Σ ∪ Π | ∃b ∈ A ∩ S . b attS X};
• Acc(S) ={X∈A∪Σ∪Π | ∀b ∈A. b attS X ⇒b ∈Def (S)}.

Attack-Support AF. The Attack-Support Argumentation Framework (ASAF) has been proposed in [Cohen et al., 2015; Gottifredi et al., 2018]. The semantics combines the AFRA interpretation of attacks [Baroni et al., 2011] 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.

Formally, given an ASAF 〈A, Σ, Π, s, t〉, X ∈ (A∪Σ∪Π), α ∈ Σ, 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 ∈ A such that t(α) = b and either (b,X) ∈ (Π ∩ S)+ or (b, s(X)) ∈ (Π∩S)+. For any ASAF ∆ and S ⊆ A∪Σ∪Π, the defeated and acceptable sets (given S) are as follows:

• ·Def (S) = {X ∈ A ∪ Σ ∪ Π | ∃ α ∈ Σ ∩ S . α defS X};
• Acc(S)={X ∈A∪Σ∪Π|∀α∈Σ. α defS X⇒α∈Def (S)}.

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.

Example 2 For the framework ∆ of Example 1, under RAFN semantics CO(∆) = {E1 = {o, s, p, α1, α2, α3, β1}, E2 = {o, r, α1, α2, α3, β1}}. Differently, under ASAF semantics CO(∆) = {E3 = {o, s, p, α3, β1}, E4 = {o, r, α1, α2, β1}}. Note that α1 and α2 (resp., α3) do not belong to E3 (resp. E4) since their source, r (resp., s), is defeated.

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 [Cohen et al., 2015] that in turns can be translated into an AF [Nouioua and Risch, 2011; Gottifredi et al., 2018].

AF-based frameworks belonging to the class of Rec-BAFs.

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 frameworks sharing the 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 attacks' status. Finally, ASAF and RAFN are two frameworks belonging to the general class Rec-BAF presented in this section, consisting in the extension of BAF with recursive attacks and supports.

Hereafter, we focus on necessary supports only, even if the approach discussed in next section has been extended to cope with deductive supports in two frameworks: Recursive Argumentation Framework with Deductive supports (RAFD), which extends RAF, and Argumentation Framework with Recursive Attacks and Deductive supports (AFRAD), which extends AFRA. AFDs are special cases of these frameworks. We refer the reader to [Alfano et al., 2020c] for details.

Thus, the class of Rec-BAF includes 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.

2.3 Propositional Logic Programs

Given a set of symbols Λ = {a1, ..., an}, a (propositional) program over Λ is a set of |Λ| 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) [Sacc`a and Zaniolo, 1990].

The set of PSMs 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)1 , 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 maxdeterministic model (denoted byMD(P)) is the ⊆-maximal PSM contained in every maximal-stable model [Sacc`a, 1997; Greco and Sacc`a, 1999].

1 Corresponding to the preferred extensions of [Dung, 1991].

3 AF-based Frameworks and PSMs

We present a new way to define the semantics of AFbased frameworks by considering propositional programs and PSMs. To compare extensions E of a given framework ∆ (containing acceptable elements) with PSMs of a given program P (containing true and false atoms), we denote by ̂ E = E ∪ {¬a | a ∈ Def(E)} the completion of E. For a collection of extensions E, ̂E denotes the set { ̂ E | E ∈ E}.

A first relationship between AF-based frameworks (e.g. BAF, Rec-BAF) and logic programs with PSMs is as follows.

Proposition 1 For any framework ∆ ∈ F and propositional program P, whenever ̂ CO(∆) = PS(P) it holds that ̂ PR(∆) = MS(P), ̂ ST (∆) = ST (P), ̂ SST (∆) = LM(P ), ̂ GR(∆) = WF(P ), and ̂ ID(∆) = MD(P ).

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 maxdeterministic (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 ∈ E, false if a ∈ Def(E), undec (undecided) otherwise. Hereafter, we assume that false < undec < true and ¬undec = undec.

The 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 [Wu et al., 2009; Caminada et al., 2015]. 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) ≥ min{v(b1), ..., v(bn), true}.

The semantics of an AF ∆ can be obtained by considering PSMs of the logic program P∆. In fact, ̂ CO(∆) = 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. 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 ∆ ∈ F. For AFs we have that, for every set S ⊆ A, DEF(S) = Def (S) and ACC(S) = Acc(S).

3.1 Recursive BAFs with Necessary Supports

We now study the relationship between PSMs and the semantics of Rec-BAFs. We first present results for RAFN semantics, and then we discuss results for the ASAF framework.

RAFN. We next provide the definitions of defeated and acceptable sets for an RAFN.

Definition 2 For any RAFN 〈A, Σ, Π, s, t〉 and set S ⊆ A ∪ Σ∪Π, we have that:

• DEF(S) = {X ∈ A ∪ Σ ∪ Π | (∃ α ∈ Σ ∩ S . s(α) ∈ S ∧ t(α) = X) ∨
• (∃ β ∈ Π∩ S . s (β) ∈ DEF(S) ∧ t(β) =X) }; · ACC(S)={X ∈ A ∪ Σ ∪ Π | (∀ α∈Σ . t(α)=X⇒(α∈DEF(S) ∨ s(α)∈DEF(S))) ∧ (∀ β ∈Π . t(β)=X⇒(β ∈ DEF(S) ∨ s(β)∈ACC(S)))}.

Notice that DEF(S) and ACC(S) are defined recursively. If S is a complete extension we obtain the following result.

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 ∆ = 〈A, Σ, Π, s, t〉, then P∆ (the propositional program derived from ∆) contains, for each X ∈ A ∪ Σ ∪ Π, a rule

Intuitively, starting from the definition of ACC(S) in Definition 2, the rationale of the above definition is as follows. An element X ∈ A ∪ Σ ∪ Π is true if (i) every attack α toward X is false or originates from a source s(α) which is false, and (ii) every support β toward X is false or originates from a source s(β) which is true. These conditions resemble the conditions (∀α ∈ Σ . t(α) = X ⇒ (α ∈ DEF(S) ∨ s(α) ∈ DEF(S))) and (∀β ∈Π . t(β) = X⇒(β ∈ DEF(S) ∨ s(β) ∈ ACC(S))), respectively, of Definition 2 after interpreting elements in DEF(S) as false and elements in ACC(S) as true.

As stated below, the set of complete extensions of an RAFN ∆ coincides with the set of PSMs of P∆.

Thus, using Proposition 1, also the others argumentation semantics turns out to be characterized in terms of subsets of PSMs. Notice that, 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 to obtain a semantically-equivalent propositional program for ASAFs.

Definition 4 Given an ASAF 〈A,Σ,Π, s, t〉 and a set S ⊆ A ∪ Σ ∪ Π, we define:

• DEF(S) = {X ∈ A∪Σ∪Π |(X ∈ Σ ∧ s(X) ∈ DEF(S)) ∨ (∃α ∈ Σ ∩ S . t(α) = X) ∨ (∃β ∈ Π ∩ S . t(β) = X ∧ s(β) ∈ DEF(S))};
• ACC(S)={X ∈A ∪ Σ ∪ Π |(X ∈ Σ⇒ s(X) ∈ACC(S)) ∧ (∀ α ∈ Σ. t(α)=X ⇒α ∈ DEF(S)) ∧ (∀ β ∈ Π . t(β)=X⇒ (β ∈DEF(S) ∨ s(β)∈ACC(S)))}.

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 program P∆ for ∆ 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 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 ∆ = 〈A,Σ,Π, s, t〉, P∆ (the propositional program derived from ∆) contains, for each X ∈ A∪Σ∪Π, a rule of the form

The set of complete extensions of an ASAF ∆ coincides with the set of PSMs of P∆, meaning that using Proposition 1 also the others argumentation semantics turns out to be characterized in terms of subsets of PSMs.

The above results also apply to restricted frameworks such as AFRA, where Π = ∅, and AFN, where t : Σ ∪ Π → A.

Example 3 Consider ∆ of Example 1, whose complete extensions under RAFN and ASAF semantics are given in Example 2. The program under the RAFN semantics is P∆ = {(o ←), (r ← ¬α3∨¬s), (p ← ¬α1∨¬r), (s ← ¬α2∨¬r), (α1 ← ¬β1 ∨ o), (α2 ←), (α3 ←), (β1 ←)}, whose set of PSM is PS(P∆′) = {M1={o, ¬r, s, p, α1, α2, α3, β1}, M2={o, r, ¬s, ¬p, α1, α2, α3, β1}}. For ASAF semantics, P∆ = {(o ←), (r ← ¬α3), (p ← ¬α1), (s ← ¬α2), (α1 ← r ∧ (¬β1 ∨ o)), (α2 ← r), (α3 ← s), (β1 ←)}, whose set of PSMs is PS(P∆′) = {M3={o, ¬r, s, p, ¬α1, ¬α2, α3, β1}, M4={o, r, ¬s, ¬p, α1, α2, ¬α3, β1}}. Note that M1 (resp., M2) differs from M3 (resp., M4) in the status of α1 and α2 (resp., α3).

4 Conclutions and FutureWork

We have proposed a general framework that 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 [Gebser et al., 2018], as well as other complete-based semantics using classical program rewriting [Janhunen et al., 2006; Sakama and Rienstra, 2017; Gaggl et al., 2015].

Future work will be devoted to generalize our approach to also deal with AF-based framework with probabilities [Fazzinga et al., 2015; Alfano et al., 2020a], weights [Bistarelli et al., 2018], preferences [Amgoud and Vesic, 2011; Modgil, 2009], and constraints [Alfano et al., 2021b]. 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 [Alfano et al., 2020b; Alfano et al., 2021a].