Argumentation frameworks with necessities and their relationship with logic programs

Abstract

This paper presents a comprehensive study of argumentation frameworks with necessities (AFNs), a bipolar extension of Dung Abstract argumentation frameworks (AFs) where the support relation captures a positive interaction between arguments having the meaning of necessity: the acceptance of an argument may require the acceptance of other argument(s). The paper discusses new main acceptability semantics for AFNs and their characterization both by a direct approach and a labelling approach. It examines the relationship between AFNs and Dung AFs and shows the gain provided by the former in terms of concision. Finally, the paper shows how to represent an AFN as a normal logic program (LP) and vice versa and in both cases establishes a one-to-one correspondence between extensions under the main acceptability semantics (except for semi-stable semantics where the correspondence is not completely full) of an AFN and particular cases of 3-valued stable models of normal LPs.

1. Introduction

In the last decades, formal argumentation has become an attractive research field in artificial intelligence (AI) (see e.g. [15,84]). It provides a form of reasoning based on the construction and the evaluation of arguments in favor or against a given claim. Argumentation-based models are proposed in different AI domains such as defeasible reasoning [79,87] and multi-agent systems [17,64,82,84]. Moreover, the argumentation approach has been used to provide solutions to several problems including decision making [10,12], negotiation [11,13], opinion analysis [18], practical reasoning [9], critical thinking [63], ontology alignment [89,92], statistical modeling [86], etc. (see [65] for more practical applications of formal argumentation).

Roughly speaking, works on argumentation may be divided into two classes. The first one is interested in the internal structure of arguments. We find in this class approaches that instantiate arguments from knowledge bases expressed in propositional logic [4–6,17,61], in conditional logic [16], in description logic [94], in rule-based systems [7,68] or in logic programming [30,43]. The interactions between arguments are expressed by attack relations (defeaters, undercuts, rebuttals, etc.) induced from the arguments’ structure. The second class is that of abstract approaches which consider arguments as atomic entities and do not care about their internal structure. It focuses rather on the interaction between arguments and aims at drawing plausible conclusions according to some acceptability principle. Most of the works in this class are developed around Dung’s abstract model [53] where the unique interaction between arguments is a negative one captured by an attack relation. Extensive research has been done to generalize this model (see e.g. [8,19,21,22,38–41,44,46,47,69–72]).

Besides, one interesting research topic, which goes back to Dung’s seminal work [53], is to explore links between Argumentation Frameworks (AFs) and Logic Programs (LPs) [29,30,73]. One important research line in this context (see e.g.. [29,30]) consists in representing an LP as a Dung system following an instantiation process similar to that used in rule-based systems [7,68] and then different 3-valued semantics of an LP are related to well-known acceptability semantics of the corresponding AF.

Some relatively recent works have addressed frameworks that include, in addition to an attack relation, positive interactions between arguments represented by a support relation. Dung AFs define an implicit positive interaction between arguments by means of the notion of defense: an argument defends another one if it attacks all its attackers. But some positive influences between arguments may not be reduced to the notion of defense and this motivates the study of new explicit support relations. Notice that in [77], the need for bipolar approaches has been empirically assessed. For our purpose in this work, let us illustrate this idea by the following example: (another example following the same principle is given in [45] inspired from [82] and [39]): Consider the following exchange of arguments during a meeting in a computer science department to organize exams:

Only the basic notions of automata theory have been presented to students. Thus, the exam of this unit cannot be taken shortly.

Normally, all the exams are taken during the same week and the exams of all the other teaching units are expected to be soon.

The teacher of the automata theory unit was absent several times.

Clearly, arguments (A) and (B) attack each other. In contrast, the argument (C) supports (A) since it brings some information in favor of it. However, perceiving this support as a defense of (A) by (C) against (B) does not make sense since it is counter-intuitive to consider an attack from (C) to (B).

The work in [38] is an early attempt to explicitly represent a support relation in abstract argumentation. It uses an unspecified meaning of the support relation without considering additional constraints. This generality leads in some contexts to counter-intuitive conclusions since the correct interactions between attacks and supports depend strongly on the exact meaning of the support. According to the exact meaning given to support, several approaches have been proposed. The evidential support approach [72] limits acceptance to arguments supported by some evidence provided either directly from the environment (prima facie arguments) or from other supported arguments (standard arguments). In the deductive support approach, a supports b if the acceptance of a suffices to accept b. The abstract dialectical frameworks [22] extend Dung AFs by generalizing the acceptability conditions of an argument according to the acceptability of other arguments related to it. Finally, the backing relation approach [43,44] captures the meaning of support used in Toulmin’s model of argumentation (see [45] for a survey on the different approaches on support in argumentation and Section 6 for a discussion of these approaches and some of their extensions).

Several extensions and applications of bipolar AFs have been proposed in the literature. We can cite the use of bipolar AFs for text exploration [28], for detecting bipolar relations from texts [26], for supporting users [27] and ranking comment sorting policies [93] in inline debate and for social networks analysis [60].

In this paper we focus on Argumentation Frameworks with Necessities (AFNs) introduced in [70,71] where the support relation has the meaning of necessity and relates sets of arguments to single arguments.

On the one hand this paper synthesizes and extends the two conference papers [70,71] (Sections 3 and 4) by introducing new concepts and detailed proofs of results (given in the Appendix). On the other hand, the paper further investigates the relationship between AFNs and LPs under 3-valued semantics.

We show in particular that the interest of using the particular meaning of necessity is twofold: First, it allows us to extend in a natural way several results concerning Dung AFs, namely the main acceptability semantics and their relationships. Hence, to directly draw conclusions from an AFN, it is not necessary to use an intermediate Dung AF (even if such an option remains available, see Section 4) or to borrow techniques from other domains such as logic programming. Moreover, the proposed framework is a proper generalization of Dung AFs in the sense that if no supports are present, the new definitions and results collapse with the classical ones of Dung AFs. Second, we show that the proposed framework is strongly related with logic programming under 3-valued semantics. We highlight in particular that thanks to the necessity relation, an easy and immediate translation of an LP into an AFN and vice versa is obtained and may be used instead of the usual but relatively complex instantiation process of arguments from an LP. In summary, the present work brings answers to the following main questions:

• How to generalize the main acceptability semantics of Dung AFs to AFNs by accommodating directly the necessity relation instead of translating the AFN into a Dung AF or using techniques from other formalisms?

• How to generalize the labelling characterization to the case of AFNs?

• How to extract a meta-argumentation model having the structure of a Dung AF from any AFN? What is the impact of using a necessity relation that relates sets of arguments to single arguments instead of a binary support relation as it is the case in most of existing works?

• How to instantiate an AFN from an LP and how to represent an AFN as an LP? In both cases, how to exploit the necessity relation to simplify the translation and how are the acceptability semantics of an AFN related to 3-valued semantics of the corresponding LP?

The rest of the paper is organized as follows. Section 2 recalls basic notions about Dung AFs and main concepts of LPs under 3-valued semantics. Section 3 presents AFNs. It introduces new notions regarding the necessity relation, generalizes the main notions of Dung AFs to the new context and presents in detail the main acceptability semantics of AFNs. Then, a labelling characterization of acceptability semantics for AFNs is presented. It extends the existing characterization for Dung AFs to take into account jointly both the attack and the necessity relations. Section 4 discusses the representation of an AFN as a meta Dung AF so that a one-to-one correspondence is established between acceptability semantics of an AFN and that of the corresponding meta Dung AF. Section 5 is devoted to a deep analysis of the links between the acceptability semantics of AFNs and 3-valued semantics of LPs. Finally, in Section 6, we discuss related work and give some perspectives for possible future work.

2. Preliminaries

2.1. Dung AFs

A Dung AF is an abstract argumentation model based on a set of arguments and the attacks between them.

Definition 2.1 (Argumentation framework).

A Dung AF is a pair $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ where $\mathcal{A}$ is a set of arguments and $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ is a binary attack relation.

Throughout the paper, we use the infix $\mathit{a}\mathcal{R}\mathit{b}$ to denote the attack $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{R}$ . Moreover, for $\mathcal{E}\subseteq \mathcal{A}$ and $\mathit{a}\in \mathcal{A}$ , we abuse notation and write $\mathit{a}\mathcal{R}\mathcal{E}$ (resp. $\mathcal{E}\mathcal{R}\mathit{a}$ ) if there is $\mathit{b}\in \mathcal{E}$ such that $\mathit{a}\mathcal{R}\mathit{b}$ (resp. $\mathit{b}\mathcal{R}\mathit{a}$ ). For $\mathcal{E}\mathrm{,}{\mathcal{E}}^{\prime }\subseteq \mathcal{A}$ , we similarly write $\mathcal{E}\mathcal{R}{\mathcal{E}}^{\prime }$ if there is $\mathit{a}\in \mathcal{E}$ and $\mathit{b}\in {\mathcal{E}}^{\prime }$ s.t. $\mathit{a}\mathcal{R}\mathit{b}$ . Finally we denote by ${\mathcal{E}}^{+}$ the set of arguments attacked by $\mathcal{E}$ , i.e., ${\mathcal{E}}^{+}=\{\mathit{a}\in \mathcal{A}\mid \mathcal{E}\mathcal{R}\mathit{a}\}$ .

Intuitively, $\mathit{a}\mathcal{R}\mathit{b}$ means that accepting a blocks the acceptance of b. In presence of various interacting arguments, one needs to know what are the sets of arguments that may be accepted collectively, called extensions. Several principles may be used as a basis to determine the extensions of a framework. Such principles are called acceptability semantics in the abstract argumentation literature. Acceptability semantics are defined on the basis of some elementary concepts that we sum up in Definition 2.2.

Definition 2.2 (Conflict-freeness, defense, characteristic function, admissibility).

Let $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an AF and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is conflict-free iff $\nexists \mathit{a}\mathrm{,}\mathit{b}\in \mathcal{E}$ s.t. $\mathit{a}\mathcal{R}\mathit{b}$ ; $\mathcal{E}$ defends an argument a iff $\forall \mathit{b}\in \mathcal{A}$ , if $\mathit{b}\mathcal{R}\mathit{a}$ , then $\mathcal{E}\mathcal{R}\mathit{b}$ ; the characteristic function ${\mathcal{F}}_{\mathcal{H}}$ is defined by: ${\mathcal{F}}_{\mathcal{H}}:2^{\mathcal{A}}\to 2^{\mathcal{A}}$ s.t. for $\mathcal{E}\subseteq \mathcal{A}$ , ${\mathcal{F}}_{\mathcal{H}}\mathrm{(}\mathcal{E}\mathrm{)}=\{\mathit{a}\in \mathcal{A}\mid \mathcal{E}\text{ defends }\mathit{a}\}$ ; $\mathcal{E}$ is admissible iff $\mathcal{E}$ is conflict-free and $\forall \mathit{a}\in \mathcal{E}$ , $\mathcal{E}$ defends a.

The main acceptability semantics1

¹

All the presented semantics have been introduced in [53] except the semi-stable semantics which has been introduced in [31].

of Dung AFs are defined as follows:

Definition 2.3 (Acceptability semantics).

Let $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be an AF and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is a complete extension iff it is admissible and contains all the elements it defends (i.e., ${\mathcal{F}}_{\mathcal{H}}\mathrm{(}\mathcal{E}\mathrm{)}=\mathcal{E}$ ); $\mathcal{E}$ is the grounded extension iff it is the ⊆-minimal complete extension; $\mathcal{E}$ is a preferred extension iff it is a ⊆-maximal complete extension; $\mathcal{E}$ is a stable extension iff it is conflict-free and attacks all the arguments outside it (i.e., ${\mathcal{E}}^{+}=\mathcal{A}\setminus \mathcal{E}$ ); $\mathcal{E}$ is a semi-stable extension iff it is a complete extension s.t. $\mathcal{E}\cup {\mathcal{E}}^{+}$ is ⊆-maximal.

Figure 1 depicts the relations between acceptability semantics (an arrow from a semantics s to a semantics s’ means that each s-extension is a s’-extension).

Fig. 1.

Relations between AF semantics.

Example 1.

Consider the Dung AF $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ depicted in Fig. 2.

Fig. 2.

A Dung AF $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ .

The admissible sets of $\mathcal{H}$ are: ∅, $\{\mathit{a}\}$ , $\{\mathit{b}\}$ and $\{\mathit{b}\mathrm{,}\mathit{d}\}$ . All of them are complete extensions except $\{\mathit{b}\}$ . The grounded extension of $\mathcal{H}$ is ∅. $\mathcal{H}$ has two preferred extensions: $\{\mathit{a}\}$ and $\{\mathit{b}\mathrm{,}\mathit{d}\}$ . Only $\{\mathit{b}\mathrm{,}\mathit{d}\}$ is a stable extension and hence is also semi-stable.

2.2. Logic programs

LPs represent a main knowledge representation formalism that has been extensively studied in AI. Indeed a large body of work has been developed around LPs and their semantics. In this paper we focus on normal LPs. A (propositional) normal LP Π is a set of rules of the form: $$\begin{array}{c}{\mathit{a}}_0\leftarrow {\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mathrm{,}\text{not }{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{a}}_{\mathit{n}}\text{with }0⩽\mathit{m}⩽\mathit{n}\end{array}$$ ${\mathit{a}}_{\mathit{i}}$ ( $0⩽{\mathit{a}}_{\mathit{i}}⩽\mathit{n}$ ) are atoms. We read such a rule as follows: if ${\mathit{a}}_1\dots {\mathit{a}}_{\mathit{m}}$ are true and none of the atoms ${\mathit{a}}_{\mathit{m}+1}\dots {\mathit{a}}_{\mathit{n}}$ is true then deduce that ${\mathit{a}}_0$ is true. For a rule r, we use the following notations: $\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}={\mathit{a}}_0$ , ${\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\}$ and ${\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ . More generally, we write: $\mathtt{Head}\mathrm{(}\mathrm{\Pi }\mathrm{)}=\{\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}|\mathit{r}\in \mathrm{\Pi }\}$ , ${\mathtt{Body}}^{+}\mathrm{(}\mathrm{\Pi }\mathrm{)}={\bigcup }_{\mathit{r}\in \mathrm{\Pi }}{\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}$ and ${\mathtt{Body}}^{-}\mathrm{(}\mathrm{\Pi }\mathrm{)}={\bigcup }_{\mathit{r}\in \mathrm{\Pi }}{\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}$ . The Herbrand base of an LP Π denoted ${\mathtt{HB}}_{\mathrm{\Pi }}$ is the set of all atoms present in Π. An LP Π is said to be basic (or positive) if ${\mathtt{Body}}^{-}\mathrm{(}\mathrm{\Pi }\mathrm{)}=\varnothing$ .

We present here a general setting based on 3-valued interpretations and capturing a wide range of semantics for LPs including the well-known bi-valued stable semantics defined in [58] by the so-called Gelfond-Lifschitz reduct.

Definition 2.4 (3-valued interpretation).

A 3-valued interpretation I is a pair $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ where T, F are disjoint subsets of $\mathtt{HB}$ . T (resp. F) stands for true (resp. false) atoms. The truth value of the remaining atoms is undefined. A 3-valued interpretation I can be equivalently defined as a function that associates to each atom a truth value in $\{\mathbf{\text{t}}\mathrm{,}\mathbf{\text{f}}\mathrm{,}\mathbf{\text{u}}\}$ s.t.: $\mathit{a}\in \mathit{T}$ iff $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ , $\mathit{a}\in \mathit{F}$ iff $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ and $\mathit{a}\in \mathtt{HB}\setminus \mathrm{(}\mathit{T}\cup \mathit{F}\mathrm{)}$ iff $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{u}}$ . In the sequel, we use according to the context, one or the other of these two equivalent definitions.

We consider the ordering ⩽ over the set $\{\mathbf{\text{f}}\mathrm{,}\mathbf{\text{t}}\mathrm{,}\mathbf{\text{u}}\}$ s.t. $\mathbf{\text{f}}⩽\mathbf{\text{u}}⩽\mathbf{\text{t}}$ and $\forall \mathit{v}\in \{\mathbf{\text{f}}\mathrm{,}\mathbf{\text{t}}\mathrm{,}\mathbf{\text{u}}\}$ , $\mathit{v}⩽\mathit{v}$ . The extension $\hat{\mathit{I}}$ of a 3-valued interpretation I is defined as follows: $\hat{\mathit{I}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}$ if a is an atom; $\hat{\mathit{I}}\mathrm{(}\text{not }\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ (resp. $\mathbf{\text{t}}$ , $\mathbf{\text{u}}$ ) if $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ (resp. $\mathbf{\text{f}}$ , $\mathbf{\text{u}}$ ); $\hat{\mathit{I}}\mathrm{(}{\mathit{A}}_1\mathrm{,}\dots \mathrm{,}{\mathit{A}}_{\mathit{n}}\mathrm{)}=\mathbf{\text{min}}\mathrm{(}\hat{\mathit{I}}\mathrm{(}{\mathit{A}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\hat{\mathit{I}}\mathrm{(}{\mathit{A}}_{\mathit{n}}\mathrm{)}\mathrm{)}$ where each ${\mathit{A}}_{\mathit{i}}$ is either an atom or an expression $\text{not }{\mathit{a}}_{\mathit{i}}$ with ${\mathit{a}}_{\mathit{i}}$ an atom. Finally, for any rule of the form $\mathit{r}:{\mathit{a}}_0\leftarrow {\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mathrm{,}\text{not }{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{a}}_{\mathit{n}}$ , we have: $\hat{\mathit{I}}\mathrm{(}\mathit{r}\mathrm{)}=\mathbf{\text{t}}$ if $\hat{\mathit{I}}\mathrm{(}{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mathrm{,}\text{not }{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{a}}_{\mathit{n}}\mathrm{)}⩽\hat{\mathit{I}}\mathrm{(}{\mathit{a}}_0\mathrm{)}$ and $\hat{\mathit{I}}\mathrm{(}\mathit{r}\mathrm{)}=\mathbf{\text{f}}$ otherwise.

Definition 2.5 (Model).

A 3-valued interpretation I is a model of an LP Π iff $\forall \mathit{r}\in \mathrm{\Pi }$ , $\hat{\mathit{I}}\mathrm{(}\mathit{r}\mathrm{)}=\mathbf{\text{t}}$ .

Given an LP Π, the operator Ψ takes a 3-valued interpretation I and gives its “immediate consequences” as follows. For every atom $\mathit{a}\in \mathtt{HB}$ :

• $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ iff there is a rule $\mathit{a}\leftarrow {\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mathrm{,}\text{not }{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{a}}_{\mathit{n}}$ in Π s.t. $\mathit{I}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\mathbf{\text{t}}$ for all i s.t. $1⩽\mathit{i}⩽\mathit{m}$ and $\mathit{I}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}=\mathbf{\text{f}}$ for all j s.t. $\mathit{m}+1⩽\mathit{j}⩽\mathit{n}$ .

• $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{u}}$ iff $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}\ne \mathbf{\text{t}}$ and there is a rule $\mathit{a}\leftarrow {\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{m}}\mathrm{,}\text{not }{\mathit{a}}_{\mathit{m}+1}\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{a}}_{\mathit{n}}$ in Π s.t. $\mathit{I}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}\ne \mathbf{\text{f}}$ for all i s.t. $1⩽\mathit{i}⩽\mathit{m}$ and $\mathit{I}\mathrm{(}{\mathit{a}}_{\mathit{j}}\mathrm{)}\ne \mathbf{\text{t}}$ for all j s.t. $\mathit{m}+1⩽\mathit{j}⩽\mathit{n}$ .

• $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ otherwise.

It has been shown (see [83]) that a positive LP Π has a unique least Herbrand model. It is worth mentioning that minimality here is w.r.t. the relation ⪯ over 3-valued interpretations defined as follows: $⟨\mathit{T}\mathrm{,}\mathit{F}⟩⪯⟨{\mathit{T}}^{\prime }\mathrm{,}{\mathit{F}}^{\prime }⟩$ iff $\mathit{T}\subseteq {\mathit{T}}^{\prime }$ and ${\mathit{F}}^{\prime }\subseteq \mathit{F}$ . Thus, intuitively a model ${\mathit{I}}_1$ is smaller than a model ${\mathit{I}}_2$ if ${\mathit{I}}_1$ contains “less truth than” ${\mathit{I}}_2$ . Moreover, this least model is exactly the least fixpoint of the operator Ψ defined above2

²

I is a fixed-point of Ψ iff $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}=\mathit{I}$ .

and can be obtained by successive application of the operator Ψ starting from the interpretation ${\mathit{I}}_0=⟨\varnothing \mathrm{,}\mathtt{HB}⟩$ .

Definition 2.6 (Extended G/L reduct).

Let Π be an LP and I be a 3-valued interpretation. The extended Gelfond-Lifschitz (G/L for short) reduct of Π w.r.t. I is the positive LP denoted ${\mathrm{\Pi }}^{\mathit{I}}$ obtained by replacing in every rule of Π, every expression $\text{not }\mathit{a}$ s.t. $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ (resp. $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ , $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{u}}$ ) by the constant $\mathbf{\text{t}}$ (resp. $\mathbf{\text{f}}$ , $\mathbf{\text{u}}$ ). Let J be the unique least model of ${\mathrm{\Pi }}^{\mathit{I}}$ , we define the operator Γ by $\mathrm{\Gamma }\mathrm{(}\mathit{I}\mathrm{)}=\mathit{J}$ .

Like in the approach of [58,59] for bi-valued stable models, the 3-valued fixpoints correspond to the 3-valued stable models called also P-stable models. Various other semantics are defined on the basis of P-stable semantics.3

³

Except for P-stable semantics which defines a P-stable model as a 3-valued interpretation I, in the original definitions of the other semantics, the corresponding models are defined as the set T of true atoms of a particular P-stable model $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ . For the sake of homogeneity we define in this paper all kinds of models as 3-valued interpretations.

Definition 2.7 (Different kinds of models).

Let Π be an LP and $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ be a 3-valued interpretation of Π. Then:

I is a P-stable model of Π iff $\mathrm{\Gamma }\mathrm{(}\mathit{I}\mathrm{)}=\mathit{I}$ .

I is a well-founded model of Π iff I is a P-stable model having the ⊆-minimal set T among all P-stable models of Π.

I is an M-stable model of Π iff I is a P-stable model having the ⊆-maximal set T among all P-stable models of Π.

I is a stable model of Π iff I is a P-stable model s.t. $\mathit{T}\cup \mathit{F}=\mathtt{HB}$ (no atom is undefined).

I is an L-stable model of Π iff I is a P-stable model having the ⊆-maximal set $\mathit{T}\cup \mathit{F}$ among all P-stable models of Π.

Example 2.

Let us consider the LPs ${\mathrm{\Pi }}_1$ , ${\mathrm{\Pi }}_2$ , ${\mathrm{\Pi }}_3$ and ${\mathrm{\Pi }}_4$ (see Fig. 3):

Fig. 3.

Examples of LPs.

${\mathrm{\Pi }}_1$ has one P-stable model $\mathit{I}=⟨\mathit{T}=\{\mathit{s}\}\mathrm{,}\mathit{F}=\{\mathit{p}\mathrm{,}\mathit{q}\}⟩$ . Indeed the extended G/L reduct of ${\mathrm{\Pi }}_1$ w.r.t. I is ${\mathrm{\Pi }}_1^{\mathit{I}}=\{\mathit{p}\leftarrow \mathit{q};\mathit{q}\leftarrow \mathit{p};\mathit{s}\leftarrow \mathbf{\text{t}}\}$ . Starting from ${\mathit{I}}_0=⟨\varnothing \mathrm{,}\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\}⟩$ , we have $\mathrm{\Psi }\mathrm{(}{\mathit{I}}_0\mathrm{)}=\mathit{I}$ , $\mathrm{\Psi }\mathrm{(}\mathit{I}\mathrm{)}=\mathit{I}$ . Thus, $\mathrm{\Gamma }\mathrm{(}\mathit{I}\mathrm{)}=\mathit{I}$ which means that I is a P-stable model of ${\mathrm{\Pi }}_1$ . It is easy to check that for all 3-valued interpretation ${\mathit{I}}^{\prime }\ne \mathit{I}$ of ${\mathrm{\Pi }}_1$ , $\mathrm{\Gamma }\mathrm{(}{\mathit{I}}^{\prime }\mathrm{)}\ne {\mathit{I}}^{\prime }$ , i.e., I is the unique P-stable model of ${\mathrm{\Pi }}_1$ which is also its unique well-founded, M-stable and L-stable model. Since ${\mathtt{HB}}_{{\mathrm{\Pi }}_1}=\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\}=\mathit{T}\cup \mathit{F}$ , I is the unique stable model of ${\mathrm{\Pi }}_1$ .

Following the same method, one can check that ${\mathrm{\Pi }}_2$ has one P-stable model $\mathit{I}=⟨\mathit{T}=\{\mathit{s}\}\mathrm{,}\mathit{F}=\varnothing ⟩$ which is also its unique well-founded, M-stable and L-stable model. Since ${\mathtt{HB}}_{{\mathrm{\Pi }}_2}=\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\}\ne \mathit{T}\cup \mathit{F}$ , I is not a stable model of ${\mathrm{\Pi }}_2$ .

${\mathrm{\Pi }}_3$ has three P-stable models: ${\mathit{I}}_1=⟨{\mathit{T}}_1=\varnothing \mathrm{,}{\mathit{F}}_1=\varnothing ⟩$ , ${\mathit{I}}_2=⟨{\mathit{T}}_2=\{\mathit{q}\}\mathrm{,}{\mathit{F}}_2=\{\mathit{p}\}⟩$ and ${\mathit{I}}_3=⟨{\mathit{T}}_3=\{\mathit{p}\mathrm{,}\mathit{y}\}\mathrm{,}{\mathit{F}}_3=\{\mathit{q}\mathrm{,}\mathit{s}\mathrm{,}\mathit{x}\}⟩$ . The well-founded model of ${\mathrm{\Pi }}_3$ is ${\mathit{I}}_1$ . ${\mathit{I}}_2$ and ${\mathit{I}}_3$ are the two M-stable models of ${\mathrm{\Pi }}_3$ and only ${\mathit{I}}_3$ is an L-stable model of ${\mathrm{\Pi }}_3$ . Since ${\mathtt{HB}}_{{\mathrm{\Pi }}_3}=\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\mathrm{,}\mathit{y}\mathrm{,}\mathit{x}\mathrm{,}\mathit{v}\mathrm{,}\mathit{w}\}\ne {\mathit{T}}_{\mathit{i}}\cup {\mathit{F}}_{\mathit{i}}$ (for $\mathit{i}\in \{1\mathrm{,}2\mathrm{,}3\}$ ), ${\mathrm{\Pi }}_3$ has no stable model.

${\mathrm{\Pi }}_4$ has one P-stable model $\mathit{I}=⟨\mathit{T}=\varnothing \mathrm{,}\mathit{F}=\varnothing ⟩$ which is also its unique well-founded, M-stable and L-stable model. Since ${\mathtt{HB}}_{{\mathrm{\Pi }}_4}=\{\mathit{p}\mathrm{,}\mathit{q}\}\ne \mathit{T}\cup \mathit{F}$ , ${\mathrm{\Pi }}_4$ has no stable model.

3. Argumentation frameworks with necessities

This section introduces AFNs, a bipolar generalization of Dung AFs where the support relation has the meaning of necessity. We show how to extend the basic concepts used in Dung AFs to accommodate the new support relation. We show then how to use the new basic concepts to generalize the main acceptability semantics to AFNs. The proposed approach has the advantage to keep the same properties and relationships for the acceptability semantics as in the classical Dung approach. Moreover, the new semantics represent proper generalizations of Dung semantics, i.e., in an AFN where the necessity relation is empty the new semantics collapse to the classical ones.

3.1. Basic concepts

An AFN extends classical Dung AF with a necessity relation $\mathcal{N}$ that relates sets of arguments to single arguments.

Definition 3.1 (Argumentation framework with necessities).

An AFN is a tuple $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ where $\mathcal{A}$ is a set of arguments, $\mathcal{R}\subseteq \mathcal{A}\times \mathcal{A}$ is a binary attack relation and $\mathcal{N}\subseteq 2^{\mathcal{A}}\times \mathcal{A}$ is a necessity relation.

The attack relation $\mathcal{R}$ is interpreted as usual: $\mathit{a}\mathcal{R}\mathit{b}$ means that the acceptance of b requires the non acceptance of a. The new relation $\mathcal{N}$ is interpreted analogously but in a positive manner as follows: $\mathit{E}\mathcal{N}\mathit{b}$ means that the acceptance of b requires the acceptance of at least an argument of E. When all the necessary sets are singletons, $\mathcal{N}$ becomes a binary relation like $\mathcal{R}$ . The general case captures the fact that an argument may satisfy a requirement by different possible combinations of arguments, instead of one possible way .4

⁴

Notice that a similar generalization of the attack relation is also possible by considering relations of the form $\mathit{E}\mathcal{R}\mathit{a}$ where the argument a is attacked by the set of arguments E but not by a subset ${\mathit{E}}^{\prime }$ of E, unless there is another explicit attack relation: ${\mathit{E}}^{\prime }\mathcal{R}\mathit{a}$ . There is no substantial difficulty to generalize the framework to this extended setting.

In presence of the necessity relation, conflict-freeness is no more the minimal requirement for any extension. It has to be reinforced by two additional requirements w.r.t. necessity relation. The first requirement is closure under ${\mathcal{N}}^{-1}$ . Intuitively, a set of arguments is closed under ${\mathcal{N}}^{-1}$ if it satisfies the necessities of each of its arguments.

Definition 3.2 (closure under ${\mathcal{N}}^{-1}$ ).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is closed under ${\mathcal{N}}^{-1}$ iff for each argument $\mathit{a}\in \mathcal{E}$ , if $\mathit{E}\mathcal{N}\mathit{a}$ for some $\mathit{E}\subseteq \mathcal{A}$ , then $\mathit{E}\cap \mathcal{E}\ne \varnothing$ .

A second requirement that must be satisfied in any extension is the absence of self-supported cycles, i.e., cycles of necessity links .5

⁵

Such cycles exist in LPs but not in Dung AFs because they do not contain any support relation.

Definition 3.3 (N-cycle freeness).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, $\mathcal{E}\subseteq \mathcal{A}$ and $\mathit{a}\in \mathcal{E}$ . We say that a is N-Cycle-Free in $\mathcal{E}$ iff for all $\mathit{E}\subseteq \mathcal{A}$ s.t. $\mathit{E}\mathcal{N}\mathit{a}$ , we have either $\mathit{E}\cap \mathcal{E}=\varnothing$ or there is $\mathit{b}\in \mathcal{E}\cap \mathit{E}$ s.t. b is N-Cycle-Free in $\mathcal{E}$ . $\mathcal{E}$ is N-Cycle-Free iff every $\mathit{a}\in \mathcal{E}$ is N-Cycle-Free in $\mathcal{E}$ .

The combination of the two previous requirements gives rise to the notion of coherence:

Definition 3.4 (Coherence).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is coherent iff it is closed under ${\mathcal{N}}^{-1}$ and N-Cycle-Free.

Intuitively, in a coherent set $\mathcal{E}$ , the necessities of each argument are satisfied and no risk of a deadlock due to necessity cycles is present.

The notion of coherence may be equivalently characterized by using the notion of a powerful argument. Intuitively, an argument a is powerful in a set of arguments $\mathcal{E}$ if it is always possible to find a sequence of distinct arguments ending by a s.t. the necessities of every argument of the sequence are satisfied by the arguments that precede it.

Definition 3.5 (Powerful argument).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . An argument $\mathit{a}\in \mathcal{A}$ is powerful in $\mathcal{E}$ iff $\mathit{a}\in \mathcal{E}$ and there is a sequence ${\mathit{a}}_0\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{k}}$ of elements of $\mathcal{E}$ s.t. ${\mathit{a}}_{\mathit{k}}=\mathit{a}$ ; there is no $\mathit{E}\subseteq \mathcal{A}$ s.t. $\mathit{E}\mathcal{N}{\mathit{a}}_0$ and for $1⩽\mathit{i}⩽\mathit{k}$ : for all $\mathit{E}\subseteq \mathcal{A}$ , if $\mathit{E}\mathcal{N}{\mathit{a}}_{\mathit{i}}$ , then $\mathit{E}\cap \{{\mathit{a}}_0\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{i}-1}\}\ne \varnothing$ .

Coherent sets are characterized in terms of powerful arguments as follows:

Proposition 3.6.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is coherent iff each $\mathit{a}\in \mathcal{E}$ is powerful in $\mathcal{E}$ .

The following proposition gives two equivalent characterizations of non powerful arguments w.r.t. to a set of arguments:

Proposition 3.7.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, $\mathcal{E}\subseteq \mathcal{A}$ and $\mathit{a}\in \mathcal{E}$ .

a is not powerful in $\mathcal{E}$ iff there is no coherent subset $\mathcal{C}$ of $\mathcal{E}$ s.t. $\mathit{a}\in \mathcal{C}$

iff $\exists \mathit{E}\subseteq \mathcal{A}$ s.t. $\mathit{E}\mathcal{N}\mathit{a}$ and $\forall \mathit{E}\subseteq \mathcal{A}$ s.t. $\mathit{E}\mathcal{N}\mathit{a}$ , $\forall \mathit{b}\in \mathit{E}\cap \mathcal{E}$ , b is not powerful in $\mathcal{E}$ .

Putting together conflict-freeness and coherence results in the notion of strong coherence which represents the new minimal requirement that any extension has to satisfy:

Definition 3.8 (Strong coherence).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is strongly coherent iff it is coherent and conflict-free.

Example 3.

Let us consider the four AFNs ${\mathcal{G}}_{\mathit{i}}=⟨{\mathcal{A}}_{\mathit{i}}\mathrm{,}{\mathcal{R}}_{\mathit{i}}\mathrm{,}{\mathcal{N}}_{\mathit{i}}⟩$ ( $1⩽\mathit{i}⩽4$ ) depicted in Fig. 4 where continuous (resp. dashed) arrows represent attacks (resp. necessities).

Fig. 4.

Four AFNs: (a) ${\mathcal{G}}_1$ , (b) ${\mathcal{G}}_2$ , (c) ${\mathcal{G}}_3$ , (d) ${\mathcal{G}}_4$ .

For ${\mathcal{G}}_1$ , the only coherent sets are ∅ and $\{\mathit{c}\}$ . In particular the set $\{\mathit{a}\mathrm{,}\mathit{b}\}$ is closed under ${\mathcal{N}}^{-1}$ but not N-Cycle-Free, hence $\{\mathit{a}\mathrm{,}\mathit{b}\}$ is not coherent. The coherent sets of ${\mathcal{G}}_2$ are those sets of arguments that contain b or c whenever they contain a. The coherent sets of ${\mathcal{G}}_3$ are those sets of arguments that contain b whenever they contain c and contain g whenever they contain f. The coherent sets of ${\mathcal{G}}_4$ are those sets of arguments that contain b or a whenever they contain c and contain c or d whenever they contain b except the set $\{\mathit{b}\mathrm{,}\mathit{c}\}$ . Indeed, the set $\{\mathit{b}\mathrm{,}\mathit{c}\}$ is closed under ${\mathcal{N}}^{-1}$ but not N-Cycle-Free, whereas the sets $\{\mathit{b}\}$ , $\{\mathit{c}\}$ , $\{\mathit{a}\mathrm{,}\mathit{b}\}$ , $\{\mathit{c}\mathrm{,}\mathit{d}\}$ are N-Cycle-Free but not closed under ${\mathcal{N}}^{-1}$ and hence they are not coherent. All the other sets of arguments not including $\{\mathit{b}\mathrm{,}\mathit{c}\}$ are coherent.

For each AFN ${\mathcal{G}}_{\mathit{i}}$ , the strongly coherent sets are limited to coherent sets that are also conflict-free.

The second ingredient in the generalization of acceptability semantics to AFNs is to redefine the notion of defense.

Definition 3.9 (Defense in AFNs).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, $\mathcal{E}\subseteq \mathcal{A}$ and $\mathit{a}\in \mathcal{A}$ . We say that $\mathcal{E}$ defends a iff $\mathcal{E}\cup \{\mathit{a}\}$ is coherent and for all $\mathit{b}\in \mathcal{A}$ , if $\mathit{b}\mathcal{R}\mathit{a}$ then for every coherent subset $\mathcal{C}\subseteq \mathcal{A}$ s.t. $\mathit{b}\in \mathcal{C}$ , $\mathcal{E}\mathcal{R}\mathcal{C}$ .

It is worth noticing that the obligation of counter-attacking is limited to those arguments that belong to at least one coherent set of arguments. This means that the attacks coming from incoherent sets of arguments are not effective and need not be counter-attacked. Based on the new definition of defense, the characteristic function of an AFN is defined exactly as in Dung AFs:

Definition 3.10 (Characteristic function of AFNs).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ . The characteristic function of $\mathcal{G}$ is defined by ${\mathcal{F}}_{\mathcal{G}}:2^{\mathcal{A}}\to 2^{\mathcal{A}}$ with ${\mathcal{F}}_{\mathcal{G}}\mathrm{(}\mathcal{E}\mathrm{)}=\{\mathit{a}\mid \mathcal{E}\text{ defends }\mathit{a}\}$ .

Finally, the last ingredient we need in generalizing the acceptability semantics to AFNs is the notion of arguments deactivated by a given set of arguments, which replaces the set of arguments attacked by a set of arguments.

Definition 3.11 (Deactivated arguments).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ be a strongly coherent subset of arguments. The set of arguments deactivated by $\mathcal{E}$ is ${\mathcal{E}}^{\mathit{d}}=\{\mathit{a}\mid \text{if }\mathcal{C}\subseteq \mathcal{A}\text{ is a coherent subset s.t. }\mathit{a}\in \mathcal{C}\text{ then }\mathcal{E}\mathcal{R}\mathcal{C}\}$ .

The set ${\mathcal{E}}^{\mathit{d}}$ includes, in addition to arguments deactivated because of a direct attack from $\mathcal{E}$ against them, the arguments that are not powerful in $\mathcal{A}$ 6

⁶

Every argument which is not powerful in $\mathcal{A}$ does not belong to any coherent set. This means that such arguments always verify the condition of Definition 3.11 and hence, are deactivated by any set of arguments $\mathcal{E}$ .

as well as the arguments that $\mathcal{E}$ “indirectly” attacks by making impossible to accept arguments from at least one set of arguments that is necessary for them.

3.2. Acceptability semantics for AFNs

Now we are ready to define the different acceptability semantics of AFNs.

Definition 3.12 (Acceptability semantics for AFNs).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ .

$\mathcal{E}$ is an admissible set iff it is strongly coherent and $\forall \mathit{a}\in \mathcal{E}$ , $\mathcal{E}$ defends a.

$\mathcal{E}$ is a complete extension iff it is admissible and $\forall \mathit{a}\in \mathcal{A}$ , if $\mathcal{E}$ defends a then $\mathit{a}\in \mathcal{E}$ .

$\mathcal{E}$ is the grounded extension iff $\mathcal{E}$ is the least fixpoint of ${\mathcal{F}}_{\mathcal{G}}$ . It is obtained by the repetitive application of ${\mathcal{F}}_{\mathcal{G}}$ starting from ∅ until a fixpoint is reached.

$\mathcal{E}$ is a preferred extension iff $\mathcal{E}$ is a maximal (w.r.t. set inclusion) admissible set.

$\mathcal{E}$ is a stable extension of $\mathcal{G}$ iff it is a strongly coherent subset of $\mathcal{A}$ s.t. for all $\mathit{a}\in \mathcal{A}\setminus \mathcal{E}$ , a is deactivated by $\mathcal{E}$ .

$\mathcal{E}$ is a semi-stable extension iff it is a complete extension and $\mathcal{E}\cup {\mathcal{E}}^{\mathit{d}}$ is maximal (w.r.t set inclusion).

Now, the following Theorem shows that the main properties and relationships that hold for Dung acceptability semantics continue to hold for AFNs, by simply using strong coherence instead of conflict-freeness and deactivated arguments instead of attacked arguments.

Theorem 3.13.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathcal{E}\subseteq \mathcal{A}$ be a strongly coherent set.

$\mathcal{E}$ is an admissible set iff $\mathcal{E}\subseteq {\mathcal{F}}_{\mathcal{G}}\mathrm{(}\mathcal{E}\mathrm{)}$ (characterization of admissible sets using the characteristic function ${\mathcal{F}}_{\mathcal{G}}$ ).

$\mathcal{E}$ is a complete extension iff $\mathcal{E}={\mathcal{F}}_{\mathcal{G}}\mathrm{(}\mathcal{E}\mathrm{)}$ (complete extensions are exactly the fixpoints of the characteristic function ${\mathcal{F}}_{\mathcal{G}}$ ).

$\mathcal{E}$ is the grounded extension of $\mathcal{G}$ iff it is the least (w.r.t. set inclusion) complete extension of $\mathcal{G}$ .

There is at least one preferred extension for $\mathcal{G}$ ; every preferred extension is a complete extension but not vice versa; $\mathcal{E}$ is a preferred extension iff it is a maximal (w.r.t. set inclusion) complete extension.

If $\mathcal{E}$ is a stable extension then $\mathcal{E}$ is a semi-stable extension but not vice versa; if $\mathcal{E}$ is a semi-stable extension, then $\mathcal{E}$ is a preferred extension but not vice versa.

If $\mathcal{E}$ is a stable extension, then $\mathcal{E}$ is a preferred extension but not vice versa; there may be zero, one or several stable extensions for $\mathcal{G}$ .

Example 3 (Cont).

We continue with the AFNs ${\mathcal{G}}_1\mathrm{,}\dots \mathrm{,}{\mathcal{G}}_4$ .

${\mathcal{G}}_1$ has two admissible sets: ∅ and $\{\mathit{c}\}$ . Indeed, $\{\mathit{c}\}$ defends itself since the only attacker of c is b and there is no coherent set containing b. We have: ${\mathcal{F}}_{{\mathcal{G}}_1}\mathrm{(}\varnothing \mathrm{)}=\{\mathit{c}\}$ , ${\mathcal{F}}_{{\mathcal{G}}_1}\mathrm{(}\{\mathit{c}\}\mathrm{)}=\{\mathit{c}\}$ . Thus $\{\mathit{c}\}$ is the unique complete extension of ${\mathcal{G}}_1$ which is also its unique grounded, preferred and semi-stable extension. Moreover, $\{\mathit{c}\}$ is also the unique stable extension of ${\mathcal{G}}_1$ since the set of arguments deactivated by $\{\mathit{c}\}$ is ${\{\mathit{c}\}}^{\mathit{d}}=\{\mathit{a}\mathrm{,}\mathit{b}\}=\mathcal{A}\setminus \{\mathit{c}\}$ (Indeed, a and b are not powerful in $\mathcal{A}$ ).

${\mathcal{G}}_2$ has two admissible sets: ∅ and $\{\mathit{d}\}$ . $\{\mathit{d}\}$ defends itself since d has no attackers. No other strongly coherent set of ${\mathcal{G}}_2$ is admissible. For instance, $\{\mathit{b}\mathrm{,}\mathit{d}\}$ is not admissible because a attacks b and $\{\mathit{a}\mathrm{,}\mathit{b}\}$ is a coherent set containing a but not attacked by $\{\mathit{b}\mathrm{,}\mathit{d}\}$ . We have: ${\mathcal{F}}_{{\mathcal{G}}_2}\mathrm{(}\varnothing \mathrm{)}=\{\mathit{d}\}$ , ${\mathcal{F}}_{{\mathcal{G}}_2}\mathrm{(}\{\mathit{d}\}\mathrm{)}=\{\mathit{d}\}$ . Thus $\{\mathit{d}\}$ is the unique complete extension of ${\mathcal{G}}_2$ which is also its unique grounded, preferred and semi-stable extension. However $\{\mathit{d}\}$ is not a stable extension since ${\{\mathit{d}\}}^{\mathit{d}}=\{\mathit{c}\}\ne \mathcal{A}\setminus \{\mathit{d}\}$ .

The admissible sets of ${\mathcal{G}}_3$ are: ∅, $\{\mathit{a}\}$ , $\{\mathit{b}\}$ and $\{\mathit{a}\mathrm{,}\mathit{d}\}$ . Let us take for instance $\{\mathit{a}\mathrm{,}\mathit{d}\}$ : a is attacked by b and a attacks b (hence a attacks any coherent set containing b) and d is attacked by c but any coherent set containing c contains b and hence is attacked by a. We have: ${\mathcal{F}}_{{\mathcal{G}}_3}\mathrm{(}\varnothing \mathrm{)}=\varnothing$ , ${\mathcal{F}}_{{\mathcal{G}}_3}\mathrm{(}\{\mathit{a}\}\mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{d}\}$ , ${\mathcal{F}}_{{\mathcal{G}}_3}\mathrm{(}\{\mathit{b}\}\mathrm{)}=\{\mathit{b}\}$ , ${\mathcal{F}}_{{\mathcal{G}}_3}\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{d}\}$ . It follows that ${\mathcal{G}}_3$ has three complete extensions: ∅, $\{\mathit{b}\}$ and $\{\mathit{a}\mathrm{,}\mathit{d}\}$ . The grounded extension of ${\mathcal{G}}_3$ is ∅. ${\mathcal{G}}_3$ has two preferred extensions that are $\{\mathit{b}\}$ and $\{\mathit{a}\mathrm{,}\mathit{d}\}$ . ${\mathcal{G}}_3$ has no stable extension since ${\{\mathit{b}\}}^{\mathit{d}}=\{\mathit{a}\}\ne \mathcal{A}\setminus \{\mathit{b}\}$ and ${\{\mathit{a}\mathrm{,}\mathit{d}\}}^{\mathit{d}}=\{\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{e}\}\ne \mathcal{A}\setminus \{\mathit{a}\mathrm{,}\mathit{d}\}$ . We have: ${\{\mathit{b}\}}^{\mathit{d}}\cup \{\mathit{b}\}=\{\mathit{a}\mathrm{,}\mathit{b}\}$ and ${\{\mathit{a}\mathrm{,}\mathit{d}\}}^{\mathit{d}}\cup \{\mathit{a}\mathrm{,}\mathit{d}\}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\}$ . Since ${\{\mathit{b}\}}^{\mathit{d}}\cup \{\mathit{b}\}\subset {\{\mathit{a}\mathrm{,}\mathit{d}\}}^{\mathit{d}}\cup \{\mathit{a}\mathrm{,}\mathit{d}\}$ , ${\mathcal{G}}_3$ admits $\{\mathit{a}\mathrm{,}\mathit{d}\}$ as a unique semi-stable extension.

The only admissible set of ${\mathcal{G}}_4$ is ∅. Namely, the strongly coherent set $\{\mathit{a}\}$ is not admissible because c attacks a and $\{\mathit{a}\mathrm{,}\mathit{c}\}$ is a coherent set containing c but not attacked by $\{\mathit{a}\}$ . A similar reasoning is valid for the non admissibility of $\{\mathit{d}\}$ . We have: ${\mathcal{F}}_{{\mathcal{G}}_4}\mathrm{(}\varnothing \mathrm{)}=\varnothing$ . Thus, ∅ is the only complete extension of ${\mathcal{G}}_4$ which is also its unique grounded, preferred and semi-stable extension. ${\mathcal{G}}_4$ has no stable extension.

The relations between AFN acceptability semantics are depicted in Fig. 5. We can notice that these relations are the same as those connecting Dung AF acceptability semantics except that AFN semantics are based on strong coherence instead of conflict-freeness as a minimal requirement for all acceptability semantics.

Fig. 5.

Relations between AFN semantics.

3.3. Labelling characterization of AFNs

The labelling approach has been proposed as an elegant characterization of acceptability semantics of Dung AFs (see e.g. [32,67]). In this approach, each argument receives a label indicating its status: accepted, rejected or undefined. Extensions under a given semantics are then characterized by labellings fulfilling particular conditions that depend on the used semantics. In this section, we show how to take into account the necessity relation in order to adapt this approach to the case of AFNs. Let us start by recalling the notion of labelling:

Definition 3.14 (Labelling).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN. A labelling is a function $\mathcal{L}:\mathcal{A}⟶\{\mathtt{in}\mathrm{,}\mathtt{out}\mathrm{,}\mathtt{undec}\}$ . We put $\text{in}\mathrm{(}\mathcal{L}\mathrm{)}=\{\mathit{a}\in \mathcal{A}|\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\text{in}\}$ , $\text{out}\mathrm{(}\mathcal{L}\mathrm{)}=\{\mathit{a}\in \mathcal{A}|\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\text{out}\}$ and $\text{undec}\mathrm{(}\mathcal{L}\mathrm{)}=\{\mathit{a}\in \mathcal{A}|\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\text{undec}\}$ and we write a labelling $\mathcal{L}$ as a triplet $\mathrm{(}\text{in}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{,}\text{out}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{,}\text{undec}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{)}$ .

In a given labelling, the label attributed to an argument may or may not be justified. For example, if all the attackers of an argument a are labelled $\mathtt{out}$ and each set E necessary for a contains at least an argument labelled $\mathtt{in}$ , it would not be justified that a be labelled $\mathtt{out}$ . This leads to the notion of legal labelling:

Definition 3.15 (Legal labelling).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, $\mathcal{L}$ be a labelling and a be an argument.

a is legally $\mathtt{in}$ iff a is labelled $\mathtt{in}$ and the two following conditions hold:

1. $\forall \mathit{b}\in \mathcal{A}$ , if $\mathit{b}\mathcal{R}\mathit{a}$ then $\mathit{b}\in \text{out}\mathrm{(}\mathcal{L}\mathrm{)}$ (all attackers of a are labelled $\mathtt{out}$ ) and

2. $\forall \mathit{E}\subseteq \mathcal{A}$ , if $\mathit{E}\mathcal{N}\mathit{a}$ then $\mathit{E}\cap \text{in}\mathrm{(}\mathcal{L}\mathrm{)}\ne \varnothing$ (at least one argument from each necessary set for a is labelled $\mathtt{in}$ ).

a is legally $\mathtt{out}$ iff a is labelled $\mathtt{out}$ and at least one of the two following conditions holds:

1. either $\exists \mathit{b}\in \mathcal{A}$ s.t. $\mathit{b}\mathcal{R}\mathit{a}$ and $\mathit{b}\in \text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ (at least one attacker of a is labelled $\mathtt{in}$ ) or

2. $\exists \mathit{E}\subseteq \mathcal{A}$ , s.t. $\mathit{E}\mathcal{N}\mathit{a}$ and $\mathit{E}\subseteq \text{out}\mathrm{(}\mathcal{L}\mathrm{)}$ (all the arguments of a necessary set for a are labelled $\mathtt{out}$ ).

a is legally $\mathtt{undec}$ iff a is labelled $\mathtt{undec}$ and the following conditions hold:

1. $\forall \mathit{b}\in \mathcal{A}$ , if $\mathit{b}\mathcal{R}\mathit{a}$ then $\mathit{b}\notin \text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ (no attacker of a is labelled $\mathtt{in}$ ) and

2. $\forall \mathit{E}\subseteq \mathcal{A}$ , if $\mathit{E}\mathcal{N}\mathit{a}$ then $\mathit{E}⊈\text{out}\mathrm{(}\mathcal{L}\mathrm{)}$ (not all the arguments of any necessary set for a are labelled $\mathtt{out}$ ) and

3. either $\exists \mathit{b}\in \mathcal{A}$ s.t. $\mathit{b}\mathcal{R}\mathit{a}$ and $\mathit{b}\notin \text{out}\mathrm{(}\mathcal{L}\mathrm{)}$ or $\exists \mathit{E}\subseteq \mathcal{A}$ s.t. $\mathit{E}\mathcal{N}\mathit{a}$ and $\mathit{E}\cap \text{in}\mathrm{(}\mathcal{L}\mathrm{)}=\varnothing$ (either at least one attacker of a is not labelled $\mathtt{out}$ or at least one necessary set for a does not contain any argument that is labelled $\mathtt{in}$ ).

Notice that for $\mathcal{N}=\varnothing$ , we find exactly the original definitions of legal labels given in [67]. In addition to legality of labels, the presence of necessity relation imposes two further constraints. Any argument which is not powerful in $\mathcal{A}$ does not belong to any extension and must be labelled $\mathtt{out}$ and since each extension $\mathcal{E}$ under any semantics must be coherent, the set of $\mathtt{in}$ arguments of any labelling characterizing any acceptability semantics for an AFN must be coherent. Labellings that satisfy these constraints are called safe labellings.

Definition 3.16 (Safe labelling).

We say that a labelling $\mathcal{L}$ is safe iff the set $\text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ is coherent and for each $\mathit{a}\in \mathcal{A}$ : if a is not powerful in $\mathcal{A}$ then $\mathit{a}\in \text{out}\mathrm{(}\mathcal{L}\mathrm{)}$ .

Once the notion of labelling is extended to the necessity relation, the different kinds of labellings are defined as usual except that they must always be safe.

Definition 3.17 (Different kinds of labellings).

A labelling $\mathcal{L}$ is:

admissible iff $\mathcal{L}$ is safe and without arguments that are illegally $\mathtt{in}$ and without arguments that are illegally $\mathtt{out}$ ;

complete iff $\mathcal{L}$ is admissible and without arguments that are illegally $\mathtt{undec}$ ;

grounded iff $\mathcal{L}$ is complete and $\text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ is ⊆-minimal;

preferred iff $\mathcal{L}$ is complete and $\text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ is ⊆-maximal;

stable iff $\mathcal{L}$ is complete and $\text{undec}\mathrm{(}\mathcal{L}\mathrm{)}=\varnothing$ and

semi-stable iff $\mathcal{L}$ is complete and $\text{undec}\mathrm{(}\mathcal{L}\mathrm{)}$ is ⊆-minimal.

Notice that since admissible labellings must be safe, all other kinds of labellings (complete, preferred, grounded, stable and semi-stable) must be safe too because all of them are admissible. Besides, admissible labellings only require that every argument which is labelled $\text{in}$ or $\text{out}$ must be legal but tolerate the illegality of arguments that are labelled $\text{undec}$ . However, complete labellings require the legality of all arguments: Every argument which is labeled $\text{in}$ (resp. $\text{out}$ , $\text{undec}$ ) must be legally $\text{in}$ (resp. $\text{out}$ , $\text{undec}$ ). Hence, Since all other kinds of labellings (grounded, preferred, stable and semi-stable) are also complete, they require the legality of all their arguments.

For Dung AFs (i.e. an AFN where $\mathcal{N}=\varnothing$ ), any set of arguments is safe. In this case, we obtain exactly the classical definitions for legally $\mathtt{in}$ , $\mathtt{out}$ and $\mathtt{undec}$ arguments and for the different kinds of labellings. The relationship between labellings and acceptability semantics for AFNs is given as follows.

Theorem 3.18.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, $\mathcal{E}\subseteq \mathcal{A}$ and $\mathcal{L}$ be a labelling of $\mathcal{G}$ .

If $\mathcal{E}$ is an admissible set of $\mathcal{G}$ then the labelling $\mathcal{L}=\mathrm{(}\mathcal{E}\mathrm{,}{\mathcal{E}}^{\mathit{d}}\mathrm{,}\mathcal{A}\setminus \mathrm{(}\mathcal{E}\cup {\mathcal{E}}^{\mathit{d}}\mathrm{)}\mathrm{)}$ is an admissible labelling of $\mathcal{G}$ . Inversely, if $\mathcal{L}$ is an admissible labelling of $\mathcal{G}$ then $\mathcal{E}=\mathit{\text{in}}\mathrm{(}\mathcal{L}\mathrm{)}$ is an admissible set of $\mathcal{G}$ and $\mathit{\text{out}}\mathrm{(}\mathcal{L}\mathrm{)}\subseteq {\mathcal{E}}^{\mathit{d}}$ .

If $\mathcal{E}$ is a complete (resp. the grounded, a preferred, a stable, a semi-stable) extension of $\mathcal{G}$ then the labelling $\mathcal{L}=\mathrm{(}\mathcal{E}\mathrm{,}{\mathcal{E}}^{\mathit{d}}\mathrm{,}\mathcal{A}\setminus \mathrm{(}\mathcal{E}\cup {\mathcal{E}}^{\mathit{d}}\mathrm{)}\mathrm{)}$ is a complete (resp. the grounded, a preferred, a stable, a semi-stable extension) labelling of $\mathcal{G}$ . Inversely, if $\mathcal{L}$ is a complete (resp. the grounded, a preferred, a stable, a semi-stable extension) labelling of $\mathcal{G}$ then $\mathcal{E}=\mathit{\text{in}}\mathrm{(}\mathcal{L}\mathrm{)}$ is a complete (resp. the grounded, a preferred, a stable, a semi-stable) extension of $\mathcal{G}$ and $\mathit{\text{out}}\mathrm{(}\mathcal{L}\mathrm{)}={\mathcal{E}}^{\mathit{d}}$ .

Example 3 (Cont).

Let us consider again our four AFNs: ${\mathcal{G}}_1\dots {\mathcal{G}}_4$ .

Consider the labellings: ${\mathcal{L}}_1=\mathrm{(}\{\mathit{c}\}\mathrm{,}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\}\mathrm{)}$ , ${\mathcal{L}}_2=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{)}$ , ${\mathcal{L}}_3=\mathrm{(}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\{\mathit{c}\}\mathrm{)}$ , and ${\mathcal{L}}_4=\mathrm{(}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\varnothing \mathrm{)}$ for ${\mathcal{G}}_1$ . In ${\mathcal{L}}_1$ c is legally $\text{in}$ because ${\mathcal{L}}_1\mathrm{(}\mathit{b}\mathrm{)}=\text{out}$ but b is illegally $\text{out}$ . Moreover, ${\mathcal{L}}_1$ is not safe because a is not powerful in $\mathcal{A}$ but $\mathit{a}\notin \text{out}\mathrm{(}{\mathcal{L}}_1\mathrm{)}$ . Thus, ${\mathcal{L}}_1$ is not admissible. ${\mathcal{L}}_2$ is not safe for the same reason and thus, is not admissible. In ${\mathcal{L}}_3$ , a and b are legally $\text{out}$ but c is illegally $\text{undec}$ . ${\mathcal{L}}_3$ is admissible but not complete. In ${\mathcal{L}}_4$ c is legally $\text{in}$ and a and b are legally $\text{out}$ . Moreover, ${\mathcal{L}}_4$ is safe and thus it is admissible and complete (no argument is illegally $\text{undec}$ ). In summary, ${\mathcal{L}}_3$ and ${\mathcal{L}}_4$ are the admissible labellings of ${\mathcal{G}}_1$ and ${\mathcal{L}}_4$ is its unique complete labelling which is also its unique grounded and preferred labelling. Moreover, since $\text{undec}\mathrm{(}{\mathcal{L}}_4\mathrm{)}=\varnothing$ , ${\mathcal{L}}_4$ is also the unique stable and semi-stable labelling of ${\mathcal{G}}_1$ .

${\mathcal{L}}_1=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{)}$ and ${\mathcal{L}}_2=\mathrm{(}\{\mathit{d}\}\mathrm{,}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{)}$ are the admissible labellings of ${\mathcal{G}}_2$ . ${\mathcal{L}}_2$ is the only complete labelling of ${\mathcal{G}}_2$ (d is illegally $\text{undec}$ in ${\mathcal{L}}_1$ ) which is also its unique grounded, preferred and semi-stable labelling. However, since $\text{undec}\mathrm{(}{\mathcal{L}}_2\mathrm{)}\ne \varnothing$ , ${\mathcal{L}}_4$ is not stable.

${\mathcal{L}}_1=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ , ${\mathcal{L}}_2=\mathrm{(}\{\mathit{a}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ , ${\mathcal{L}}_3=\mathrm{(}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ and ${\mathcal{L}}_4=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{e}\}\mathrm{,}\{\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ are the admissible labellings of ${\mathcal{G}}_3$ . Among them, only ${\mathcal{L}}_2$ is not complete (d is illegally $\text{undec}$ in ${\mathcal{L}}_2$ ). The grounded labelling is ${\mathcal{L}}_1$ , the preferred labellings are ${\mathcal{L}}_3$ and ${\mathcal{L}}_4$ . No complete labelling has an empty set of $\text{undec}$ arguments, thus no labelling is stable. The only semi-stable stable labelling (which minimizes $\text{undec}$ ) is ${\mathcal{L}}_4$ .

${\mathcal{G}}_4$ admits $\mathcal{L}=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{)}$ as the unique admissible, complete, grounded, preferred and semi-stable labelling. ${\mathcal{G}}_4$ has no stable labelling.

For each of the previous AFNs, $\mathcal{L}$ is an s-labelling ( $\mathit{s}\in \{\text{admissible}\mathrm{,}\text{complete}\mathrm{,}\text{grounded}\mathrm{,}\text{preferred}\mathrm{,}\text{stable}\mathrm{,}\text{semi-stable}\}$ ) if and only if $\text{in}\mathrm{(}\mathcal{L}\mathrm{)}$ is an s-extension.

4. AFNs and Dung AFs

A Dung AF is simply a particular case of AFN where the necessity relation is empty.

Theorem 4.1.

Let $\mathcal{H}=⟨\mathcal{A}\mathrm{,}\mathcal{R}⟩$ be a Dung AF. We define the AFN ${\mathcal{G}}_{\mathcal{H}}$ by ${\mathcal{G}}_{\mathcal{H}}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\varnothing ⟩$ . Let $\mathcal{E}\subseteq \mathcal{A}$ . $\mathcal{E}$ is an admissible set (resp. complete, grounded, preferred, stable, semi-stable extension) of $\mathcal{H}$ iff $\mathcal{E}$ is an admissible set (resp. complete, grounded preferred, stable, semi-stable extension) of ${\mathcal{G}}_{\mathcal{H}}$ .

Let us now consider the opposite issue, i.e., representing an AFN as an AF.

Given an AFN $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ , a first question we are interested in is to know if it is always possible to find a Dung AF with exactly the same arguments and which contains all the information encoded in $\mathcal{G}$ . It has been shown in [71] that the answer is positive when the necessity relation is binary (for AFNs where if $\mathit{E}\mathcal{N}\mathit{a}$ then E is a singleton). The idea is to add the implicit attacks that result from the interaction between attacks and necessities as follows: if a attacks b and b is necessary for c then a attacks indirectly c and if a requires b and b attacks c then a attacks indirectly c.

We show here that the answer is negative in the general case and one may need a greater number of arguments to encode all the information of an AFN in an AF. To show this, let us take the AFN ${\mathcal{G}}_2$ of Example 3 and let us suppose that $\mathcal{F}=⟨\mathcal{A}\mathrm{,}{\mathcal{R}}^{\prime }⟩$ is an AF encoding the same information as ${\mathcal{G}}_2$ . It is clear that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , $\mathrm{(}\mathit{d}\mathrm{,}\mathit{c}\mathrm{)}$ are in ${\mathcal{R}}^{\prime }$ . The AF $⟨\mathcal{A}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{d}\mathrm{,}\mathit{c}\mathrm{)}\}⟩$ does not have the same extensions for all the considered semantics. Apart from these two attacks, any other possible attack from an argument x to an argument y ( $\mathit{x}\mathrm{,}\mathit{y}\in \mathcal{A}$ ) is not present directly or indirectly in ${\mathcal{G}}_2$ . In particular we cannot say that d attacks a because a may be obtained either by having c or b and d attacks only c. The solution is to represent separately the two different ways to obtain a (by providing b and by providing c) as two meta arguments, say ${\mathit{A}}_1$ and ${\mathit{A}}_2$ . Only the second meta argument, involving a and c, is attacked by d. More generally, the notion of a meta-argument is defined as follows:

Definition 4.2 (Meta-argument).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and $\mathit{a}\in \mathcal{A}$ . A meta-argument associated to a is a minimal (w.r.t. set inclusion) coherent set $\mathcal{C}\subseteq \mathcal{A}$ containing a (no subset of $\mathcal{C}$ containing a is coherent).

The meta Dung AF representing an AFN is then defined as follows:

Definition 4.3 (Meta AF representing an AFN).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN. The Dung AF representing $\mathcal{G}$ is ${\mathcal{H}}_{\mathcal{G}}=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ where: ${\mathcal{A}}^{\prime }$ is the set of all meta-arguments associated to all arguments in $\mathcal{A}$ and for ${\mathcal{C}}_1\mathrm{,}{\mathcal{C}}_2\in {\mathcal{A}}^{\prime }$ , ${\mathcal{C}}_1{\mathcal{R}}^{\prime }{\mathcal{C}}_2$ iff there is $\mathit{a}\in {\mathcal{C}}_1$ and there is $\mathit{b}\in {\mathcal{C}}_2$ s.t. $\mathit{a}\mathcal{R}\mathit{b}$ .

It is worth noticing that by construction of meta-arguments, any argument which is not powerful in $\mathcal{A}$ is ruled-out.

Proposition 4.4.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, ${\mathcal{H}}_{\mathcal{G}}=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ be its corresponding meta AF and $\mathit{a}\in \mathcal{A}$ . If a is not powerful in $\mathcal{A}$ , then $\nexists \mathcal{C}\in {\mathcal{A}}^{\prime }$ s.t. $\mathit{a}\in \mathcal{C}$ .

Example 3 (Cont).

Each AFN ${\mathcal{G}}_{\mathit{i}}=⟨{\mathcal{A}}_{\mathit{i}}\mathrm{,}{\mathcal{R}}_{\mathit{i}}\mathrm{,}{\mathcal{N}}_{\mathit{i}}⟩$ is translated into ${\mathcal{H}}_{{\mathcal{G}}_{\mathit{i}}}=⟨{\mathcal{A}}_{\mathit{i}}^{\prime }\mathrm{,}{\mathcal{R}}_{\mathit{i}}^{\prime }⟩$ for $\mathit{i}\in \{1\mathrm{,}2\mathrm{,}3\mathrm{,}4\}$ .

For ${\mathcal{H}}_{{\mathcal{G}}_1}$ , the arguments a and b are not powerful in $\mathcal{A}$ and hence they do not give rise to any meta-argument. The argument c gives rise to the unique meta-argument ${\mathit{c}}^{\prime }=\{\mathit{c}\}$ . Accordingly, ${\mathcal{A}}_1^{\prime }=\{{\mathit{c}}^{\prime }\}$ and ${\mathcal{R}}_1^{\prime }=\varnothing$ (see Fig. 6-(a)).

For ${\mathcal{H}}_{{\mathcal{G}}_2}$ , the argument a gives rise to two meta-arguments: ${\mathit{a}}_1^{\prime }=\{\mathit{a}\mathrm{,}\mathit{b}\}$ and ${\mathit{a}}_2^{\prime }=\{\mathit{a}\mathrm{,}\mathit{c}\}$ . b (resp. c, d) gives rise to the unique meta-argument ${\mathit{b}}^{\prime }=\{\mathit{b}\}$ (resp. ${\mathit{c}}^{\prime }=\{\mathit{c}\}$ , ${\mathit{d}}^{\prime }=\{\mathit{d}\}$ ). Thus, ${\mathcal{A}}_2^{\prime }=\{{\mathit{a}}_1^{\prime }\mathrm{,}{\mathit{a}}_2^{\prime }\mathrm{,}{\mathit{b}}^{\prime }\mathrm{,}{\mathit{c}}^{\prime }\mathrm{,}{\mathit{d}}^{\prime }\}$ . ${\mathcal{R}}_2^{\prime }$ is depicted in Fig. 6-(b).

For ${\mathcal{H}}_{{\mathcal{G}}_3}$ , the argument c (resp. f) gives rise to the meta-arguments: ${\mathit{c}}^{\prime }=\{\mathit{b}\mathrm{,}\mathit{c}\}$ (resp. ${\mathit{f}}^{\prime }=\{\mathit{f}\mathrm{,}\mathit{g}\}$ ). The argument a (resp. b, d, e, g) gives rise to the unique meta-argument ${\mathit{a}}^{\prime }=\{\mathit{a}\}$ (resp. ${\mathit{b}}^{\prime }=\{\mathit{b}\}$ , ${\mathit{d}}^{\prime }=\{\mathit{d}\}$ , ${\mathit{e}}^{\prime }=\{\mathit{e}\}$ , ${\mathit{g}}^{\prime }=\{\mathit{g}\}$ ). Thus ${\mathcal{A}}_3^{\prime }=\{{\mathit{a}}^{\prime }\mathrm{,}{\mathit{b}}^{\prime }\mathrm{,}{\mathit{c}}^{\prime }\mathrm{,}{\mathit{d}}^{\prime }\mathrm{,}{\mathit{e}}^{\prime }\mathrm{,}{\mathit{f}}^{\prime }\mathrm{,}{\mathit{g}}^{\prime }\}$ . ${\mathcal{R}}_3^{\prime }$ is depicted in Fig. 6-(c).

For ${\mathcal{H}}_{{\mathcal{G}}_4}$ , the argument b (resp. c) gives rise to the meta-argument: ${\mathit{b}}^{\prime }=\{\mathit{b}\mathrm{,}\mathit{d}\}$ (resp. ${\mathit{c}}^{\prime }=\{\mathit{a}\mathrm{,}\mathit{c}\}$ ). The argument a (resp. d) gives rise to the meta-argument ${\mathit{a}}^{\prime }=\{\mathit{a}\}$ (resp. ${\mathit{d}}^{\prime }=\{\mathit{d}\}$ ). Note that $\{\mathit{b}\mathrm{,}\mathit{c}\}$ is not a meta-argument since it is not coherent (it is not N-Cycle-Free). Thus, ${\mathcal{A}}_4^{\prime }=\{{\mathit{a}}^{\prime }\mathrm{,}{\mathit{b}}^{\prime }\mathrm{,}{\mathit{c}}^{\prime }\mathrm{,}{\mathit{d}}^{\prime }\}$ . ${\mathcal{R}}_4^{\prime }$ is depicted in Fig. 6-(d).

Fig. 6.

The Dung AFs associated to the four AFNs ${\mathcal{G}}_1$ , ${\mathcal{G}}_2$ , ${\mathcal{G}}_3$ and ${\mathcal{G}}_4$ .

The following result shows that there is a full correspondence between the extensions of an AFN $\mathcal{G}$ and those of the corresponding meta Dung AF ${\mathcal{H}}_{\mathcal{G}}$ under all the considered semantics.

Theorem 4.5.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN, ${\mathcal{H}}_{\mathcal{G}}=⟨{\mathcal{A}}^{\prime }\mathrm{,}{\mathcal{R}}^{\prime }⟩$ be its corresponding Dung AF.

If $\mathcal{E}\subseteq \mathcal{A}$ is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of $\mathcal{G}$ then ${\mathrm{\Gamma }}_{\mathcal{E}}=\{{\mathcal{C}}_{\mathit{a}}\mid \mathit{a}\in \mathcal{E}\mathrm{,}{\mathcal{C}}_{\mathit{a}}\mathit{\text{ is a meta-argument associated to }}\mathit{a}\mathit{\text{ and }}{\mathcal{C}}_{\mathit{a}}\subseteq \mathcal{E}\}$ is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of ${\mathcal{H}}_{\mathcal{G}}$ .

Inversely, if Γ is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of ${\mathcal{H}}_{\mathcal{G}}$ , then ${\mathcal{E}}_{\mathrm{\Gamma }}={\bigcup }_{\mathcal{C}\in \mathrm{\Gamma }}\mathcal{C}$ is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of $\mathcal{G}$ .

Example 3 (Cont).

It is easy to check that for any of the considered acceptability semantics, the extensions of each ${\mathcal{G}}_{\mathit{i}}$ ( $1⩽{\mathcal{G}}_{\mathit{i}}⩽4$ ) correspond exactly (in the sense of theorem 4.5) to the extensions of ${\mathcal{H}}_{{\mathcal{G}}_{\mathit{i}}}$ under the same semantics.

It is worth noticing that by using the translation described above there are AFNs whose corresponding AFs contain a number of arguments that is exponential with respect to the number of arguments in the initial AFN. To illustrate this, let us take the example of the AFN $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ where $\mathcal{A}=\{\mathit{a}\}\cup {\mathcal{A}}_1\cup \dots {\mathcal{A}}_{\mathit{n}}$ , each ${\mathcal{A}}_{\mathit{i}}$ contains p arguments ( $\mathit{p}\mathrm{>}1$ ) and ${\mathcal{A}}_{\mathit{i}}\mathcal{N}\mathit{a}$ (for $1⩽\mathit{i}⩽\mathit{n}$ ). Let $\mathcal{H}$ be the corresponding AF. The number of arguments in $\mathcal{G}$ is $1+\mathit{p}\times \mathit{n}$ . Each set $\{\mathit{a}\mathrm{,}{\mathit{b}}_1\mathrm{,}\dots {\mathit{b}}_{\mathit{n}}\}$ s.t. ${\mathit{b}}_{\mathit{i}}\in {\mathcal{A}}_{\mathit{i}}$ for $1⩽\mathit{i}⩽\mathit{n}$ is a minimal coherent set containing a, i.e., is a meta argument in $\mathcal{H}$ . The number of meta arguments corresponding to a is ${\mathit{p}}^{\mathit{n}}$ and each argument x of $\mathcal{A}\setminus \{\mathit{a}\}$ gives rise to one meta argument ( $\{\mathit{x}\}$ ). The total number of the meta arguments is then ${\mathit{p}}^{\mathit{n}}+\mathit{p}\times \mathit{n}$ .

This means that even if the information present in an AFN may always be encoded by a Dung AF, the use of an AFN in general, may allow a representation that is significantly more concise than that obtained by moving to the corresponding AF using the translation described in this section. The question of whether there exists alternative translations from AFNs to AFs that provide more concise representations reminds open and will be addressed in future work.

5. AFNs and logic programs

Most of the works done in the domain of connecting LPs to abstract argumentation use Dung AFs as an abstract argumentation formalism (see [30,33,53,55,56]).

This section addresses the issue of connecting AFNs and LPs under 3-valued semantics. We consider both the representation of an LP as an AFN and vice versa. In both cases, we establish the correspondences between acceptability semantics of AFNs and different kinds of partial stable models of LPs.

5.1. From a logic program to an AFN

We present in this section a straightforward representation of any LP as an AFN where each rule of the LP is represented as an argument in the AFN. Accordingly, the proposed instantiation is no more based on a complex process that constructs arguments from the knowledge base by combining sets of rules (see e.g. [7,30,33]). This shows in particular the usefulness of AFN as an abstract reasoning tool to be used for knowledge bases expressed by LPs.

Before discussing the representation of LPs as AFNs, let us first consider some technical requirements that will make easier the subsequent development. We present a kind of pre-processing that is performed on any LP Π to produce another LP ${\mathrm{\Pi }}^{\prime }$ which has exactly the same models as Π under any semantics but is more suitable to be represented as an AFN. This pre-processing is based on the remark that: (1) if a rule in an LP has in its positive body an atom that never appears as a head of any rule, then this rule may never be applied and may be removed from the LP; (2) if a rule in an LP has in its negative body an atom that never appear as a head of any rule, then this rule may be simplified by removing this part of its negative body. The pre-processing step consists in repeatedly applying (1) and (2) until reaching a fixpoint, i.e., until in the resulting LP ${\mathrm{\Pi }}^{\prime }$ , any atom in the body of any rule appears as a head in at least one rule, i.e., the Herbrand base of ${\mathrm{\Pi }}^{\prime }$ is ${\mathtt{HB}}_{{\mathrm{\Pi }}^{\prime }}=\mathtt{Head}\mathrm{(}{\mathrm{\Pi }}^{\prime }\mathrm{)}$ . Notice that because each step of the pre-processing process can only remove rules and/or negative atoms, it is sure to have a fixpoint.

Theorem 5.1.

Let Π be an LP and ${\mathrm{\Pi }}^{\prime }$ be the LP which is the fixpoint obtained from Π by repeatedly removing every rule r s.t. ${\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}⊈\mathtt{Head}\mathrm{(}\mathrm{\Pi }\mathrm{)}$ and every expression $\mathit{\text{not }}\mathit{a}$ s.t. $\mathit{a}\notin \mathtt{Head}\mathrm{(}\mathrm{\Pi }\mathrm{)}$ . Then, a 3-valued interpretation $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ is a P-stable model of Π if and only if ${\mathit{I}}^{\prime }=⟨\mathit{T}\mathrm{,}{\mathit{F}}^{\prime }⟩$ is a P-stable model of ${\mathrm{\Pi }}^{\prime }$ where ${\mathit{F}}^{\prime }=\mathit{F}\cap {\mathtt{HB}}_{{\mathrm{\Pi }}^{\prime }}$ .

$\hat{\mathit{I}}$ As a result of the previous theorem, the same result continues to hold for all the other models that we consider in this paper.

Corollary 5.2.

Let Π be an LP and ${\mathrm{\Pi }}^{\prime }$ be the LP obtained from Π by the method described in Theorem  5.1 . Then, a 3-valued interpretation I is a well-founded (resp. M-stable, stable, L-stable) model of Π if and only if ${\mathit{I}}^{\prime }=⟨\mathit{T}\mathrm{,}{\mathit{F}}^{\prime }⟩$ is a well-founded (resp. M-stable, stable, L-stable) model of ${\mathrm{\Pi }}^{\prime }$ where ${\mathit{F}}^{\prime }=\mathit{F}\cap {\mathtt{HB}}_{{\mathrm{\Pi }}^{\prime }}$ .

Now, without loss of generality, we consider in the rest of the paper only LPs that have already been pre-processed. That is, any LP Π used in what follows is s.t.: ${\bigcup }_{\mathit{r}\in \mathrm{\Pi }}{\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}\subseteq \mathtt{Head}\mathrm{(}\mathrm{\Pi }\mathrm{)}$ and ${\bigcup }_{\mathit{r}\in \mathrm{\Pi }}{\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}\subseteq \mathtt{Head}\mathrm{(}\mathrm{\Pi }\mathrm{)}$ . Let us call this class of LPs AFN-logic programs (AFN-LPs). This is the class of LPs that are directly translatable into AFNs by our proposed approach. Notice that every LP can be transformed into an AFN-Program preserving its semantics (see Theorem 5.1).

Two kinds of interactions are possible between the rules of an LP. To see that, let Π be an LP and r be a rule of Π, then r is blocked if one of the atoms of its negative body is inferred. So, r is attacked by any rule whose head is present in ${\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}$ . On the other hand, if a is an atom of ${\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}$ , then r cannot be applied unless at least one rule of Π whose head is a is applied. This corresponds exactly to the meaning of the necessity relation in an AFN. Accordingly, the translation of an LP into an AFN does not need any complex construction of arguments since the rules themselves can serve as arguments.7 ⁷

This explains why we focused on this particular setting where the roles of attacks and supports are not symmetric.

Definition 5.3 (The AFN representing an LP).

Let $\mathrm{\Pi }=\{{\mathit{r}}_1\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{n}}\}$ be an LP. The AFN representing Π is defined by ${\mathcal{G}}_{\mathrm{\Pi }}=⟨\mathrm{\Pi }\mathrm{,}{\mathcal{R}}_{\mathrm{\Pi }}\mathrm{,}{\mathcal{N}}_{\mathrm{\Pi }}⟩$ where:

if $\mathit{E}\subseteq \mathrm{\Pi }$ is a subset of rules having the same head (denoted $\mathtt{Head}\mathrm{(}\mathit{E}\mathrm{)}$ ) and $\mathit{r}\in \mathrm{\Pi }$ is a rule s.t. $\mathtt{Head}\mathrm{(}\mathit{E}\mathrm{)}\in {\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}$ , then we put $\mathit{E}{\mathcal{N}}_{\mathrm{\Pi }}\mathit{r}$ ;

if $\mathit{r}\mathrm{,}{\mathit{r}}^{\prime }\in \mathrm{\Pi }$ are two rules s.t. $\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}\in {\mathtt{Body}}^{-}\mathrm{(}{\mathit{r}}^{\prime }\mathrm{)}$ then we put $\mathit{r}{\mathcal{R}}_{\mathrm{\Pi }}{\mathit{r}}^{\prime }$ .

Before giving the results that relate the models of an LP and the extensions of the corresponding AFN, we need two further definitions allowing one to extract a labelling from a 3-valued interpretation and vice versa.

Definition 5.4 (From a labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ to a 3-valued interpretation of Π).

Let $\mathrm{\Pi }=\{{\mathit{r}}_1\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{n}}\}$ be an LP and ${\mathcal{G}}_{\mathrm{\Pi }}=⟨\mathrm{\Pi }\mathrm{,}{\mathcal{R}}_{\mathrm{\Pi }}\mathrm{,}{\mathcal{N}}_{\mathrm{\Pi }}⟩$ its corresponding AFN. Let $\mathcal{L}=⟨\text{IN}\mathrm{,}\text{OUT}\mathrm{,}\text{UND}⟩$ be a labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ . The 3-valued interpretation associated to $\mathcal{L}$ is denoted $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ and defined as follows. For every $\mathit{a}\in {\mathtt{HB}}_{\mathrm{\Pi }}$ :

if there is a rule $\mathit{r}\in \mathrm{\Pi }$ s.t. $\mathit{a}=\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}$ and $\mathcal{L}\mathrm{(}\mathit{r}\mathrm{)}=\mathtt{in}$ then a is interpreted as true, i.e., $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ .

if a is not interpreted as true and there is a rule $\mathit{r}\in \mathrm{\Pi }$ s.t. $\mathit{a}=\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}$ and $\mathcal{L}\mathrm{(}\mathit{r}\mathrm{)}=\mathtt{undec}$ then a is interpreted as undefined i.e., $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{u}}$ .

Otherwise, i.e., if for every rule $\mathit{r}\in \mathrm{\Pi }$ s.t. $\mathit{a}=\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}$ we have $\mathcal{L}\mathrm{(}\mathit{r}\mathrm{)}=\mathtt{out}$ then a is interpreted as false, i.e., $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ .

Definition 5.5 (From a 3-valued interpretation of Π to a labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ ).

Let $\mathrm{\Pi }=\{{\mathit{r}}_1\mathrm{,}\dots \mathrm{,}{\mathit{r}}_{\mathit{n}}\}$ be an LP and ${\mathcal{G}}_{\mathrm{\Pi }}=⟨\mathrm{\Pi }\mathrm{,}{\mathcal{R}}_{\mathrm{\Pi }}\mathrm{,}{\mathcal{N}}_{\mathrm{\Pi }}⟩$ its corresponding AFN. Let $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ be a 3-valued interpretation of Π. The labelling associated to I is denoted $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ and defined as follows. For every $\mathit{r}\in \mathrm{\Pi }$ :

if ${\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}\subseteq \mathit{T}$ and ${\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}\subseteq \mathit{F}$ then r is labelled $\mathtt{in}$ in $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

if ${\mathtt{Body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}\cap \mathit{F}\ne \varnothing$ or ${\mathtt{Body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}\cap \mathit{T}\ne \varnothing$ then r is labelled $\mathtt{out}$ in $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

Otherwise, r is labelled $\mathtt{undec}$ in $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

Now we are ready to establish the relationships between 3-valued semantics of an LP and acceptability semantics of the corresponding AFN.

Theorem 5.6.

Let Π be an LP and ${\mathcal{G}}_{\mathrm{\Pi }}$ be the AFN representing Π.

If $\mathcal{L}$ is a complete (resp. the grounded, a preferred, a stable) labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ then $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ is a P-stable (resp. the well-founded, an M-stable, a stable) model of Π. Inversely, if I is a P-stable (resp. the well-founded, an M-stable, a stable) model of Π then $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ is a complete (resp. the grounded, a preferred, a stable) labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ .

It is possible to find a semi-stable labelling $\mathcal{L}$ of ${\mathcal{G}}_{\mathrm{\Pi }}$ s.t. $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ is not an L-stable model of Π. Inversely, it is possible to find an L-stable model I of Π s.t. $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ is not a semi-stable labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ .

In summary, except for the case of L-stable models and semi-stable semantics, there is a bijection between semantics of an LP and that of the corresponding AFN. It is worth mentioning that this same exception for semi-stable semantics has been encountered in [30] when translating LPs into Dung AFs. Similarly to [30], we can show that L-stable models of an LP are obtained from the complete labellings, not by minimizing first the set of undefined arguments and then take the conclusions of arguments labelled $\mathtt{in}$ , but by directly minimizing the set of conclusions of the undefined arguments. Theorem 5.7.

Let Π be an LP and ${\mathcal{G}}_{\mathrm{\Pi }}$ be the AFN representing Π.

If $\mathcal{L}=\mathrm{(}\mathit{\text{IN}}\mathrm{,}\mathit{\text{OUT}}\mathrm{,}\mathit{\text{UND}}\mathrm{)}$ is a complete labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ that minimizes (w.r.t. set inclusion) the set $\{\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}|\mathit{r}\in \mathit{\text{UND}}\}$ then $\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ is an L-stable model of Π. Inversely, if $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ is an L-stable model of Π then $\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ is a complete labelling of ${\mathcal{G}}_{\mathrm{\Pi }}$ that minimizes (w.r.t. set inclusion) the set $\{\mathtt{Head}\mathrm{(}\mathit{r}\mathrm{)}|\mathit{r}\in \mathit{\text{UND}}\}$ .

Example 2 (Cont).

Consider again the LPs ${\mathrm{\Pi }}_1$ , ${\mathrm{\Pi }}_2$ , ${\mathrm{\Pi }}_3$ and ${\mathrm{\Pi }}_4$ given in Example 2. Using Definition 5.3, it is easy to check that the AFN ${\mathcal{G}}_{{\mathrm{\Pi }}_1}$ (resp. ${\mathcal{G}}_{{\mathrm{\Pi }}_2}$ , ${\mathcal{G}}_{{\mathrm{\Pi }}_3}$ , ${\mathcal{G}}_{{\mathrm{\Pi }}_4}$ ) representing the LP ${\mathrm{\Pi }}_1$ (resp. ${\mathrm{\Pi }}_2$ , ${\mathrm{\Pi }}_3$ , ${\mathrm{\Pi }}_4$ ) corresponds exactly to the AFN ${\mathcal{G}}_1$ (resp. ${\mathcal{G}}_2$ , ${\mathcal{G}}_3$ , ${\mathcal{G}}_4$ ) depicted in Fig. 4-(a) (resp. Fig. 4-(b), Fig. 4-(c), Fig. 4-(d)).

Recall that ${\mathrm{\Pi }}_1$ has one P-stable model $\mathit{I}=⟨\{\mathit{s}\}\mathrm{,}\{\mathit{p}\mathrm{,}\mathit{q}\}⟩$ which is also its unique well-founded, M-stable, stable and L-stable model and ${\mathcal{G}}_1$ has one complete labelling $\mathcal{L}=\mathrm{(}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\varnothing \mathrm{)}$ which is also its unique grounded, preferred, stable and semi-stable labelling. We can check that $\mathit{I}=\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}=\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

${\mathrm{\Pi }}_2$ has one P-stable model $\mathit{I}=⟨\{\mathit{s}\}\mathrm{,}\varnothing ⟩$ which is also its unique well-founded, M-stable and L-stable model but ${\mathrm{\Pi }}_2$ has no stable model. ${\mathcal{G}}_2$ has one complete labelling $\mathcal{L}=\mathrm{(}\{\mathit{d}\}\mathrm{,}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{)}$ which is also its unique grounded, preferred and semi-stable labelling but ${\mathcal{G}}_2$ has no stable labelling. We have: $\mathit{I}=\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}=\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

${\mathrm{\Pi }}_3$ has three P-stable models ${\mathit{I}}_1=⟨\varnothing \mathrm{,}\varnothing ⟩$ , ${\mathit{I}}_2=⟨\{\mathit{q}\}\mathrm{,}\{\mathit{p}\}⟩$ , ${\mathit{I}}_3=⟨\{\mathit{p}\mathrm{,}\mathit{t}\}\mathrm{,}\{\mathit{q}\mathrm{,}\mathit{s}\mathrm{,}\mathit{u}\}⟩$ . Its well-founded model is ${\mathit{I}}_1$ , its preferred models are ${\mathit{I}}_2$ and ${\mathit{I}}_3$ , its unique L-stable model is ${\mathit{I}}_3$ and it has no stable model. ${\mathcal{G}}_3$ has three complete labellings: ${\mathcal{L}}_1=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ , ${\mathcal{L}}_2=\mathrm{(}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ and ${\mathcal{L}}_3=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{e}\}\mathrm{,}\{\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ . Its grounded labelling is ${\mathcal{L}}_1$ , its preferred labellings are ${\mathcal{L}}_2$ and ${\mathcal{L}}_3$ , its unique semi-stable labelling is ${\mathcal{L}}_3$ and it has no stable labelling. We can check that ${\mathit{I}}_{\mathit{i}}=\mathtt{Int}\mathrm{(}{\mathcal{L}}_{\mathit{i}}\mathrm{)}$ for $\mathit{i}\in \{1\mathrm{,}2\mathrm{,}3\}$ .

${\mathrm{\Pi }}_4$ has one P-stable model $\mathit{I}=⟨\varnothing \mathrm{,}\varnothing ⟩$ which is also its unique well-founded, M-stable and L-stable model but ${\mathrm{\Pi }}_4$ has no stable model. ${\mathcal{G}}_4$ has one complete labelling $\mathcal{L}=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{)}$ which is also its unique grounded, preferred and semi-stable labelling but ${\mathcal{G}}_4$ has no stable labelling. We have: $\mathit{I}=\mathtt{Int}\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}=\mathtt{Label}\mathrm{(}\mathit{I}\mathrm{)}$ .

Notice that as stated in Theorem 5.6, in general, there is no full correspondence between L-stable models of an LP and semi- stable labellings of its representing AFN (see counter-examples in the proof of Theorem 5.6 given in the Appendix).

5.2. From an AFN to a logic program

Let us consider now the opposite issue, i.e, the representation of an AFN as an LP. The idea is that each argument a gives rise in the LP to an atom and a rule ( ${\mathit{r}}_{\mathit{a}}$ ) that expresses its acceptability conditions. Intuitively, whenever an argument b attacks a, the expression $\text{not }\mathit{b}$ appears in the body of ${\mathit{r}}_{\mathit{a}}$ . Similarly, whenever a set of arguments E is necessary for a, we introduce a new atom e which appears in the positive body of ${\mathit{r}}_{\mathit{a}}$ and a rule for every argument $\mathit{x}\in \mathit{E}$ telling that e is obtained from x. This translation is formally given as follows:

Definition 5.8 (The LP representing an AFN).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN. The LP ${\mathrm{\Pi }}_{\mathcal{G}}$ representing $\mathcal{G}$ is constructed as follows:

Each argument of $\mathcal{A}$ is considered as an atom in ${\mathrm{\Pi }}_{\mathcal{G}}$ . Moreover, let ${\mathit{E}}_1\mathrm{,}\dots \mathrm{,}{\mathit{E}}_{\mathit{p}}$ be all the subsets of $\mathcal{A}$ s.t. for every ${\mathit{E}}_{\mathit{i}}$ there is some argument $\mathit{a}\in \mathcal{A}$ with ${\mathit{E}}_{\mathit{i}}\mathcal{N}\mathit{a}$ . We associate to each ${\mathit{E}}_{\mathit{i}}$ an atom (denoted ${\mathit{e}}_{\mathit{i}}$ ) in ${\mathrm{\Pi }}_{\mathcal{G}}$ . Thus, the Herbrand base of ${\mathrm{\Pi }}_{\mathcal{G}}$ is ${\mathtt{HB}}_{{\mathrm{\Pi }}_{\mathcal{G}}}=\mathcal{A}\cup {\mathcal{A}}^{\prime }$ where ${\mathcal{A}}^{\prime }=\{{\mathit{e}}_1\mathrm{,}\dots \mathrm{,}{\mathit{e}}_{\mathit{p}}\}$ .

For every argument $\mathit{a}\in \mathcal{A}$ , let ${\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{m}}$ be its attackers and let ${\mathit{E}}_1\mathrm{,}\dots \mathrm{,}{\mathit{E}}_{\mathit{k}}$ be all the subsets of $\mathcal{A}$ s.t. ${\mathit{E}}_{\mathit{i}}\mathcal{N}\mathit{a}$ for $0⩽\mathit{i}⩽\mathit{k}$ . The argument a gives rise in ${\mathrm{\Pi }}_{\mathcal{G}}$ to the rule: ${\mathit{r}}_{\mathit{a}}:\mathit{a}\leftarrow {\mathit{e}}_1\mathrm{,}\dots \mathrm{,}{\mathit{e}}_{\mathit{k}}\mathrm{,}\text{not }{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}\text{not }{\mathit{b}}_{\mathit{m}}$ .

For every atom ${\mathit{e}}_{\mathit{i}}$ associated to a set ${\mathit{E}}_{\mathit{i}}$ we add $|{\mathit{E}}_{\mathit{i}}|$ rules as follows: for every $\mathit{x}\in {\mathit{E}}_{\mathit{i}}$ , the rule: ${\mathit{e}}_{\mathit{i}}\leftarrow \mathit{x}$ is added to ${\mathrm{\Pi }}_{\mathcal{G}}$ .

To extract a 3-valued interpretation from a labelling and vice versa, let us define the functions ${\mathtt{Int}}^{\prime }$ and ${\mathtt{Label}}^{\prime }$ .

Definition 5.9 (From a labelling of $\mathcal{G}$ to a 3-valued interpretation of ${\mathrm{\Pi }}_{\mathcal{G}}$ ).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and ${\mathrm{\Pi }}_{\mathcal{G}}$ its corresponding LP. Let $\mathcal{L}=⟨\text{IN}\mathrm{,}\text{OUT}\mathrm{,}\text{UND}⟩$ be a labelling of $\mathcal{G}$ . The 3-valued interpretation associated to $\mathcal{L}$ is denoted ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}$ and defined as follows:

For every $\mathit{a}\in \mathcal{A}$ , if $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ (resp. $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ , $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{undec}$ ) then ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{t}}$ (resp. ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{f}}$ , ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{\text{u}}$ ).

For every $\mathit{e}\in {\mathcal{A}}^{\prime }$ :

• if there is a rule $\mathit{r}:\mathit{e}\leftarrow \mathit{a}$ in ${\mathrm{\Pi }}_{\mathcal{G}}$ s.t. $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{in}$ then e is interpreted as true, i.e., ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{e}\mathrm{)}=\mathbf{\text{t}}$ .

• if e is not interpreted as true and there is a rule $\mathit{r}:\mathit{e}\leftarrow \mathit{a}$ in ${\mathrm{\Pi }}_{\mathcal{G}}$ s.t. $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{undec}$ then e is interpreted as undefined i.e., ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{e}\mathrm{)}=\mathbf{\text{u}}$ .

• Otherwise, i.e., if for every rule $\mathit{r}:\mathit{e}\leftarrow \mathit{a}$ in ${\mathrm{\Pi }}_{\mathcal{G}}$ , it holds that $\mathcal{L}\mathrm{(}\mathit{a}\mathrm{)}=\mathtt{out}$ then e is interpreted as false, i.e., ${\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}\mathrm{(}\mathit{e}\mathrm{)}=\mathbf{\text{f}}$ .

Definition 5.10 (From a 3-valued interpretation of ${\mathrm{\Pi }}_{\mathcal{G}}$ to a labelling of $\mathcal{G}$ ).

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and ${\mathrm{\Pi }}_{\mathcal{G}}$ its corresponding LP. Let $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ be a 3-valued interpretation of ${\mathrm{\Pi }}_{\mathcal{G}}$ . The labelling associated to I is defined by: ${\mathtt{Label}}^{\prime }\mathrm{(}\mathit{I}\mathrm{)}=\mathrm{(}\mathit{T}\cap \mathcal{A}\mathrm{,}\mathit{F}\cap \mathcal{A}\mathrm{,}\mathcal{A}\setminus \mathrm{(}\mathit{T}\cup \mathit{F}\mathrm{)}\mathrm{)}$ .

Now, the following result shows full correspondences between the acceptability semantics of an AFN and the semantics of the corresponding LP.

Theorem 5.11.

Let $\mathcal{G}=⟨\mathcal{A}\mathrm{,}\mathcal{R}\mathrm{,}\mathcal{N}⟩$ be an AFN and ${\mathrm{\Pi }}_{\mathcal{G}}$ be the LP representing $\mathcal{G}$ . If $\mathcal{L}$ is a complete (the grounded, a preferred, a stable, a semi-stable) labelling of $\mathcal{G}$ then ${\mathit{I}}_{\mathcal{L}}={\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}$ is a P-stable (the well-founded, an M-stable, a stable, an L-stable) model of ${\mathrm{\Pi }}_{\mathcal{G}}$ . Inversely, if $\mathit{I}=⟨\mathit{T}\mathrm{,}\mathit{F}⟩$ is a P-stable (the well-founded, an M-stable, a stable, an L-stable) model of ${\mathrm{\Pi }}_{\mathit{G}}$ then ${\mathcal{L}}_{\mathit{I}}={\mathtt{Label}}^{\prime }\mathrm{(}\mathit{I}\mathrm{)}$ is a complete (the grounded, a preferred, a stable, a semi-stable) labelling of $\mathcal{G}$ .

Example 3 (Cont).

Let us take again our four AFNs ${\mathcal{G}}_1\mathrm{,}\dots \mathrm{,}{\mathcal{G}}_4$ . The LP ${\mathrm{\Pi }}_1^{\prime }$ (resp. ${\mathrm{\Pi }}_2^{\prime }$ , ${\mathrm{\Pi }}_3^{\prime }$ , ${\mathrm{\Pi }}_4^{\prime }$ ) is obtained from ${\mathcal{G}}_1$ (resp. ${\mathcal{G}}_2$ , ${\mathcal{G}}_3$ , ${\mathcal{G}}_4$ ) by Definition 5.8. (see Fig. 7).

Fig. 7.

LPs obtained from our four AFNs.

${\mathrm{\Pi }}_1^{\prime }$ has one P-stable model $\mathit{I}=⟨\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}{\mathit{e}}_1\mathrm{,}{\mathit{e}}_2\}⟩$ which is also its unique well-founded, M-stable, stable and L-stable model. ${\mathcal{G}}_1$ has one complete labelling $\mathcal{L}=\mathrm{(}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\varnothing \mathrm{)}$ which is also its unique grounded, preferred, stable and semi-stable labelling. It is easy to check that $\mathit{I}={\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}={\mathtt{Label}}^{\prime }\mathrm{(}\mathit{I}\mathrm{)}$ .

${\mathrm{\Pi }}_2^{\prime }$ has one P-stable model $\mathit{I}=⟨\{\mathit{d}\}\mathrm{,}\{\mathit{c}\}⟩$ which is also its unique well-founded, M-stable and L-stable model but ${\mathrm{\Pi }}_2^{\prime }$ has no stable model. ${\mathcal{G}}_2$ has one complete labelling $\mathcal{L}=\mathrm{(}\{\mathit{d}\}\mathrm{,}\{\mathit{c}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{)}$ which is also its unique grounded, preferred and semi-stable labelling but ${\mathcal{G}}_2$ has no stable labelling. We have: $\mathit{I}={\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}={\mathtt{Label}}^{\prime }\mathrm{(}\mathit{I}\mathrm{)}$ .

${\mathrm{\Pi }}_3^{\prime }$ has three P-stable models ${\mathit{I}}_1=⟨\varnothing \mathrm{,}\varnothing ⟩$ , ${\mathit{I}}_2=⟨\{\mathit{b}\mathrm{,}{\mathit{e}}_1\}\mathrm{,}\{\mathit{a}\}⟩$ and ${\mathit{I}}_3=⟨\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{e}\mathrm{,}{\mathit{e}}_1\}⟩$ . Its well-founded model is ${\mathit{I}}_1$ , its preferred models are ${\mathit{I}}_2$ and ${\mathit{I}}_3$ , its unique L-stable model is ${\mathit{I}}_3$ and it has no stable model. ${\mathcal{G}}_3$ has three complete labellings: ${\mathcal{L}}_1=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ , ${\mathcal{L}}_2=\mathrm{(}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\mathrm{,}\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ and ${\mathcal{L}}_3=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{e}\}\mathrm{,}\{\mathit{f}\mathrm{,}\mathit{g}\}\mathrm{)}$ . Its grounded labelling is ${\mathcal{L}}_1$ , its preferred labellings are ${\mathcal{L}}_2$ and ${\mathcal{L}}_3$ , its unique L-stable labelling is ${\mathcal{L}}_3$ and it has no stable labelling. It is easy to check that ${\mathit{I}}_1={\mathtt{Int}}^{\prime }\mathrm{(}{\mathcal{L}}_1\mathrm{)}$ and ${\mathcal{L}}_1={\mathtt{Label}}^{\prime }\mathrm{(}{\mathit{I}}_1\mathrm{)}$ ; ${\mathit{I}}_2={\mathtt{Int}}^{\prime }\mathrm{(}{\mathcal{L}}_2\mathrm{)}$ and ${\mathcal{L}}_2={\mathtt{Label}}^{\prime }\mathrm{(}{\mathit{I}}_2\mathrm{)}$ ; ${\mathit{I}}_3={\mathtt{Int}}^{\prime }\mathrm{(}{\mathcal{L}}_3\mathrm{)}$ and ${\mathcal{L}}_3={\mathtt{Label}}^{\prime }\mathrm{(}{\mathit{I}}_3\mathrm{)}$ .

${\mathrm{\Pi }}_4^{\prime }$ has one P-stable model $\mathit{I}=⟨\varnothing \mathrm{,}\varnothing ⟩$ which is also its unique well-founded, M-stable and L-stable model but ${\mathrm{\Pi }}_4^{\prime }$ has no stable model. ${\mathcal{G}}_4$ has one complete labelling $\mathcal{L}=\mathrm{(}\varnothing \mathrm{,}\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{)}$ which is also its unique grounded, preferred and semi-stable labelling but ${\mathcal{G}}_4$ has no stable labelling. We have: $\mathit{I}={\mathtt{Int}}^{\prime }\mathrm{(}\mathcal{L}\mathrm{)}$ and $\mathcal{L}={\mathtt{Label}}^{\prime }\mathrm{(}\mathit{I}\mathrm{)}$ .

6. Related work and perspectives

An early work of bipolarity in abstract argumentation is that about bipolar argumentation frameworks (BAFs) [38,40]. In this work, the meaning of support is left unspecified to keep a high abstraction level. However, the drawback of this proposal is the possibility to find counter-intuitive results in some situations.

The work presented in [19] started from a criticism of BAFs on two points, namely, the loss of admissibility in the extensions obtained from the meta-model using coalitions [40]. The proposed approach develops the so-called deductive support and introduces mediated attacks instead of indirect attacks. The authors show that the admissibility of extensions is then restored. As remarked in [71] then later in [41,45], it turns out that the deductive support is nothing but the inverse of the necessity relation in the case where the latter is binary (relating couples of single arguments). Thus, if we limit ourselves to a binary support relation, instead of imposing the use of only one type of support relation, one can start from a system where the two types are freely expressed and then reduce in a preliminary stage all the relations to one type. Note that in this case, all the results of our paper hold for a deductive support relation D by simply using closure under D instead of closure under ${\mathit{N}}^{-1}$ . The subsequent development in [19] focuses on the definition of a meta-argumentation model to handle supports and introduce defeasible supports. In our work we propose a similar approach of meta-argumentation for AFNs. Furthermore, we address the question of generalizing the existing Dung acceptability semantics in presence of the necessity relation. Another difference is that our framework uses a more general setting where single arguments may be supported by sets of arguments. Finally our approach takes benefit of the necessity relation in establishing relationships between AFNs and LPs.

Another approach that shares some features with ours is the evidence based argumentation, first introduced in [72]. This approach considers that only arguments that have some evidential support can attack other arguments. The evidential support of an argument comes either directly from the environment (prima facie arguments) or from a chain of supports that originates in such prima facie arguments (standard arguments). A similar idea is present in our work. Indeed, to ensure admissibility of a set, we must guarantee just the response to attacks coming from arguments that are N-Cycle-Free, i.e., those that have no need for a support or that are ultimately supported by arguments that have no need for a support. Thus, AFNs may be seen as a possible concretization of the notion of evidence where all arguments are by default supported unless they are taken in a set which is not N-Cycle-Free. The reader may refer to [41,45,78] for a more detailed comparison between the necessity, the deductive and the evidential supports in the context where only binary support relations are used.

Several recent works generalized Dung AFs to represent recursive attacks (attacks targeting attacks) [14,34,37]. Likewise, bipolar frameworks that represent recursive attacks and support (see e.g. [35,36,42,46,62]) have also be extensively studied. Notice that [46,62] uses necessity support relation while [36,42] use evidential support.

The work developed in [20,22,75] introduced abstract dialectical frameworks (ADF), a powerful generalization of Dung’s AFs that formalizes the idea of proof standards, widely studied in legal reasoning domain. This idea is captured in ADFs by linking each argument to a set of arguments (its parents) and introducing the notion of acceptance conditions that determine whether an argument is accepted or not according to the acceptance status of its parents. However, a sub-class of ADFs called bipolar ADFs (BADFs) is identified, where the relation between an argument and a parent plays always one role: either an attack or a support. A main difference between our work and ADFs lies in the method used to generalize stable and admissible semantics. ADFs adapt techniques from logic programming, namely G/L reduct, to avoid necessity cycles. In our work, thanks to the notions of coherence and strong coherence used instead of conflict-freeness, we keep our definitions similar to that in Dung’s original AFs. Another point is that in the method we use to encode an LP as a AFN, each rule is represented by an argument which gives an homogeneous view of the meaning of an argument. In [22], a similar homogenous representation using atoms as arguments is proposed but as pointed out in the paper, it leads in general to an ADF which may not be bipolar. To obtain a BADF, one must introduce new arguments designating rules. The resulting representation is then heterogeneous in the sense that arguments may refer to rules or to atoms. Finally, the opposite question, i.e., the representation of ADFs as LPs is not explicitly considered. However, subsequent work has been done to study ADFs in several other directions. We can cite [20] in which the semantics of ADFs are inspired by approximation fixpoint theory, [76] which proposes a probabilistic version of ADFs, [54] which shows how to represent an ADF with only attack relations and [48] which investigates sub-classes of ADFs.

A main notion in argumentation approaches with structured arguments, is that of sub-argument [17,57,66,81,87]. A sub-argument provides an intermediary conclusion to its super-argument. From this viewpoint, sub-arguments may be seen as supporting their super-arguments. The work proposed in [66] introduces the AFs with sub-arguments (AFS). An AFS extends a Dung AF with two binary relations on arguments: a sub-argument relation and a preference relation. To capture the requirements of the sub-argument relation, the authors introduce the so-called conflict inheritance constraint on the attack relation. It says that if a attacks b then any super-argument of a attacks any super-argument of b. In [45], the authors show that the kind of support provided by sub-arguments has the meaning of necessity. They point out that a rational constraint which relates arguments and sub-arguments is the compositionality principle (see [82]). It says that an argument cannot be accepted unless all its sub-arguments are accepted, i.e., (i) if an argument is accepted then all its sub-arguments are accepted and (ii) if an argument is not accepted then all its super-arguments are not accepted. It turns out that this captures exactly the meaning of (a binary) necessity relation in an AFN: if we have $\mathit{a}\mathcal{N}\mathit{b}$ then if b is accepted then necessarily a is accepted and if a is not accepted then b is not accepted. In the same spirit, the work of [80] points out the strong correspondence between the necessity relation in AFNs and the sub-argument relation in the ASPIC+ system.

The work in [44] introduces the backing-undercutting argumentation framework (BUAF) which extends Dung AFs by incorporating a special binary support relation (backing relation) and a partial order representing a preference relation among arguments. The support relation is intended to represent the backing link considered in Toulmin’s model of an argument (see [88,90] for more details about Toulmin’s model).8 ⁸

Roughly speaking, Toulmin’s scheme of an argument is constituted of five elements. A data (D) which is the ground which we produce as a support. A claim (C) which is a conclusion based on the data. A warrant (W) which is a rule-like statement that justifies the conclusion of (C) from (D). A qualifier (Q) which reflects a degree of force that data confers on the claim in virtue of the warrant. A backing (B) which explains why the warrant holds and thus brings a support for it. Finally, a rebuttal (R) which represents particular contexts where the claim is challenged.

Three kinds of attack relations are distinguished: the rebutting, the undercutting and the undermining attacks. Only the undercutting attack can interact with the backing relation since both of them involve the warrant. As in many other approaches to bipolarity in argumentation, the objective in this approach is to produce new indirect attacks that result from the interaction of direct attacks and supports. In this approach, the final negative interactions are called defeats. They take into account the input attack, the backing as well as the preference relations. Let us briefly present the three kinds of defeats present in this approach. The first one is the primary defeat: a primarily defeats c in one of the three following situation: if a rebuts or undermines c and c is not strictly preferred to a; if a undercuts c and c has no backing argument or if a undercuts c, c has a backing argument b but b is not strictly preferred to a. The second kind of defeat is the implicit defeat: a implicitly defeats b in two possible situations: if b is a backing for c, a undercuts c and b is not strictly preferred to a; or if a is a backing for c, b undercuts c and neither b is strictly preferred to a nor a is strictly preferred to b. The last kind of defeat is the indirect defeat which covers the other kinds of defeats (primary and implicit defeats) and the new defeats that result recursively by chaining backing arguments. Once all the indirect defeats are computed, Dung acceptability semantics are used to evaluate arguments. It has been shown in [45] that some aspects of the backing relation correspond to some aspects of the necessity relation but there is no full correspondence between the two relations.

Constrained AFs [47] extend Dung AFs with propositional constraints on arguments. We notice that AFNs cannot be reduced to constrained AFs where $\mathit{E}\mathit{N}\mathit{b}$ is replaced by the implication $\mathit{b}\Rightarrow {\bigvee }_{\mathit{a}\in \mathit{E}}$ . To show this, recall that a stable extension of a constrained AF is a stable extension of the corresponding AF that verifies the additional constraints. This does not hold for AFNs. For instance, the AFN $⟨\mathit{A}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\mathit{R}=\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\mathit{N}=\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\}⟩$ has one stable extension: $\{\mathit{a}\}$ , but the constrained AF $⟨\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\mathit{C}=\mathit{c}\Rightarrow \mathit{b}⟩$ has no stable extension (the only stable extension of $⟨\mathit{A}\mathrm{,}\mathit{R}⟩$ is $\{\mathit{a}\mathrm{,}\mathit{c}\}$ which does not verify the constraint C).

Linking abstract argumentation to logic programming is an interesting research topic. It goes back to the seminal work of Dung [53]. Some works in this domain have considered the issue of using logic programming, especially answer set programming, to compute the extensions of AFs under different semantics (see e.g. [55,56,85]). The objective of these works differs from ours.

In [1], the authors focuses on the equivalence between Abstract Dialectical Frameworks and logic programs under 3-valued semantics. More precisely this work focuses on a fragment of ADFs, called Attacking dialectical frameworks ( ${\mathrm{ADF}}^{+}$ s) and provides a translation from normal LPs to ${\mathrm{ADF}}^{+}$ such that partial stable, well-founded, regular and stable models of normal LPs are in a one to one correspondence with complete, grounded, preferred and stable extensions of the corresponding ${\mathrm{ADF}}^{+}$ s, respectively.

Another work that is closer to ours is that presented in [29,30]. This work establishes the links between 3-valued LPs and Dung AFs. An LP is represented by a Dung AF where an argument is obtained by chaining a subset of rules of the LP (as in rule-based argumentation systems [7,68]). An argument involves a set of rules, a conclusion (the head of the last used rule), a set of vulnerabilities (the atoms appearing in the negative bodies of the rules involved in the argument) and a set of sub-arguments. Then, an attack relation is defined from an argument a to an argument b if the conclusion of a belongs to the set of vulnerabilities of b. The process results in a Dung AF. The authors show then a one-to-one correspondence between the well-founded (resp. P-stable, M-stable, stable) models of the LP and the grounded (resp. complete, preferred, stable) extensions of the corresponding AF. Only L-stable semantics of LPs and semi-stable semantics are not in full correspondence. Then, it has been shown that when representing an AF as an LP, the picture is complete, i.e., all the correspondences hold including that semi-stable extensions and L-stable model. Notice that [29] generalizes the approach to cope with ideal and eager semantics. Our work may be seen as a generalization of this approach to bipolar setting using the necessity support. More precisely, in representing an LP as an abstract AFN, our work takes benefit from the positive interaction (necessity links) between the rules of an LP to propose a new simpler instantiation method where each rule is represented by an argument. The use of an additional necessity support relation in the argumentation models avoids the construction of complex arguments. In the opposite direction our work allows one to represent as an LP a wider range of argumentation frameworks since Dung AFs are a strict subset of AFNs.

In the same spirit, the work by Alfano et al. [2,3] presents how to translate different kinds of extensions of dung AFs (called AF-based frameworks) into logic programs and shows how the acceptability semantics of such AF-based frameworks are related to particular cases of partial stable models of the corresponding LPs. The considered AF-based frameworks include: Original Dung AFs [53]; bipolar AFs (BAF), namely AFs with necessity support (AFN) [71] and AFs with deductive support (AFD) [19,91]; recursive AFs (Rec-AF) namely, AFs with recursive attack (AFRA) [14] and recursive AFs (RAF) [37] and recursive bipolar AFs (Rec-BAF) namely, attack-support AFs (ASAF) [62], recursive AFs with necessities (RAFN) [35], AFs with recursive attack and deductive support (AFRAD) [3] and recursive AFs with deductive support (RAFD) [3]. Our work differs from that by Alfano et al. [2,3] in two main respects: First, the work in [2,3] considers only the restricted version of AFNs where the necessary support relation is binary and acyclic while our proposal considers a more general framework where the support relation may relate a set of arguments to a single one and no restriction is made about its cyclicality. The second issue is that the work in [2,3] considers only the representation of AF-based frameworks as LPs and does not study the opposite direction (representing an LP as an AF-based framework). In our work, we consider the translation in the two directions. This shows among other things that among the different existing AF-based frameworks, AFN is suitable to represent any normal LP in a direct and simple way.

For a more comprehensive comparative study of the above approaches of support in argumentation as well as some other approaches having some links with the topic,9 ⁹

namely, [90] considers a reconstruction of Toulmin’s ideas using DEFLOG and [43] studies an extension of DELP, where Toulmin’s form of support between backings and warrants are considered.

the reader is referred to [45]. It is worth noticing that most of the current bipolar argumentation approaches use binary support relations and turn eventually the bipolar framework to a Dung AF in order to evaluate arguments. Our work goes a step further: it uses a generalized necessity relation that involves sets of arguments as supports, allows one to evaluate arguments directly in the new setting, generalizes the labelling characterization and algorithms to the new context and relates AFNs to LPs.

As stated above, some works (e.g.. [41]) have started to look for similarities and differences between the different approaches of support in abstract argumentation. An interesting future work would be to propose a unified framework able to take into account different kinds of supports and to define a general approach for acceptability semantics to such a framework in the simple and high-order case (recursive attacks and supports). As pointed out in [80], in argumentation approaches with structured arguments, the sub-argument relation is a possible instantiation of the necessity relation. This idea opens the way to a future work on a more general question about how to instantiate different kinds of supports present in the literature and then to propose general postulates that describe their expected behavior as it is done for the attack relation (see e.g.. [61]).

As regards the links with logic programming, we believe that the strong relationship established between AFNs and LPs is a key tool that will enable us to bring advanced results in logic programming into abstract argumentation theory and vice versa. For instance, we are interested on works about equilibrium logics that gave logical foundation to stable models [74] and later partial equilibrium logics that generalize the idea to capture well-founded models [23–25]. We believe that variants of partial equilibrium logics may capture other 3-valued models of LPs and we want to exploit the strong links between AFNs and 3-valued semantics to give a logical foundation for Dung AFs, AFNs and possibly other approaches of bipolar argumentation in terms of partial equilibrium logics. In the same spirit, the work in [52] captures the notion of stable model with the notion of minimally specific model of generalized possibilistic logic [51] which is an extension of possibilistic logic (see e.g. [49,50]) that enables one to reason on epistemic states instead of merely constrain them. Again, the strong links between AFNs and LPs may be exploited to capture acceptability semantics of Dung AFs and AFNs in the generalized possibilistic logic framework.