Argumentation frameworks with necessities and their relationship with logic programs

Nouioua, Farid; Boutouhami, Sara

doi:10.3233/AAC-210028

Argumentation frameworks with necessities and their relationship with logic programs

Article type: Research Article

Authors: Nouioua, Farid^{a; b; *} | Boutouhami, Sara^a

Affiliations: [a] Computer Science Department, University of Bordj Bou Arreridj, Algeria | [b] LIS UMR-CNRS 7020, University of Aix-Marseille, France

Correspondence: [*] Corresponding author. E-mail: farid.nouioua@gmail.com.

Keywords: Abstract argumentation, bipolarity, acceptability semantics, linking argumentation and logic programming

DOI: 10.3233/AAC-210028

Journal: Argument & Computation, vol. 14, no. 1, pp. 17-58, 2023

Published: 22 February 2023

Get PDF

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:

(A): Only the basic notions of automata theory have been presented to students. Thus, the exam of this unit cannot be taken shortly.
(B): Normally, all the exams are taken during the same week and the exams of all the other teaching units are expected to be soon.
(C): 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

Definition 2.1(Argumentation framework).

A Dung AF is a pair H=⟨A,R⟩ where A is a set of arguments and R⊆A×A is a binary attack relation.

Throughout the paper, we use the infix aRb to denote the attack (a,b)∈R. Moreover, for E⊆A and a∈A, we abuse notation and write aRE (resp. ERa) if there is b∈E such that aRb (resp. bRa). For E,E′⊆A, we similarly write ERE′ if there is a∈E and b∈E′ s.t. aRb. Finally we denote by E+ the set of arguments attacked by E, i.e., E+={a∈A∣ERa}.

Intuitively, aRb 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

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

Let H=⟨A,R⟩ be an AF and E⊆A. E is conflict-free iff ∄a,b∈E s.t. aRb; E defends an argument a iff ∀b∈A, if bRa, then ERb; the characteristic function FH is defined by: FH:2A→2A s.t. for E⊆A, FH(E)={a∈A∣E defends a}; E is admissible iff E is conflict-free and ∀a∈E, E defends a.

The main acceptability semantics1 1 of Dung AFs are defined as follows:

Definition 2.3

Definition 2.3(Acceptability semantics).

Let H=⟨A,R⟩ be an AF and E⊆A. E is a complete extension iff it is admissible and contains all the elements it defends (i.e., FH(E)=E); E is the grounded extension iff it is the ⊆-minimal complete extension; E is a preferred extension iff it is a ⊆-maximal complete extension; E is a stable extension iff it is conflict-free and attacks all the arguments outside it (i.e., E+=A∖E); E is a semi-stable extension iff it is a complete extension s.t. E∪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 H=⟨A,R⟩ depicted in Fig. 2.

Fig. 2.

A Dung AF H=⟨A,R⟩.

The admissible sets of H are: ∅, {a}, {b} and {b,d}. All of them are complete extensions except {b}. The grounded extension of H is ∅. H has two preferred extensions: {a} and {b,d}. Only {b,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:

a0←a1,…,am,not am+1,…,not anwith 0⩽m⩽n

ai (0⩽ai⩽n) are atoms. We read such a rule as follows: if a1…am are true and none of the atoms am+1…an is true then deduce that a0 is true. For a rule r, we use the following notations: Head(r)=a0, Body+(r)={a1,…,am} and Body−(r)={am+1,…,an}. More generally, we write: Head(Π)={Head(r)|r∈Π}, Body+(Π)=⋃r∈ΠBody+(r) and Body−(Π)=⋃r∈ΠBody−(r). The Herbrand base of an LP Π denoted HBΠ is the set of all atoms present in Π. An LP Π is said to be basic (or positive) if Body−(Π)=∅.

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

Definition 2.4(3-valued interpretation).

A 3-valued interpretation I is a pair I=⟨T,F⟩ where T, F are disjoint subsets of 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 {t,f,u} s.t.: a∈T iff I(a)=t, a∈F iff I(a)=f and a∈HB∖(T∪F) iff I(a)=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 {f,t,u} s.t. f⩽u⩽t and ∀v∈{f,t,u}, v⩽v. The extension Iˆ of a 3-valued interpretation I is defined as follows: Iˆ(a)=I(a) if a is an atom; Iˆ(not a)=f (resp. t, u) if I(a)=t (resp. f, u); Iˆ(A1,…,An)=min(Iˆ(A1),…,Iˆ(An)) where each Ai is either an atom or an expression not ai with ai an atom. Finally, for any rule of the form r:a0←a1,…,am,not am+1,…,not an, we have: Iˆ(r)=t if Iˆ(a1,…,am,not am+1,…,not an)⩽Iˆ(a0) and Iˆ(r)=f otherwise.

Definition 2.5

Definition 2.5(Model).

A 3-valued interpretation I is a model of an LP Π iff ∀r∈Π, Iˆ(r)=t.

Given an LP Π, the operator Ψ takes a 3-valued interpretation I and gives its “immediate consequences” as follows. For every atom a∈HB:

Ψ(I)(a)=t iff there is a rule a←a1,…,am,not am+1,…,not an in Π s.t. I(ai)=t for all i s.t. 1⩽i⩽m and I(aj)=f for all j s.t. m+1⩽j⩽n.
Ψ(I)(a)=u iff Ψ(I)(a)≠t and there is a rule a←a1,…,am,not am+1,…,not an in Π s.t. I(ai)≠f for all i s.t. 1⩽i⩽m and I(aj)≠t for all j s.t. m+1⩽j⩽n.
Ψ(I)(a)=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: ⟨T,F⟩⪯⟨T′,F′⟩ iff T⊆T′ and F′⊆F. Thus, intuitively a model I1 is smaller than a model I2 if I1 contains “less truth than” I2. Moreover, this least model is exactly the least fixpoint of the operator Ψ defined above2 2 and can be obtained by successive application of the operator Ψ starting from the interpretation I0=⟨∅,HB⟩.

Definition 2.6

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 ΠI obtained by replacing in every rule of Π, every expression not a s.t. I(a)=f (resp. I(a)=t, I(a)=u) by the constant t (resp. f, u). Let J be the unique least model of ΠI, we define the operator Γ by Γ(I)=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 3

Definition 2.7

Definition 2.7(Different kinds of models).

Let Π be an LP and I=⟨T,F⟩ be a 3-valued interpretation of Π. Then:

I is a P-stable model of Π iff Γ(I)=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. T∪F=HB (no atom is undefined).
I is an L-stable model of Π iff I is a P-stable model having the ⊆-maximal set T∪F among all P-stable models of Π.

Example 2.

Let us consider the LPs Π1, Π2, Π3 and Π4 (see Fig. 3):

Fig. 3.

Examples of LPs.

Π1 has one P-stable model I=⟨T={s},F={p,q}⟩. Indeed the extended G/L reduct of Π1 w.r.t. I is Π1I={p←q;q←p;s←t}. Starting from I0=⟨∅,{p,q,s}⟩, we have Ψ(I0)=I, Ψ(I)=I. Thus, Γ(I)=I which means that I is a P-stable model of Π1. It is easy to check that for all 3-valued interpretation I′≠I of Π1, Γ(I′)≠I′, i.e., I is the unique P-stable model of Π1 which is also its unique well-founded, M-stable and L-stable model. Since HBΠ1={p,q,s}=T∪F, I is the unique stable model of Π1.

Following the same method, one can check that Π2 has one P-stable model I=⟨T={s},F=∅⟩ which is also its unique well-founded, M-stable and L-stable model. Since HBΠ2={p,q,s}≠T∪F, I is not a stable model of Π2.

Π3 has three P-stable models: I1=⟨T1=∅,F1=∅⟩, I2=⟨T2={q},F2={p}⟩ and I3=⟨T3={p,y},F3={q,s,x}⟩. The well-founded model of Π3 is I1. I2 and I3 are the two M-stable models of Π3 and only I3 is an L-stable model of Π3. Since HBΠ3={p,q,s,y,x,v,w}≠Ti∪Fi (for i∈{1,2,3}), Π3 has no stable model.

Π4 has one P-stable model I=⟨T=∅,F=∅⟩ which is also its unique well-founded, M-stable and L-stable model. Since HBΠ4={p,q}≠T∪F, Π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 N that relates sets of arguments to single arguments.

Definition 3.1

Definition 3.1(Argumentation framework with necessities).

An AFN is a tuple G=⟨A,R,N⟩ where A is a set of arguments, R⊆A×A is a binary attack relation and N⊆2A×A is a necessity relation.

The attack relation R is interpreted as usual: aRb means that the acceptance of b requires the non acceptance of a. The new relation N is interpreted analogously but in a positive manner as follows: ENb means that the acceptance of b requires the acceptance of at least an argument of E. When all the necessary sets are singletons, N becomes a binary relation like 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 4

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 N−1. Intuitively, a set of arguments is closed under N−1 if it satisfies the necessities of each of its arguments.

Definition 3.2

Definition 3.2(closure under N−1).

Let G=⟨A,R,N⟩ be an AFN and E⊆A. E is closed under N−1 iff for each argument a∈E, if ENa for some E⊆A, then E∩E≠∅.

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

Definition 3.3

Definition 3.3(N-cycle freeness).

Let G=⟨A,R,N⟩ be an AFN, E⊆A and a∈E. We say that a is N-Cycle-Free in E iff for all E⊆A s.t. ENa, we have either E∩E=∅ or there is b∈E∩E s.t. b is N-Cycle-Free in E. E is N-Cycle-Free iff every a∈E is N-Cycle-Free in E.

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

Definition 3.4

Definition 3.4(Coherence).

Let G=⟨A,R,N⟩ be an AFN and E⊆A. E is coherent iff it is closed under N−1 and N-Cycle-Free.

Intuitively, in a coherent set 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 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

Definition 3.5(Powerful argument).

Let G=⟨A,R,N⟩ be an AFN and E⊆A. An argument a∈A is powerful in E iff a∈E and there is a sequence a0,…,ak of elements of E s.t. ak=a; there is no E⊆A s.t. ENa0 and for 1⩽i⩽k: for all E⊆A, if ENai, then E∩{a0,…,ai−1}≠∅.

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

Proposition 3.6.

Let G=⟨A,R,N⟩ be an AFN and E⊆A. E is coherent iff each a∈E is powerful in E.

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

Proposition 3.7.

Let G=⟨A,R,N⟩ be an AFN, E⊆A and a∈E.

a is not powerful in E iff there is no coherent subset C of E s.t. a∈C

iff ∃E⊆A s.t. ENa and ∀E⊆A s.t. ENa, ∀b∈E∩E, b is not powerful in 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

Definition 3.8(Strong coherence).

Let G=⟨A,R,N⟩ be an AFN and E⊆A. E is strongly coherent iff it is coherent and conflict-free.

Example 3.

Let us consider the four AFNs Gi=⟨Ai,Ri,Ni⟩ (1⩽i⩽4) depicted in Fig. 4 where continuous (resp. dashed) arrows represent attacks (resp. necessities).

Fig. 4.

Four AFNs: (a) G1, (b) G2, (c) G3, (d) G4.

For G1, the only coherent sets are ∅ and {c}. In particular the set {a,b} is closed under N−1 but not N-Cycle-Free, hence {a,b} is not coherent. The coherent sets of G2 are those sets of arguments that contain b or c whenever they contain a. The coherent sets of G3 are those sets of arguments that contain b whenever they contain c and contain g whenever they contain f. The coherent sets of G4 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 {b,c}. Indeed, the set {b,c} is closed under N−1 but not N-Cycle-Free, whereas the sets {b}, {c}, {a,b}, {c,d} are N-Cycle-Free but not closed under N−1 and hence they are not coherent. All the other sets of arguments not including {b,c} are coherent.

For each AFN Gi, 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

Definition 3.9(Defense in AFNs).

Let G=⟨A,R,N⟩ be an AFN, E⊆A and a∈A. We say that E defends a iff E∪{a} is coherent and for all b∈A, if bRa then for every coherent subset C⊆A s.t. b∈C, ERC.

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

Definition 3.10(Characteristic function of AFNs).

Let G=⟨A,R,N⟩ be an AFN and E⊆A. The characteristic function of G is defined by FG:2A→2A with FG(E)={a∣E defends 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

Definition 3.11(Deactivated arguments).

Let G=⟨A,R,N⟩ be an AFN and E⊆A be a strongly coherent subset of arguments. The set of arguments deactivated by E is Ed={a∣if C⊆A is a coherent subset s.t. a∈C then ERC}.

The set Ed includes, in addition to arguments deactivated because of a direct attack from E against them, the arguments that are not powerful in A6 6 as well as the arguments that 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

Definition 3.12(Acceptability semantics for AFNs).

Let G=⟨A,R,N⟩ be an AFN and E⊆A.

E is an admissible set iff it is strongly coherent and ∀a∈E, E defends a.
E is a complete extension iff it is admissible and ∀a∈A, if E defends a then a∈E.
E is the grounded extension iff E is the least fixpoint of FG. It is obtained by the repetitive application of FG starting from ∅ until a fixpoint is reached.
E is a preferred extension iff E is a maximal (w.r.t. set inclusion) admissible set.
E is a stable extension of G iff it is a strongly coherent subset of A s.t. for all a∈A∖E, a is deactivated by E.
E is a semi-stable extension iff it is a complete extension and E∪Ed 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 G=⟨A,R,N⟩ be an AFN and E⊆A be a strongly coherent set.

(1) E is an admissible set iff E⊆FG(E) (characterization of admissible sets using the characteristic function FG).
(2) E is a complete extension iff E=FG(E) (complete extensions are exactly the fixpoints of the characteristic function FG).
(3) E is the grounded extension of G iff it is the least (w.r.t. set inclusion) complete extension of G.
(4) There is at least one preferred extension for G; every preferred extension is a complete extension but not vice versa; E is a preferred extension iff it is a maximal (w.r.t. set inclusion) complete extension.
(5) If E is a stable extension then E is a semi-stable extension but not vice versa; if E is a semi-stable extension, then E is a preferred extension but not vice versa.
(6) If E is a stable extension, then E is a preferred extension but not vice versa; there may be zero, one or several stable extensions for G.

Example 3

Example 3(Cont).

We continue with the AFNs G1,…,G4.

G1 has two admissible sets: ∅ and {c}. Indeed, {c} defends itself since the only attacker of c is b and there is no coherent set containing b. We have: FG1(∅)={c}, FG1({c})={c}. Thus {c} is the unique complete extension of G1 which is also its unique grounded, preferred and semi-stable extension. Moreover, {c} is also the unique stable extension of G1 since the set of arguments deactivated by {c} is {c}d={a,b}=A∖{c} (Indeed, a and b are not powerful in A).

G2 has two admissible sets: ∅ and {d}. {d} defends itself since d has no attackers. No other strongly coherent set of G2 is admissible. For instance, {b,d} is not admissible because a attacks b and {a,b} is a coherent set containing a but not attacked by {b,d}. We have: FG2(∅)={d}, FG2({d})={d}. Thus {d} is the unique complete extension of G2 which is also its unique grounded, preferred and semi-stable extension. However {d} is not a stable extension since {d}d={c}≠A∖{d}.

The admissible sets of G3 are: ∅, {a}, {b} and {a,d}. Let us take for instance {a,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: FG3(∅)=∅, FG3({a})={a,d}, FG3({b})={b}, FG3({a,d})={a,d}. It follows that G3 has three complete extensions: ∅, {b} and {a,d}. The grounded extension of G3 is ∅. G3 has two preferred extensions that are {b} and {a,d}. G3 has no stable extension since {b}d={a}≠A∖{b} and {a,d}d={b,c,e}≠A∖{a,d}. We have: {b}d∪{b}={a,b} and {a,d}d∪{a,d}={a,b,c,d,e}. Since {b}d∪{b}⊂{a,d}d∪{a,d}, G3 admits {a,d} as a unique semi-stable extension.

The only admissible set of G4 is ∅. Namely, the strongly coherent set {a} is not admissible because c attacks a and {a,c} is a coherent set containing c but not attacked by {a}. A similar reasoning is valid for the non admissibility of {d}. We have: FG4(∅)=∅. Thus, ∅ is the only complete extension of G4 which is also its unique grounded, preferred and semi-stable extension. G4 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

Definition 3.14(Labelling).

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

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 out and each set E necessary for a contains at least an argument labelled in, it would not be justified that a be labelled out. This leads to the notion of legal labelling:

Definition 3.15

Definition 3.15(Legal labelling).

Let G=⟨A,R,N⟩ be an AFN, L be a labelling and a be an argument.

a is legally in iff a is labelled in and the two following conditions hold:
- (1) ∀b∈A, if bRa then b∈out(L) (all attackers of a are labelled out) and
- (2) ∀E⊆A, if ENa then E∩in(L)≠∅ (at least one argument from each necessary set for a is labelled in).
a is legally out iff a is labelled out and at least one of the two following conditions holds:
- (1) either ∃b∈A s.t. bRa and b∈in(L) (at least one attacker of a is labelled in) or
- (2) ∃E⊆A, s.t. ENa and E⊆out(L) (all the arguments of a necessary set for a are labelled out).
a is legally undec iff a is labelled undec and the following conditions hold:
- (1) ∀b∈A, if bRa then b∉in(L) (no attacker of a is labelled in) and
- (2) ∀E⊆A, if ENa then E⊈out(L) (not all the arguments of any necessary set for a are labelled out) and
- (3) either ∃b∈A s.t. bRa and b∉out(L) or ∃E⊆A s.t. ENa and E∩in(L)=∅ (either at least one attacker of a is not labelled out or at least one necessary set for a does not contain any argument that is labelled in).

Notice that for N=∅, 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 A does not belong to any extension and must be labelled out and since each extension E under any semantics must be coherent, the set of 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

Definition 3.16(Safe labelling).

We say that a labelling L is safe iff the set in(L) is coherent and for each a∈A: if a is not powerful in A then a∈out(L).

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

Definition 3.17(Different kinds of labellings).

A labelling L is:

admissible iff L is safe and without arguments that are illegally in and without arguments that are illegally out;
complete iff L is admissible and without arguments that are illegally undec;
grounded iff L is complete and in(L) is ⊆-minimal;
preferred iff L is complete and in(L) is ⊆-maximal;
stable iff L is complete and undec(L)=∅ and
semi-stable iff L is complete and undec(L) 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 in or out must be legal but tolerate the illegality of arguments that are labelled undec. However, complete labellings require the legality of all arguments: Every argument which is labeled in (resp. out, undec) must be legally in (resp. out, 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 N=∅), any set of arguments is safe. In this case, we obtain exactly the classical definitions for legally in, out and 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 G=⟨A,R,N⟩ be an AFN, E⊆A and L be a labelling of G.

If E is an admissible set of G then the labelling L=(E,Ed,A∖(E∪Ed)) is an admissible labelling of G. Inversely, if L is an admissible labelling of G then E=in(L) is an admissible set of G and out(L)⊆Ed.
If E is a complete (resp. the grounded, a preferred, a stable, a semi-stable) extension of G then the labelling L=(E,Ed,A∖(E∪Ed)) is a complete (resp. the grounded, a preferred, a stable, a semi-stable extension) labelling of G. Inversely, if L is a complete (resp. the grounded, a preferred, a stable, a semi-stable extension) labelling of G then E=in(L) is a complete (resp. the grounded, a preferred, a stable, a semi-stable) extension of G and out(L)=Ed.

Example 3

Example 3(Cont).

Let us consider again our four AFNs: G1…G4.

Consider the labellings: L1=({c},{b},{a}), L2=(∅,∅,{a,b,c}), L3=(∅,{a,b},{c}), and L4=({c},{a,b},∅) for G1. In L1 c is legally in because L1(b)=out but b is illegally out. Moreover, L1 is not safe because a is not powerful in A but a∉out(L1). Thus, L1 is not admissible. L2 is not safe for the same reason and thus, is not admissible. In L3, a and b are legally out but c is illegally undec. L3 is admissible but not complete. In L4 c is legally in and a and b are legally out. Moreover, L4 is safe and thus it is admissible and complete (no argument is illegally undec). In summary, L3 and L4 are the admissible labellings of G1 and L4 is its unique complete labelling which is also its unique grounded and preferred labelling. Moreover, since undec(L4)=∅, L4 is also the unique stable and semi-stable labelling of G1.

L1=(∅,∅,{a,b,c,d}) and L2=({d},{c},{a,b}) are the admissible labellings of G2. L2 is the only complete labelling of G2 (d is illegally undec in L1) which is also its unique grounded, preferred and semi-stable labelling. However, since undec(L2)≠∅, L4 is not stable.

L1=(∅,∅,{a,b,c,d,e,f,g}), L2=({a},{b,c},{d,e,f,g}), L3=({b},{a},{c,d,e,f,g}) and L4=({a,d},{b,c,e},{f,g}) are the admissible labellings of G3. Among them, only L2 is not complete (d is illegally undec in L2). The grounded labelling is L1, the preferred labellings are L3 and L4. No complete labelling has an empty set of undec arguments, thus no labelling is stable. The only semi-stable stable labelling (which minimizes undec) is L4.

G4 admits L=(∅,∅,{a,b,c,d}) as the unique admissible, complete, grounded, preferred and semi-stable labelling. G4 has no stable labelling.

For each of the previous AFNs, L is an s-labelling (s∈{admissible,complete,grounded,preferred,stable,semi-stable}) if and only if in(L) 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 H=⟨A,R⟩ be a Dung AF. We define the AFN GH by GH=⟨A,R,∅⟩. Let E⊆A. E is an admissible set (resp. complete, grounded, preferred, stable, semi-stable extension) of H iff E is an admissible set (resp. complete, grounded preferred, stable, semi-stable extension) of GH.

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

Given an AFN G=⟨A,R,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 G. It has been shown in [71] that the answer is positive when the necessity relation is binary (for AFNs where if ENa 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 G2 of Example 3 and let us suppose that F=⟨A,R′⟩ is an AF encoding the same information as G2. It is clear that (a,b), (d,c) are in R′. The AF ⟨A,{(a,b),(d,c)}⟩ 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 (x,y∈A) is not present directly or indirectly in G2. 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 A1 and A2. 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

Definition 4.2(Meta-argument).

Let G=⟨A,R,N⟩ be an AFN and a∈A. A meta-argument associated to a is a minimal (w.r.t. set inclusion) coherent set C⊆A containing a (no subset of C containing a is coherent).

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

Definition 4.3

Definition 4.3(Meta AF representing an AFN).

Let G=⟨A,R,N⟩ be an AFN. The Dung AF representing G is HG=⟨A′,R′⟩ where: A′ is the set of all meta-arguments associated to all arguments in A and for C1,C2∈A′, C1R′C2 iff there is a∈C1 and there is b∈C2 s.t. aRb.

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

Proposition 4.4.

Let G=⟨A,R,N⟩ be an AFN, HG=⟨A′,R′⟩ be its corresponding meta AF and a∈A. If a is not powerful in A, then ∄C∈A′ s.t. a∈C.

Example 3

Example 3(Cont).

Each AFN Gi=⟨Ai,Ri,Ni⟩ is translated into HGi=⟨Ai′,Ri′⟩ for i∈{1,2,3,4}.

For HG1, the arguments a and b are not powerful in A and hence they do not give rise to any meta-argument. The argument c gives rise to the unique meta-argument c′={c}. Accordingly, A1′={c′} and R1′=∅ (see Fig. 6-(a)).

For HG2, the argument a gives rise to two meta-arguments: a1′={a,b} and a2′={a,c}. b (resp. c, d) gives rise to the unique meta-argument b′={b} (resp. c′={c}, d′={d}). Thus, A2′={a1′,a2′,b′,c′,d′}. R2′ is depicted in Fig. 6-(b).

For HG3, the argument c (resp. f) gives rise to the meta-arguments: c′={b,c} (resp. f′={f,g}). The argument a (resp. b, d, e, g) gives rise to the unique meta-argument a′={a} (resp. b′={b}, d′={d}, e′={e}, g′={g}). Thus A3′={a′,b′,c′,d′,e′,f′,g′}. R3′ is depicted in Fig. 6-(c).

For HG4, the argument b (resp. c) gives rise to the meta-argument: b′={b,d} (resp. c′={a,c}). The argument a (resp. d) gives rise to the meta-argument a′={a} (resp. d′={d}). Note that {b,c} is not a meta-argument since it is not coherent (it is not N-Cycle-Free). Thus, A4′={a′,b′,c′,d′}. R4′ is depicted in Fig. 6-(d).

Fig. 6.

The Dung AFs associated to the four AFNs G1, G2, G3 and G4.

The following result shows that there is a full correspondence between the extensions of an AFN G and those of the corresponding meta Dung AF HG under all the considered semantics.

Theorem 4.5.

Let G=⟨A,R,N⟩ be an AFN, HG=⟨A′,R′⟩ be its corresponding Dung AF.

If E⊆A is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of G then ΓE={Ca∣a∈E,Ca is a meta-argument associated to a and Ca⊆E} is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of HG.
Inversely, if Γ is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of HG, then EΓ=⋃C∈ΓC is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of G.

Example 3

Example 3(Cont).

It is easy to check that for any of the considered acceptability semantics, the extensions of each Gi (1⩽Gi⩽4) correspond exactly (in the sense of theorem 4.5) to the extensions of HGi 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 G=⟨A,R,N⟩ where A={a}∪A1∪…An, each Ai contains p arguments (p>1) and AiNa (for 1⩽i⩽n). Let H be the corresponding AF. The number of arguments in G is 1+p×n. Each set {a,b1,…bn} s.t. bi∈Ai for 1⩽i⩽n is a minimal coherent set containing a, i.e., is a meta argument in H. The number of meta arguments corresponding to a is pn and each argument x of A∖{a} gives rise to one meta argument ({x}). The total number of the meta arguments is then pn+p×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 Π′ 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 Π′, any atom in the body of any rule appears as a head in at least one rule, i.e., the Herbrand base of Π′ is HBΠ′=Head(Π′). 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 Π′ be the LP which is the fixpoint obtained from Π by repeatedly removing every rule r s.t. Body+(r)⊈Head(Π) and every expression not a s.t. a∉Head(Π). Then, a 3-valued interpretation I=⟨T,F⟩ is a P-stable model of Π if and only if I′=⟨T,F′⟩ is a P-stable model of Π′ where F′=F∩HBΠ′.

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 Π′ 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 I′=⟨T,F′⟩ is a well-founded (resp. M-stable, stable, L-stable) model of Π′ where F′=F∩HBΠ′.

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.: ⋃r∈ΠBody+(r)⊆Head(Π) and ⋃r∈ΠBody−(r)⊆Head(Π). 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 Body−(r). On the other hand, if a is an atom of Body+(r), 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 7

Definition 5.3

Definition 5.3(The AFN representing an LP).

Let Π={r1,…,rn} be an LP. The AFN representing Π is defined by GΠ=⟨Π,RΠ,NΠ⟩ where:

if E⊆Π is a subset of rules having the same head (denoted Head(E)) and r∈Π is a rule s.t. Head(E)∈Body+(r), then we put ENΠr;
if r,r′∈Π are two rules s.t. Head(r)∈Body−(r′) then we put rRΠr′.

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

Definition 5.4(From a labelling of GΠ to a 3-valued interpretation of Π).

Let Π={r1,…,rn} be an LP and GΠ=⟨Π,RΠ,NΠ⟩ its corresponding AFN. Let L=⟨IN,OUT,UND⟩ be a labelling of GΠ. The 3-valued interpretation associated to L is denoted Int(L) and defined as follows. For every a∈HBΠ:

if there is a rule r∈Π s.t. a=Head(r) and L(r)=in then a is interpreted as true, i.e., Int(L)(a)=t.
if a is not interpreted as true and there is a rule r∈Π s.t. a=Head(r) and L(r)=undec then a is interpreted as undefined i.e., Int(L)(a)=u.
Otherwise, i.e., if for every rule r∈Π s.t. a=Head(r) we have L(r)=out then a is interpreted as false, i.e., Int(L)(a)=f.

Definition 5.5

Definition 5.5(From a 3-valued interpretation of Π to a labelling of GΠ).

Let Π={r1,…,rn} be an LP and GΠ=⟨Π,RΠ,NΠ⟩ its corresponding AFN. Let I=⟨T,F⟩ be a 3-valued interpretation of Π. The labelling associated to I is denoted Label(I) and defined as follows. For every r∈Π:

if Body+(r)⊆T and Body−(r)⊆F then r is labelled in in Label(I).
if Body+(r)∩F≠∅ or Body−(r)∩T≠∅ then r is labelled out in Label(I).
Otherwise, r is labelled undec in Label(I).

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 GΠ be the AFN representing Π.

If L is a complete (resp. the grounded, a preferred, a stable) labelling of GΠ then Int(L) 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 Label(I) is a complete (resp. the grounded, a preferred, a stable) labelling of GΠ.
It is possible to find a semi-stable labelling L of GΠ s.t. Int(L) is not an L-stable model of Π. Inversely, it is possible to find an L-stable model I of Π s.t. Label(I) is not a semi-stable labelling of GΠ.

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 in, but by directly minimizing the set of conclusions of the undefined arguments.

Theorem 5.7.

Let Π be an LP and GΠ be the AFN representing Π.

If L=(IN,OUT,UND) is a complete labelling of GΠ that minimizes (w.r.t. set inclusion) the set {Head(r)|r∈UND} then Int(L) is an L-stable model of Π. Inversely, if I=⟨T,F⟩ is an L-stable model of Π then Label(I) is a complete labelling of GΠ that minimizes (w.r.t. set inclusion) the set {Head(r)|r∈UND}.

Example 2

Example 2(Cont).

Consider again the LPs Π1, Π2, Π3 and Π4 given in Example 2. Using Definition 5.3, it is easy to check that the AFN GΠ1 (resp. GΠ2, GΠ3, GΠ4) representing the LP Π1 (resp. Π2, Π3, Π4) corresponds exactly to the AFN G1 (resp. G2, G3, G4) depicted in Fig. 4-(a) (resp. Fig. 4-(b), Fig. 4-(c), Fig. 4-(d)).

Recall that Π1 has one P-stable model I=⟨{s},{p,q}⟩ which is also its unique well-founded, M-stable, stable and L-stable model and G1 has one complete labelling L=({c},{a,b},∅) which is also its unique grounded, preferred, stable and semi-stable labelling. We can check that I=Int(L) and L=Label(I).

Π2 has one P-stable model I=⟨{s},∅⟩ which is also its unique well-founded, M-stable and L-stable model but Π2 has no stable model. G2 has one complete labelling L=({d},{c},{a,b}) which is also its unique grounded, preferred and semi-stable labelling but G2 has no stable labelling. We have: I=Int(L) and L=Label(I).

Π3 has three P-stable models I1=⟨∅,∅⟩, I2=⟨{q},{p}⟩, I3=⟨{p,t},{q,s,u}⟩. Its well-founded model is I1, its preferred models are I2 and I3, its unique L-stable model is I3 and it has no stable model. G3 has three complete labellings: L1=(∅,∅,{a,b,c,d,e,f,g}), L2=({b},{a},{c,d,e,f,g}) and L3=({a,d},{b,c,e},{f,g}). Its grounded labelling is L1, its preferred labellings are L2 and L3, its unique semi-stable labelling is L3 and it has no stable labelling. We can check that Ii=Int(Li) for i∈{1,2,3}.

Π4 has one P-stable model I=⟨∅,∅⟩ which is also its unique well-founded, M-stable and L-stable model but Π4 has no stable model. G4 has one complete labelling L=(∅,∅,{a,b,c,d}) which is also its unique grounded, preferred and semi-stable labelling but G4 has no stable labelling. We have: I=Int(L) and L=Label(I).

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 (ra) that expresses its acceptability conditions. Intuitively, whenever an argument b attacks a, the expression not b appears in the body of ra. Similarly, whenever a set of arguments E is necessary for a, we introduce a new atom e which appears in the positive body of ra and a rule for every argument x∈E telling that e is obtained from x. This translation is formally given as follows:

Definition 5.8

Definition 5.8(The LP representing an AFN).

Let G=⟨A,R,N⟩ be an AFN. The LP ΠG representing G is constructed as follows:

Each argument of A is considered as an atom in ΠG. Moreover, let E1,…,Ep be all the subsets of A s.t. for every Ei there is some argument a∈A with EiNa. We associate to each Ei an atom (denoted ei) in ΠG. Thus, the Herbrand base of ΠG is HBΠG=A∪A′ where A′={e1,…,ep}.
For every argument a∈A, let b1,…,bm be its attackers and let E1,…,Ek be all the subsets of A s.t. EiNa for 0⩽i⩽k. The argument a gives rise in ΠG to the rule: ra:a←e1,…,ek,not b1,…,not bm.
For every atom ei associated to a set Ei we add |Ei| rules as follows: for every x∈Ei, the rule: ei←x is added to ΠG.

To extract a 3-valued interpretation from a labelling and vice versa, let us define the functions Int′ and Label′.

Definition 5.9

Definition 5.9(From a labelling of G to a 3-valued interpretation of ΠG).

Let G=⟨A,R,N⟩ be an AFN and ΠG its corresponding LP. Let L=⟨IN,OUT,UND⟩ be a labelling of G. The 3-valued interpretation associated to L is denoted Int′(L) and defined as follows:

For every a∈A, if L(a)=in (resp. L(a)=out, L(a)=undec) then Int′(L)(a)=t (resp. Int′(L)(a)=f, Int′(L)(a)=u).
For every e∈A′:
- ∗ if there is a rule r:e←a in ΠG s.t. L(a)=in then e is interpreted as true, i.e., Int′(L)(e)=t.
- ∗ if e is not interpreted as true and there is a rule r:e←a in ΠG s.t. L(a)=undec then e is interpreted as undefined i.e., Int′(L)(e)=u.
- ∗ Otherwise, i.e., if for every rule r:e←a in ΠG, it holds that L(a)=out then e is interpreted as false, i.e., Int′(L)(e)=f.

Definition 5.10

Definition 5.10(From a 3-valued interpretation of ΠG to a labelling of G).

Let G=⟨A,R,N⟩ be an AFN and ΠG its corresponding LP. Let I=⟨T,F⟩ be a 3-valued interpretation of ΠG. The labelling associated to I is defined by: Label′(I)=(T∩A,F∩A,A∖(T∪F)).

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 G=⟨A,R,N⟩ be an AFN and ΠG be the LP representing G. If L is a complete (the grounded, a preferred, a stable, a semi-stable) labelling of G then IL=Int′(L) is a P-stable (the well-founded, an M-stable, a stable, an L-stable) model of ΠG. Inversely, if I=⟨T,F⟩ is a P-stable (the well-founded, an M-stable, a stable, an L-stable) model of ΠG then LI=Label′(I) is a complete (the grounded, a preferred, a stable, a semi-stable) labelling of G.

Example 3

Example 3(Cont).

Let us take again our four AFNs G1,…,G4. The LP Π1′ (resp. Π2′, Π3′, Π4′) is obtained from G1 (resp. G2, G3, G4) by Definition 5.8. (see Fig. 7).

Fig. 7.

LPs obtained from our four AFNs.

Π1′ has one P-stable model I=⟨{c},{a,b,e1,e2}⟩ which is also its unique well-founded, M-stable, stable and L-stable model. G1 has one complete labelling L=({c},{a,b},∅) which is also its unique grounded, preferred, stable and semi-stable labelling. It is easy to check that I=Int′(L) and L=Label′(I).

Π2′ has one P-stable model I=⟨{d},{c}⟩ which is also its unique well-founded, M-stable and L-stable model but Π2′ has no stable model. G2 has one complete labelling L=({d},{c},{a,b}) which is also its unique grounded, preferred and semi-stable labelling but G2 has no stable labelling. We have: I=Int′(L) and L=Label′(I).

Π3′ has three P-stable models I1=⟨∅,∅⟩, I2=⟨{b,e1},{a}⟩ and I3=⟨{a,d},{b,c,e,e1}⟩. Its well-founded model is I1, its preferred models are I2 and I3, its unique L-stable model is I3 and it has no stable model. G3 has three complete labellings: L1=(∅,∅,{a,b,c,d,e,f,g}), L2=({b},{a},{c,d,e,f,g}) and L3=({a,d},{b,c,e},{f,g}). Its grounded labelling is L1, its preferred labellings are L2 and L3, its unique L-stable labelling is L3 and it has no stable labelling. It is easy to check that I1=Int′(L1) and L1=Label′(I1); I2=Int′(L2) and L2=Label′(I2); I3=Int′(L3) and L3=Label′(I3).

Π4′ has one P-stable model I=⟨∅,∅⟩ which is also its unique well-founded, M-stable and L-stable model but Π4′ has no stable model. G4 has one complete labelling L=(∅,∅,{a,b,c,d}) which is also its unique grounded, preferred and semi-stable labelling but G4 has no stable labelling. We have: I=Int′(L) and L=Label′(I).

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 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 aNb 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 8 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 ENb is replaced by the implication b⇒⋁a∈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 ⟨A={a,b,c},R={a,b},N={(b,c)}⟩ has one stable extension: {a}, but the constrained AF ⟨A,R,C=c⇒b⟩ has no stable extension (the only stable extension of ⟨A,R⟩ is {a,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 (ADF+s) and provides a translation from normal LPs to 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 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 9 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.

Notes

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

2 I is a fixed-point of Ψ iff Ψ(I)=I.

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 I=⟨T,F⟩. For the sake of homogeneity we define in this paper all kinds of models as 3-valued interpretations.

4 Notice that a similar generalization of the attack relation is also possible by considering relations of the form ERa where the argument a is attacked by the set of arguments E but not by a subset E′ of E, unless there is another explicit attack relation: E′Ra. There is no substantial difficulty to generalize the framework to this extended setting.

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

6 Every argument which is not powerful in 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 E.

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

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.

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.

Appendices

Appendix

AppendixProofs

Proof of Proposition 3.6.

⇒) Let E⊆A be a coherent set. To prove that every argument a∈E is powerful in E let us construct a sequence of sets of arguments E1,…,Em s.t.: (1) E1,…Em is a partition of E; (2) ∀a∈E1, ∄E⊆A s.t. ENa (arguments of E1 does not require any other argument) and (3) for i>1, then ∀a∈Ei, ∀E⊆A s.t. ENa, E∩⋃1⩽j<iEi≠∅ (the necessities on any argument of Ei are satisfied by the preceding sets E1,…Ei−1). Indeed if such a sequence is constructed, then for every argument a∈E, let a∈Ei. It is then clear that a sequence of arguments (not necessarily a minimal one) leading to a may be obtained by simply flattening the sequence E1,…Ei−1 (replacing each Ei by the subsequence of its arguments taken in an arbitrary order) and adding a at the end. Now the sequence of sets of arguments E1,…Em is constructed us follows. E1={a∈E∣∄E⊆A s.t. ENa}. We have E1≠∅ for if E1=∅ then ∀a∈E, ∃E⊆A s.t. ENa. Since E is closed under N−1, E∩E≠∅. But this means that E is not coherent, contradiction.

Now, let E2={a∈E∖E1∣∄E⊆A s.t. E∩E1=∅ and ENa}. We have E2≠∅ for if E2=∅ then ∀a∈E∖E1, ∃E⊆A s.t. ENa and E∩E1=∅. Since E is closed under N−1, E∩E≠∅, hence E∩(E∖E1)≠∅ (because E∩E1=∅), i.e., E is not coherent, contradiction.

We continue this process of constructing the sets Ei. Since the number of arguments is finite, this process stops necessarily at some set Em whose arguments are not necessary to any other argument. Then, by construction, the sequence E1,…Em satisfies the conditions (1)–(3) mentioned above.

⇐) Let E⊆A s.t. ∀a∈E, a is powerful in E, i.e., ∀a∈E, there is a sequence of arguments a0,…,ak of E s.t. ak=a; there is no E⊆A s.t. ENa0 and for 1⩽i⩽k: for all E⊆A, if ENai, then E∩{a0,…,ai−1}≠∅.

It is straightforward from this definition that ∀a∈E, if ENa for some E⊆A, then E∩E≠∅, i.e., that E is closed under N−1. From the definition (first item), it is clear that ∃a∈E s.t. ∀E⊆A, . This condition implies that: ∃a∈E s.t. ∀E⊆A, or E∩E≠∅. It is easy to check that this last condition is equivalent to that for N-Cycle-Freeness (see Definition 3.3). □

Proof of Proposition 3.7.

a is not powerful in E iff there is no coherent subset C of E s.t. a∈C.
⇒) Let E⊆A and let a∈E be a non powerful argument of E. Suppose that there is C⊆E s.t. C is coherent and a∈C. From proposition 3.6, it follows that a is powerful in C. But in this case a remains powerful in any superset of C (it suffices to take in E the same sequence ending by a taken in C). Contradiction.
⇐) Let E⊆A and a∈E s.t. there is no coherent subset C of E containing a. Suppose that a is powerful in E. Then from Definition 3.5, there is a sequence a0,…,ak∈E s.t. ak=a; there is no E⊆A s.t. ENa0 and for 1⩽i⩽k: for all E⊆A, if ENai, then E∩{a0,…,ai−1}≠∅. It is then easy to check that the set {a0,…,ak} is coherent. Contradiction.
a is not powerful in E iff ∃E⊆A s.t. ENa and ∀E⊆A s.t. ENa, ∀b∈E∩E, b is not powerful in E.
⇒) Let E⊆A and a an argument which is not powerful in E. If we suppose that ∄E⊂A s.t. ENa, then clearly {a} is a coherent set containing a, contradiction. If we suppose that ∃E⊆A s.t. ENa and ∃b∈E∩E s.t. b is powerful in E. Then, there is C⊆E s.t. C is coherent and b∈C. It follows that C∪{a} is a coherent set too. But thus contradicts the fact that a is not powerful in E.
⇐) Let E⊆A and a an argument s.t.: ∃E⊆A s.t. ENa and ∀E⊆A s.t. ENa, ∀b∈E∩E, b is not powerful in E. Suppose that a is powerful in E. Thus, there is C⊆E s.t. C is coherent and a∈C. From the definition of coherence, for every E⊆A s.t. ENa, E∩C≠∅, i.e., there exists b∈E∩E s.t. b∈C. This means that there is a coherent subset of E containing b (C), i.e., b is powerful in E. Contradiction.

□

Proof of Theorem 3.13.

Let G=⟨A,R,N⟩ be an AFN and E⊆A be a strongly coherent set.

(1) E is an admissible set iff E⊆FG(E):
⇒) Suppose that E is an admissible set. Thus, if a∈E then E defends a, i.e. a∈FG(E).
⇐) Suppose that E⊆FG(E). ∀a∈E we have a∈FG(E), i.e., a is defended by E. Thus E is strongly coherent and defends all its elements, so it is admissible.
(2) E is a complete extension iff E=FG(E):
⇒) Suppose that E is a complete extension. Then, E is admissible and from proposition point 1. of the current theorem, we have E⊆FG(E). Now, let a∈FG(E). Then, a is defended by E but since E is a complete extension, a∈E. Thus FG(E)⊆E, so FG(E)=E.
⇐) Suppose that E=FG(E). Then E⊆FG(E) and E is admissible (from point 1. of the current theorem). Now, let a be an argument defended by E, then a∈FG(E). Since FG(E)⊆E, a∈E. Thus E is admissible and contains any argument it defends, hence E is a complete extension.
(3) E is the grounded extension of G iff it is the least (w.r.t. set inclusion) complete extension of G:
Follows from the definition of a grounded extension (Definition 3.12) and the second point of the current.
(4) There is at least one preferred extension for G; every preferred extension is a complete extension but not vice versa; E is a preferred extension iff it is a maximal (w.r.t. set inclusion) complete extension:
The existence of at least one preferred extension follows from the fact that there is always at least one admissible set for any AFN. Indeed, obviously ∅ is always admissible.
Let E be a preferred extension and suppose that E is not complete. Then, there is a∈A s.t. E defends a and a∉E. But, in this case E∪{a} is admissible which contradicts the fact that E is a maximal admissible set. Hence, every preferred extension is a complete extension. Let us take a counter-example showing that a complete extension may not be preferred. Let G=⟨A={a,b,c},R={(a,b),(b,a),(b,c),(c,c)},N=∅⟩. G has three complete extensions: ∅, {a} and {b}. {a} and {b} are also preferred but ∅ is not.
The fact that E is a preferred extension iff it is a maximal (w.r.t. ⊆) complete extension follows immediately from point 2 of the current theorem.
(5) If E is a stable extension then E is a semi-stable extension but not vice versa; if E is a semi-stable extension, then E is a preferred extension but not vice versa:
Let E⊆A be a stable extension. Then from the definition of stable extensions we have Ed=A∖E. Thus, E∪Ed=A which is the maximal possible set of arguments. Hence, E is a semi-stable extension.
To show that the inverse is false, take G=⟨A={a,b,c},R={(c,c)},N={a,b}⟩. {a,b} is a semi-stable extension of G but not a stable extension.
Before proving that each semi-stable extension is preferred, let us first prove the following lemma.
Lemma 1.
If E and E′ are two complete extensions s.t. E⊂E′ then Ed⊂E′d.
Proof of Lemma 1.
Let E and E′ be two complete extensions s.t. E⊂E′. Thus, any argument deactivated by E is clearly deactivated by E′, hence E⊆E′. Now, suppose for the sake of contradiction that Ed=E′d. Let a∈E′∖E. For every bRa, b∈E′d because E′ defends all its elements. It follows that b∈Ed, i.e. that E also defends a. But a∉E and this contradicts the fact that E is a complete extension. Then, it follows that Ed⊂E′d. □
Now, let E⊆A be a semi-stable extension. Suppose for the sake of contradiction that E is not a preferred extension. Thus, there is E′⊆A s.t. E⊂E′ and E′ is a complete extension. From the above lemma, it holds that Ed⊂E′d. It follows that E∪Ed⊂E′∪E′d. Contradiction with the fact that E is a semi-stable extension.
To show that the inverse does not hold, let us take a counter-example. Let us consider the AFN G=⟨A={a,b,c,d},R={(a,b),(a,c),(b,a),(c,c),(d,d)},N=∅⟩. This system admits {a} and {b} as preferred extensions. However, only {a} is a semi-stable extension. Indeed {a}d={b,c} and {b}d={a}. We have that: {b}∪{b}d⊂{a}∪{a}d.
(6) If E is a stable extension, then E is a preferred extension but not vice versa; there may be zero, one or several stable extensions for G:
If E is a stable extension, then from (5) E is a semi-stable extension and from (5) again it is also a preferred extension.
To show that the inverse is not true, let us take the AFN G=⟨A={a,b,c},R={(a,b),(b,a),(b,c),(c,c)},N=∅⟩. {a} is a preferred extension but it is not stable.
To show that there may be zero, one or several stable extensions for an AFN, it suffices to find an example for each case: G1=⟨A={a},R={(a,a)},N=∅⟩ has no stable extension; G2=⟨A={a,b},R={(a,b)},N=∅⟩ admits {a} as a unique stable extension and G3=⟨A={a,b},R={(a,b),(b,a)},N=∅⟩ has two stable extensions: {a} and {b}.

□

Proof of Theorem 3.18.

Admissible

⇒) Let E be an admissible set and prove that L=(E,Ed,A∖(E∪Ed)) is an admissible labelling.

Safety of L follows directly from the coherence of E and the fact that an argument a is not powerful in A iff there is no coherent set C⊆A containing a (see proposition 3.7) which implies that a∈Ed.

Let a∈E and show that a is legally in in L. Let b be an argument s.t. bRa. Clearly b∉E follows from conflict-freeness of E. Suppose that b∈A∖(E∪Ed). Then, there exists a coherent set C⊆A containing b and since b∉Ed. This means that E does not defend a which contradict the fact that E is an admissible set. Thus b∈Ed, i.e. b∈out(L). Now let E⊆A s.t. ENa. From closure of E under N−1, it holds that E∩E≠∅, i.e. E∩in(L)≠∅. Hence, a is legally in in L.

Now, let a∈Ed and show that a is legally out in L (i.e. either ERa or ∃E∈A s.t. ENa and E⊆Ed). To do so, let us suppose that ∀E⊆A s.t. ENa, E⊈Ed and prove that ERa. Then we have: ∀E⊆A s.t. ENa, ∃b∈E s.t. b∉Ed, i.e. there is a coherent set C containing b s.t. . Thus, we can construct a coherent set C′ satisfying ∀E⊆A s.t. ENa, C′∩E≠∅ and . But then the set C′∪{a} is coherent too, and since a∈Ed, it holds (from the definition of Ed) that ERC′. Since , it must be the case that ER{a}. This means that every a∈Ed is legally out. It follows from the preceding elements that L is an admissible labelling.

⇐) Let L be an admissible labelling and prove that E=in(L) is an admissible extension and out(L)⊆Ed.

L is safe and all arguments in in(L) (resp. in out(L)) are legally in (resp. out). The coherence of E follows from the safety of L. E is conflict-free, for if we suppose the contrary then there exists a,b∈E s.t. aRb. This means that b in not legally in. Contradiction. Thus, E is strongly coherent.

Before proving that E defends all its elements, let us first prove that out(L)⊆Ed. Let a∈out(L), a is legally out. Then, two cases are possible: the first case is that a is attacked by some argument b labelled in, i.e., b∈E, but in this case, every coherent set C containing a is attacked by b, hence by E, i.e., a∈Ed. The second case is that there is E⊆A s.t. ENa and E⊆out(L). In this case either there is no coherent set containing a, so a∈Ed or such coherent sets exists and every coherent set C containing a contains at least an argument b∈E. Since a1 is labelled out and is legally out we have again two cases: either ERa1 so ERC or there is E1⊆A s.t. E1Na1 and E1⊆out(L) and so on. We repeat this process. Since the possibility that a does not belong to any coherent set is discarded (in the considered arbitrary coherent set C the continuation of this reasoning process does not involve necessity cycles) and since the number of arguments is finite, it must exist some ai s.t. ai∈C and ERai, i.e., each coherent set C containing a is attacked by E, hence a∈Ed.

Now, for all a∈E, suppose that b is an argument s.t. bRa. since a is legally in, b is necessarily labelled out. From the fact that out(L)⊆Ed we deduce that b∈Ed, i.e., every coherent set containing b is attacked by E. Thus, E defends all its elements. Since E is strongly coherent and defends all its elements, it is an admissible set.

Complete

⇒) Let E be an complete extension and prove that (E,Ed,A∖(E∪Ed)) is a complete labelling.

From the previous proof, it follows that every a∈E (resp. a∈Ed) is legally in (resp. legally out). It remains to show that every argument a∈A∖(E∪Ed) is legally undec.

Let a∈A∖(E∪Ed). Thus, there is a coherent set C containing a s.t. . Let us call this fact (F). Now, for the sake of contradiction let us suppose that a is illegally undec. We have three possible cases:

Case 1: ∃E⊆A s.t. ENa and E⊆out(L)=Ed. In this case, every coherent set C containing a must contain at least an element of E which is also in Ed. By definition of Ed, it holds that ERC. This contradicts (F).

Case 2: ∃b∈in(L)=E s.t. bRa. Again, it follows that every coherent set C containing a is attacked by E, which is in contradiction with (F).

Case 3: ∀b∈A, if bRa then b∈out(L)=Ed and ∀E⊆A, if ENa then E∩in(L)≠∅. In this case, clearly E∪{a} is coherent and for every b that attacks a, it holds that every coherent set containing b is attacked by E, i.e, E defends a, but a∉E. This contradicts the fact that E is a complete extension. It follows that: every argument in A∖(E∪Ed) is legally undec.

⇐) Let L be a complete labelling and prove that E=in(L) is a complete extension and out(L)=Ed. From the precedent proof, we have: E is admissible and out(L)⊆Ed. It remains to prove that E contains all the arguments it defends and that Ed⊆out(L).

Let us start by proving that Ed⊆out(L). Let a∈Ed. If there is no coherent set of arguments containing a, then a is not powerful in A (see proposition 3.7) and from the safety of L, it holds that L(a)=out. Now, suppose that there exists at least a coherent set containing a. For the sake of contradiction, let a∉out(L). Then, either a∈in(L) or a∈undec(L). a∈in(L) is impossible because in(L)=E. If a∈undec(L) then a is legally undec because L is a complete labelling. It follows from the definition of legally undec arguments that and ∀E⊆A s.t. ENa, E⊈out(L), i.e. any argument in E is labelled either in (hence, not attacked by E) or undec. By applying in a repetitive way the same reasoning on undec arguments, and since the number of arguments is finite, we construct a coherent set C containing a and s.t. . This contradicts the fact that a∈Ed. So Ed⊆out(L).

Now let us suppose that there is a∉E, hence a is labelled either out or undec and E defends a, i.e., E∪a is coherent and ∀b∈A, if bRa then E attacks any coherent set of arguments containing b. It follows from this statement that: ∀E⊆A, if ENa then E∩E≠∅, i.e., E∩in(L)≠∅ and ∀b∈A, if bRa then b∈Ed, i.e. b∈out(L). It is easy to check that under these conditions, a cannot be neither legally out nor legally undec. This contradicts the fact that L is a complete labelling. So, E contains any argument it defends, i.e., E is a complete extension.

Grounded

⇒) Let E be the grounded extension and prove that L=(E,Ed,A∖(E∪Ed)) is the grounded labelling. E is the ⊆-minimal complete extension. From the ⇒) part of the proof for complete semantics, it follows that L=(E,Ed,A∖(E∪Ed)) is a complete labelling. Suppose that L is not the grounded labelling, i.e., there is a complete labelling L′ s.t. in(L′)⊂in(L)=E. But, from the ⇐) part of the proof for complete semantics, it follows that in(L′) is a complete extension which contradicts the fact that E is the ⊆-minimal complete extension.

⇐) Let L be the grounded labelling and prove that E=in(L) is the grounded extension and out(L)=Ed. From the ⇐) part of the proof for complete semantics, we deduce that E=in(L) is a complete extension and that out(L)=Ed. Suppose that ∃E′⊆A s.t. E′⊂E and E′ is a complete extension. From the ⇒) part of the proof for complete semantics, it follows that (E′,E′d,A∖(E′∪E′d)) is a complete labelling. Contradicts the fact that L is the grounded labelling.

Preferred

⇒) Let E be a preferred extension and prove that (E,Ed,A∖(E∪Ed)) is a preferred labelling. The proof is similar to the ⇒) part of the proof for grounded semantics except that it is based on ⊆-maximization instead of ⊆-minimization.

⇐) Let L be a preferred labelling and prove that E=in(L) is a preferred extension and out(L)=Ed. From the ⇐) part of the proof for complete semantics, we deduce that E=in(L) is a complete extension and that out(L)=Ed. Suppose that there is E′⊆A s.t. E⊂E′ and E′ is a complete extension. Then, from the ⇒) part of the proof for complete semantics, it follows that (E′,E′d,A∖(E′∪E′d)) is a complete labelling. Contradiction with the fact that L is a preferred labelling.

Stable

⇒) Let E be an stable extension and prove that (E,Ed,A∖(E∪Ed)) is a stable labelling. if E is a stable extension, then from its definition: A∖(E∪Ed)=∅. Since it is also complete, form the ⇒) part of the proof for complete semantics, the labelling L=(E,Ed,A∖(E∪Ed)=∅) is complete and hence also stable since undec(L)=∅.

⇐) Let L be a stable labelling and prove that E=in(L) is a stable extension and out(L)=Ed. From the ⇐) part of the proof for complete semantics, we deduce that E=in(L) is a complete extension and out(L)=Ed. But since undec(L)=∅, clearly Ed=A∖E, i.e. E is a stable extension.

Semi-stable

⇒) Let E be an semi-stable extension and prove that (E,Ed,A∖(E∪Ed)) is a semi-stable labelling.

From the ⇒) part of the proof for complete semantics, it follows that L=(E,Ed,A∖(E∪Ed)) is a complete labelling. Suppose that ∃L′ s.t. undec(L′)⊂undec(L). From the ⇐) part of the proof for complete semantics, in(L′) is a complete extension with out(L)=(in(L))d. It is easy to check that undec(L′)⊂undec(L) is equivalent to (in(L′)∪(in(L′))d)⊂(E∪Ed). Contradiction with the fact that E is a semi-stable extension.

⇐) Let L be a semi-stable labelling and prove that E=in(L) is a semi-stable extension and out(L)=Ed. From the ⇐) part of the proof for complete semantics, it follows that E=in(L) is a complete extension and that out(L)=Ed. Suppose that there is complete E′ s.t. (E∪Ed)⊂(E′∪E′d). From the ⇒) part of the proof for complete semantics, it follows that L′=(E′,E′d,A∖(E′∪E′d)) is a complete labelling. Moreover, it is easy to check that (E∪Ed)⊂(E′∪E′d) is equivalent to undec(L′)⊂undec(L). Contradiction with the fact that L is a semi-stable labelling. □

Proof of Theorem 4.1.

The proof is straightforward since the definition of any kind of extension in an AFN ⟨A,R,N⟩ with N=∅ coincides with that of the same kind of extension in the AF ⟨A,R⟩. □

Proof of Proposition 4.4.

The proof follows immediately from Definition 4.2. □

Proof of Theorem 4.5.

Admissible

⇒) Let E∈A be an admissible set of G and let ΓE be the set of subsets of arguments defined by: ΓE={Ca∣a∈E,Ca⊆E and Ca is a meta-argument associated to a}. Thus, each argument of E is represented in ΓE by at least one meta-argument and it is easy to check that ⋃C∈ΓEC=E. Let us show that ΓE is an admissible set of HG. ΓE is conflict-free. Indeed, supposing the inverse means that there is Ca,Cb∈ΓE s.t. CaR′Cb, i.e., there is a′∈Ca and b′∈Cb s.t. a′Rb′. But since Ca,Cb⊆E, a′,b′∈E. Contradiction with the fact that E is conflict-free.

Let Ca∈ΓE be a meta-argument of an argument a∈E. Let Cb∉ΓE be a meta-argument of an argument b∈A∖E and CbR′Ca. From the definition of R′, it follows that there is b′ in Cb, hence in A∖E and there is a′ in Ca, hence in E s.t. b′Ra′. Since E defends all its elements. Namely, E defends a′ against b′. So, for every coherent set C containing b′ there is c∈E s.t. cRC. Since Cb is a coherent set containing b′, then there exists a meta-argument of ΓE (we can take any meta-argument Cc of c) which attacks Cb. ΓE defends all its elements. It is an admissible set of HG.

⇐) Let Γ be an admissible set of HG and let EΓ=⋃C∈ΓC. Since each meta-argument of Γ is a coherent set, it follows that EΓ is coherent and from the conflict-freeness of Γ it follows that EΓ is conflict free. Hence, EΓ is strongly coherent. Let a∈E, b∉E and bRa. Then for every meta argument Cb∉Γ associated to b and every meta-argument Ca∈Γ associated to a, it holds that: CbR′Ca. Since Γ is admissible, there is a meta-argument C∈Γ s.t. CR′Cb, i.e. EΓRCb. But since any coherent set of arguments C′ containing b contains at least one sub-argument associated to b, it follows that for every coherent set of arguments C′ containing b, we have EΓRC′. Thus, EΓ is strongly coherent and defends all its elements, i.e. an admissible set of G.

Complete

⇒) Let E∈A be a complete extension of G and let ΓE be the set of subsets of arguments defined by: ΓE={Ca∣a∈E,Ca⊆E and Ca is a meta-argument associated to a}. Thus, each argument of E is represented in ΓE by at least one meta-argument and it is easy to check that ⋃C∈ΓEC=E. Let us show that ΓE is a complete extension of HG. From the previous proof, it follows that ΓE is an admissible set of HG. It remains to show that ΓE contains every meta-argument it defends.

For the sake of contradiction, suppose that there is a meta-argument Ea∉ΓE associated to a∉E defended by ΓE, i.e., ∀C s.t. CR′Ca, ΓER′C.

First, let us precise that a first consequence of our hypotheses is that ΓE∪{Ca} is conflict-free. Indeed if we suppose that ΓER′Ca then since ΓE defends Ca it holds that ΓER′ΓE which contradicts the fact that ΓE is conflict-free. If we suppose that CaRΓE then since ΓE is admissible, ΓER′Ca which coincides with the first case implying conflict in ΓE.

Now, let us show that our hypotheses contradict the fact that E is a complete extension of G. Since Ca is a coherent set, there is a0∈Ca s.t. there is no E⊆A with ENa0. E∪a0 is coherent since E is coherent and a0 does not have any necessities to satisfy. if b is any argument s.t. bRa0 then any meta-argument Cb associated to b verifies CbR′Ca. Since ΓE defends Ca it follows that ΓER′Cb. Since any coherent set C′ containing b contains at least one meta-argument associated to b. Thus, for every coherent set C′ containing b it holds that ΓER′C′, i.e. ERC′. This means that E defends a0∉E. Contradicts the fact that E is a complete extension of G.

⇐) Let Γ be a complete extension of HG and let EΓ=⋃C∈ΓC. From the ⇐) part of the proof for admissible sets, it follows that EΓ is an admissible set of G. For the sake of contradiction, suppose that there exists a∉EΓ and EΓ defends a, i.e. EΓ∪{a} is coherent and if bRa then for every coherent set C containing b, EΓRC. Let Ca be a meta-argument associated to a, hence Ca∉Γ because a∉EΓ and show that Γ defends Ca. From EΓ∪{a} is coherent, it follows that all arguments of Ca except a are in EΓ. If Cb is a meta-argument s.t. CbR′Ca then two cases are possible. The first case is that CbRa′ with a′≠a hence a′∈EΓ, then there is at least a meta-argument associated to a′ in Γ. Consequently, CbRΓ. But since Γ is admissible it follows that ΓR′Cb. The second case is that CbRa,i.e., there is b′∈Cb s.t. b′Ra. Then, from the hypothesis that EΓ defends a, it follows that for every coherent set C containing b′, EΓRC. But Cb is a coherent set containing b′, so EΓRCb, i.e. there is a meta-argument C′∈Γ s.t. C′R′Cb. This means that Γ defends Ca which is outside it. Contradiction with the fact that Γ is a complete extension of HG.

Grounded

⇒) Let E be the grounded extension of G and ΓE is the corresponding set of meta-arguments defined as above. It follows from the ⇒) part of the proof of the complete semantics, that ΓE is a complete extension of HG. Suppose that ΓE is not the grounded extension of HG, i.e., there is Γ′⊂ΓE s.t. Γ′ is a complete extension of HG. From the ⇐) part of the proof of the complete semantics, it follows that EΓ′=⋃C∈Γ′C is a complete extension of G. But since Γ′⊂ΓE it is obvious that EΓ′⊂EΓE=E. Contradiction with the fact that E is the grounded extension of G.

⇐) Let Γ be the grounded extension of HG, i.e. the ⊆-minimal complete extension of HG. Then, from the ⇐) part of the proof of the complete semantics, it follows that the set of arguments EΓ=⋃C∈ΓC is a complete extension of G. Suppose for the sake of contradiction that EΓ is not the minimal complete extension of G, i.e., that there is a set E′⊂EΓ and E′ is a complete extension of G. From the ⇒) part of the proof of the complete semantics, it follows that ΓE′ is a complete extension of HG. But since E′⊂EΓ it is obvious that ΓE′⊂ΓEΓ=Γ. Contradiction with the fact that Γ is the grounded extension of HG.

Preferred

⇒) Let E be a preferred extension of G and ΓE is the corresponding set of meta-arguments defined as above. It follows from the ⇒) part of the proof of the complete semantics, that ΓE is a complete extension of HG. Suppose that ΓE is not a preferred extension of HG, i.e., there is Γ′⊃ΓE s.t. Γ′ is a complete extension of HG. From the ⇐) part of the proof of the complete semantics, it follows that EΓ′=⋃C∈Γ′C is a complete extension of G. But since Γ′⊃ΓE it is obvious that EΓ′⊃EΓE=E. Contradiction with the fact that E is a preferred extension of G.

⇐) Let Γ be a preferred extension of HG, i.e. a ⊆-maximal complete extension of HG. Then, from the ⇐) part of the proof of the complete semantics, it follows that the set of arguments EΓ=⋃C∈ΓC is a complete extension of G. Suppose for the sake of contradiction that EΓ is not a maximal complete extension of G, i.e., that there is a set E′⊃EΓ and E′ is a complete extension of G. From the ⇒) part of the proof of the complete semantics, it follows that ΓE′ is a complete extension of HG. But since E′⊃EΓ it is obvious that ΓE′⊃ΓEΓ=Γ. Contradiction with the fact that Γ is a preferred extension of HG.

Stable

⇒) Let E be a stable extension of G and ΓE is the corresponding set of meta-arguments defined as above. It follows from the ⇒) part of the proof of the complete semantics, that ΓE is a complete extension of HG. Suppose that ΓE is not a stable extension of HG, i.e., there is a meta-argument Ca∉ΓE associated to an argument a∉E s.t. . Thus, there is an argument a∉E and a coherent set Ca containing a s.t. . Contradiction with the fact that E is a stable extension of G.

⇐) Let Γ be a stable extension of HG, i.e. a complete extension of HG which attacks any meta-argument outside it. Then, from the ⇐) part of the proof of the complete semantics, it follows that the set of arguments EΓ=⋃C∈ΓC is a complete extension of G. Suppose for the sake of contradiction that EΓ is not a stable extension of G, i.e., that there is an argument a∉EΓ and a coherent set C containing a s.t. . This means, there exists a meta-argument Ca⊆C associated to a (if C itself is a ⊆-minimal coherent set containing a, then Ca=C, otherwise it is easy to check that a ⊆-minimal coherent set Ca⊂C containing a always exists) s.t. Ca∉Γ and . Contradicts the fact that Γ is a stable extension of HG.

Semi-stable

⇒) Let E be a semi-stable extension of G and ΓE is the corresponding set of meta-arguments defined as above. It follows from the ⇒) part of the proof of the complete semantics, that ΓE is a complete extension of HG. Suppose that ΓE is not a semi-stable extension of HG, i.e., there is Γ′⊆A′ s.t. Γ′ is a complete extension of HG and (Γ′∪Γ′d)⊃(ΓE∪ΓEd). From the ⇐) part of the proof of the complete semantics, it follows that EΓ′=⋃C∈Γ′C is a complete extension of G. From (Γ′∪Γ′d)⊃(ΓE∪ΓEd) it is easy to verify that (EΓ′∪EΓ′d)⊂(E∪Ed). Contradiction with the fact that E is a semi-stable extension of G.

⇐) Let Γ be a semi-stable extension of HG, i.e. a ⊆-maximal complete extension of HG. Then, from the ⇐) part of the proof of the complete semantics, it follows that the set of arguments EΓ=⋃C∈ΓC is a complete extension of G. Suppose for the sake of contradiction that EΓ is not a semi-stable extension of G, i.e., that there is a set E′⊆A s.t. E′ is a complete extension of G and (E′∪E′d)⊃(EΓ∪EΓd). From the ⇒) part of the proof of the complete semantics, it follows that ΓE′ is a complete extension of HG. But from (E′∪E′d)⊃(EΓ∪EΓd) it is easy to check that (ΓE′∪ΓE′d)⊃Γ∪Γd. Contradiction with the fact that Γ is a semi-stable extension of HG. □

Proof of Theorem 5.1.

To prove the theorem let us first prove the following lemma which says that any atom not appearing as a head in any rule of an LP is interpreted as false in any P-stable model of this LP.

Lemma 2.

Let Π be an LP and I=⟨T,F⟩ be a P-stable model of Π. If a is an atom of (HBΠ∖Head(Π)) then I(a)=f.

Proof of Lemma 2.

By definition, I is the least model of the generalized reduct ΠI of Π by I. Hence, I is the fixpoint obtained by repeating the application of the operator Ψ on ΠI starting from the interpretation ⟨∅,HBΠ⟩. Let a∈(HBΠ∖Head(Π)). From the definition of Ψ it is clear that the only way to assign the values t or u to a is to have a rule r in πI s.t. a=Head(r) which is obviously not possible for a. Then, a receives necessarily the value f. Notice also that from the previous lemma, it follows that I and I′ agree on atoms whose truth value is undefined (u), i.e. HBΠ∖(T∪F)=HBΠ′∖(T∪F′). □

Now let us turn to our theorem. Let Π be an LP and Π′ be the LP resulting from its simplification. We consider the partition of the rules of Π constituted from the following sets of rules. Π1={r∈Π∣(Body+(r)∪Body−(r))⊆Head(Π)} (rules whose all atoms of the body appear in the set of heads of Π rules); Π2={r∈Π∣a∉Head(Π) for some a∈Body+(r)} and Π3 contains the possible remaining rules, i.e., rules whose positive body is included in the set of heads of Π rules, but at least an atom of the negative body does not appear in the set of heads of Π rules, i.e., Π3={r∈Π|Body+(Π)⊆Head(Π) and a∉Head(Π) for some a∈Body−(r)}. Then, clearly Π′=Π1∪Π3′ where Π3′ is obtained from Π3 by removing any expression not a s.t. a∉Head(Π). Let ΠI (resp. Π′I′) be the generalized reduct of Π (resp. of Π′) by I (resp. by I′). Then, ΠI=Π1I∪Π2I∪Π3I and Π′I′=Π1I′∪Π3′I′ where Π1I (resp. Π2I, Π3I, Π1I′, Π3′I′) is obtained from Π1 (resp. from Π2, Π3, Π1, Π3′) by replacing in every rule of Π1 (resp. of Π2, Π3, Π1, Π3′) any expression not a by f if I(a)=t (resp. if I(a)=t, I(a)=t, I′(a)=t, I′(a)=t), by t if I(a)=f (resp. if I(a)=f, I(a)=f, I′(a)=f, I′(a)=f) and by u if I(a)=u (resp. if I(a)=u, I(a)=u, I′(a)=u, I′(a)=u). It is easy to verify that Π1I=Π1I′ since I and I′ agree on each atom appearing in Π1. Each rule in Π3I corresponds exactly to a rule in Π3′I′ to which we add to the body at least one t corresponding to expressions not a where a does not appear in Head(Π) (Lemma 2 shows that their value in I is f).

Now let I0=⟨∅,HBΠ⟩ and I0′=⟨∅,HBΠ′⟩. Let Ψn(I0)=In=⟨Tn,Fn⟩ (resp. Ψn(I0′)=In′=⟨Tn′,Fn′⟩) be the result of n successive applications of Ψ on Π (resp. Π′) starting from I0 (resp. from I0′). The proof of our theorem turns out to prove that for every n⩾0, Tn′=Tn and Fn′=Fn∩HBΠ′. It is easy to check that this is equivalent to the fact that Tn′=Tn and Un′=Un where Un (resp. Un′) are the atoms having the truth value u in the interpretation Ψn(I0) (resp. Ψn(I0′)). Let us prove this fact by induction on n.

For n=0, Ψ0(I0)=I0 and Ψ0(I0′)=I0′. The fact is true since T0=T0′=∅ and U0=U0′=∅.
Suppose Tn=Tn′ and Un=Un′ and prove that Tn+1=Tn+1′ and Un+1=Un+1′. Let a∈HBΠ s.t. In+1(a)=t, then there is a rule r:a←a1,…,ak in ΠI s.t. for all i⩽k, In(a)=t. It is clear that r∉Π2I. Indeed, every rule r′∉Π2I has in its body at least an atom from (HBΠ∖Head(Π)) which has necessarily the value f since from the definition of Ψ, such an atom can never receive the value t or u. If r∈Π1I then In+1′(a)=In+1(a)=t since Π1I=Π′I′ and Tn=Tn′. If r∈Π3I then there is a rule r′:a←a1′,…,am′ in Π3′I′ s.t. m<k, {a1′,…,am′}⊆{a1,…,ak} and for all b∈({a1,…,ak}∖{a1′,…,am′}), b=t. Since Tn=Tn′ it follows that In+1′(a)=In+1(a)=t. Inversely, let a∈HBΠ′ s.t. In+1′(a)=t, then there is a rule r:a←a1,…,ak in Π′I′ s.t. for all i⩽k, In′(a)=t. If r∈Π1′I′ then In+1(a)=In+1′(a)=t since Π1I=Π′I′ and Tn=Tn′. If r∈Π3′I′ then there is a rule r′:a←a1′,…,am′ in Π3′I′ s.t. m>k, {a1,…,ak}⊆{a1′,…,ak′} and for all b∈({a1′,…,am′}∖{a1,…,ak}), b=t. Since Tn=Tn′ it follows that In+1(a)=In+1′(a)=t.
Let a∈HBΠ s.t. In+1(a)=u, then In+1(a)≠t and there is a rule r:a←a1,…,ak in ΠI s.t. for all i⩽k, In(a)≠f. It is clear that r∉Π2I. Indeed, every rule r′∉Π2I has in its body at least an atom from (HBΠ∖Head(Π)) which has necessarily the value f since from the definition of Ψ, such an atom can never receive the value t or u. If r∈Π1I then In+1′(a)=In+1(a)=u since Π1I=Π′I′, Tn=Tn′ and Un=Un′. If r∈Π3I then there is a rule r′:a←a1′,…,am′ in Π3′I′ s.t. m<k, {a1′,…,am′}⊆{a1,…,ak} and for all b∈({a1,…,ak}∖{a1′,…,am′}), b=t. Since Tn=Tn′ and Un=Un′ it follows that In+1′(a)=In+1(a)=u. Inversely, let a∈HBΠ′ s.t. In+1′(a)=u, then In+1′(a)≠t and there is a rule r:a←a1,…,ak in Π′I′ s.t. for all i⩽k, In′(a)≠f. If r∈Π1′I′ then In+1(a)=In+1′(a)=u since Π1I=Π′I′, Tn=Tn′ and Un=Un′. If r∈Π3′I′ then there is a rule r′:a←a1′,…,am′ in Π3′I′ s.t. m>k, {a1,…,ak}⊆{a1′,…,ak′} and for all b∈({a1′,…,am′}∖{a1,…,ak}), b=t. Since Tn=Tn′ and Un=Un′ it follows that In+1(a)=In+1′(a)=u.

□

Proof of Corollary 5.2.

The proof follows easily from Definition 2.7. □

Proof of Theorem 5.6.

Complete labelling – P-stable model

L is a complete labelling ⇒ Int(L) is a P-stable model
Let L=(IN,OUT,UND) be a complete labelling of GΠ and I=Int(L)=⟨T,F⟩ be the associated 3-valued interpretation of Π. To prove that I is a P-stable model of Π we have to prove that I is the minimal fixpoint of the operator Ψ applied on the generalized reduct ΠI, i.e. the fixpoint obtained by the successive application of the operator Ψ on ΠI starting from the interpretation I0=⟨∅,HBΠ⟩. Let us denote by Ψn the operator corresponding to the application of Ψ for n successive times.
First, let us show that I is a fixpoint of Ψ, i.e. Ψ(I)=I. For that purpose, it suffices to show that: ∀a∈HBΠ, Ψ(I)(a)=t iff I(a)=t and Ψ(I)(a)=f iff I(a)=f (it follows then that Ψ(I)(a)=u iff I(a)=u). Let a∈HBΠ:
Ψ(I)(a)=t iff ∃r∈Π s.t. r=a←a1,…,am,not am+1,…,an. with
∀i∈{1,…,m}:I(ai)=t and ∀j∈{m+1,…,n}:I(aj)=f.
iff ∃r∈Π s.t. r=a←a1,…,am,not am+1,…,an. with
∀i∈{1,…,m}, ∃ri∈Π:Head(ri)=ai and L(ri)=in and
∀j∈{m+1,…,n}, ∀rj∈Π s.t. Head(rj)=aj, L(ri)=out. iff ∃r∈Π s.t.
r=a←a1,…,am,not am+1,…,an. and L(r)=in.
iff I(a)=t.
Ψ(I)(a)=f iff ∀r∈Π s.t. r=a←a1,…,am,not am+1,…,an.,
∃i∈{1,…,m}: I(ai)=f or ∃j∈{m+1,…,n}: I(aj)=t.
iff ∀r∈Π s.t. r=a←a1,…,am,not am+1,…,an.,
either ∃i∈{1,…,m}, ∀ri∈Π s.t. Head(ri)=ai, L(ri)=out
or ∃j∈{m+1,…,n}, ∃rj∈Π s.t. Head(rj)=aj, L(ri)=in. iff ∀r∈Π s.t.
r=a←a1,…,am,not am+1,…,an., L(r)=out.
iff I(a)=f.
Now it remains to show minimality of I. To do so, it suffices to show that the successive applications of Ψ on ΠI starting from I0 will mark as true any atom a s.t. I(a)=t (I(a)=t⇒∃n⩾1 s.t. Ψn(I0)(a)=t) and as false any atom a s.t. I(a)=f (I(a)=f⇒∀n⩾1, Ψn(I0)(a)=f). Indeed, since I has been shown to be a fixpont of Ψ and since the successive application of Ψ on ΠI starting from I0 yields the minimal fixpoint of Ψ then it is clear that further applications of Ψ cannot add to I neither true nor false atoms.
- ∗ (I(a)=t⇒∃n⩾1 s.t. Ψn(I0)(a)=t)
  Let a∈HBΠ s.t. I(a)=t. From safety of L it follows that there is a sequence r1,…,rs∈IN(L) s.t. Head(rs)=a and {r1,…,rs} is a meta-argument for rs in the sense of Definition 4.2. We can construct a partition R1,…,Rk of k sets of {r1,…,rs} (k⩽s) with Rk={rs}, if r∈R1 then Body+r=∅ (R1≠∅ since at least r1∈R1), if r∈Ri (1<i⩽k) then Body+r⊆⋃j<iHead(rj) and ∀r∈Ri (1⩽i⩽k), if r′∈Π is s.t. Head(r′)∈Body−(r) then L(r′)=out. Now, we prove by induction on i that: (Prop):∀i∈{1,…,k}, if r∈Rk and Head(r)=a then Ψi(I0)(a)=t (our result follows then by taking i=k).
  For i=0, let r∈R0 and Head(r)=a. Since we have: if r′∈Π is s.t. Head(r′)∈Body−(r) then I(a′)=out, it follows that I(a′)=f for every a′∈Body−(r). Thus Ψ1(I0)(a)=Ψ(I0)(a)=t.
  Suppose that (Prop) holds for any j⩽i<k and show that it holds for i+1. Let r∈Ri+1 and Head(r)=a. If a′∈Body+(r) then it holds that a′=Head(r′) for some r′∈Rj with j⩽i. From the induction hypothesis it follows that Ψj(I0)(a′)=t, hence Ψi(I0)(a′)=t. Moreover, if a′∈Body−(r) then I(a′)=f. It follows that Ψi+1(I0)(a)=t.
- ∗ I(a)=f⇒∀n⩾1, Ψn(I0)(a)=f Let a∈HBΠ s.t. I(a)=f. Then, for every rule r whose head is a i.e., of the form r:a→a0,…,am,not am+1,…,not an we have that L(r)=out. Since L is completely, r is legally out and two cases are possible. The first case is that for some j∈{m+1,…,n} there is a rule rj s.t. Head(rj)=aj and L(rj)=in which implies that I(aj)=t. In this case, it is clear that for every n⩾1, Ψn(I0)(a)=f. The second case is that for some i∈{0,…,m}, for all rule ri s.t. Head(ri)=ai it holds that L(ri)=out which implies that I(ai)=f. In this case we repeat for aj the same reasoning for r. since the number of rules is finite, either every starting rule r is involved in a cycle or for any (minimal) sequence of rules r1,…rk verifying: Head(rk)=a, Body+(r1)=∅ and for i>1, Body+(ri)=⋃j<iHead(rj), there is at least one rule r of the sequence s.t. I(b)=t for some b∈Body−(r). In both cases, it is clear that there is no mean to assign to a the value t or u.
Label(I) is a complete labelling ⇐ I is a P-stable model
Let I be a P-stable model of Π, i.e. a minimal fixpoint of the generalized reduct ΠI. Then, Ψ(I)=I (The application of Ψ is on ΠI) and I is a minimal interpretation satisfying the previous equality. Let L=Label(I), we prove that for every r∈GΠ, if r is labelled in (resp. out, undec) in L then it is legally ∈ (resp. legally out, legally undec) and that L is safe.
Let r:∈GΠ of the form a→a0,…,am,not am+1,…,not an s.t. L(r)=in. Since L(r)=in and from the definition of the function Label, it follows that for all i∈{0,…,m}, I(ai)=t and for all j∈{m+1,…,n}, I(aj)=f. Now, suppose for the sake of contradiction that r is illegally in. Two cases are possible.
Case 1: there is a rule r′ s.t. L(r′)≠out and r′RΠr, i.e., there is a rule r′ s.t. L(r′)≠out and Head(r′)=aj for some j∈{m+1,…,n}. Suppose that r′ has the form: r′:aj→a0′,…,am′′,not am′+1′,…,an′′. If L(r′)=in then from the definition of Label, for all i∈{0,…,m′}, I(ai′)=t and for all j∈{m′+1,…,n′}, I(aj′)=f. But from Ψ(I)=I it follows that I(aj)=t which contradicts the fact that for all j∈{m+1,…,n}, I(aj)=f. If L(r′)=undec, a similar reasoning yields I(aj)=u which contradicts also the same fact.
Case 2: there is a set of rules Ri s.t. for every r′∈Ri, L(r′)≠∈ and RiNΠr, i.e., for some i∈{0,…,m}, for every rule r′ s.t. Head(r′)=ai (the set Ri contains all such rules and only them), we have that L(r′)≠in. Let r′∈Ri and consider that r′ has the form aj→a0′,…,am′′,not am′+1′,…,an′′. If L(r′)=out then from the definition of Label it follows that: there is either i∈{0,…,m′} s.t. I(ai′)=f or j∈{m′+1,…,n′} s.t. I(aj′)=t. If L(r′)=undec then from the definition of Label it follows that: (1) there is either i∈{0,…,m′} s.t. I(ai′)≠t or j∈{m′+1,…,n′} s.t. I(aj′)≠f and (2) for all i∈{0,…,m′}, I(ai′)≠f and for all j∈{m′+1,…,n′}, I(aj′)≠t. But then from Ψ(I)=I it follows that either I(ai)=f or I(ai)=f i.e., I(ai)≠t which contradicts the fact that for all i∈{0,…,m}, I(ai)=t.

By a similar reasoning one can prove that if r is labelled out (resp. undec) in L then it is legally out (resp. undec).

For safety of L, let r be a rule r∈IN(L) with Head(r)=a. From the definition of the function Label and the fact that r is legally in it follows that I(a)=t. Now, for the sake of contradiction, suppose that r is not powerful in IN(L). Thus, if r1…rn is a minimal sequence of rules s.t. rn=r, Body+(r1)=∅ and for all i∈{2,…,n}, Body+(ri)⊆⋃j<iHead(rj), there is a rule r′ of the sequence s.t. L(r′)≠in, i.e. L(r′)=out or L(r′)=undec. By considering the structure of r′ and the definition of the function label it follows that the possible values of I for the atoms appearing in the body of r′ do never allow one to use r′ in a process ending by assigning the value t to a. Contradiction.

Grounded labelling – Well-founded model

L is a grounded labelling ⇒ Int(L) is a well-founded model
Let L=(IN,OUT,UND) be the grounded labelling of GΠ. Then L is also complete and hence I=Int(L)=⟨T,F⟩ is a P-stable model of Π. Suppose that I is not the P-stable model of Π having the minimal set T. Thus, it exists a P-stable model I′=⟨T′,F′⟩ of Π s.t. T′⊂T. It follows that L′=Label(I′)=(IN′,OUIT′,UND′) is a complete labelling of GΠ. But, from the definition of the function Label it is easy to check that IN′⊂IN which contradicts the fact that L is the grounded labelling of GΠ.
Label(L) is a grounded labelling ⇐ I is a well-founded model
Let I=⟨T,F⟩ be the Well-founded model of Π. Then I is also a P-stable model of Π and hence L=Label(I)=(IN,OUT,UND) is a complete labelling of GΠ. Suppose that L is not the complete labelling GΠ having the minimal set IN. Thus, it exists a complete labelling L′=(IN′,OUT′,UND′) of GΠ s.t. IN′⊂IN. It follows that I′=Int(L′)=(T′,F′) is a P-stable model Π. But, from the definition of the function Int it is easy to check that T′⊂T which contradicts the fact that I is the well-founded model of Π.

Preferred labelling – M-stable model

We obtain that if L is a preferred labelling of GΠ (resp. if I is an M-stable model of Π) then Int(L) is an M-stable model of Π (resp. then Label(I) is a preferred labelling of GΠ) by a proof similar to the previous one.

Stable labelling – Stable model

L is a stable labelling ⇒ Int(L) is a stable model
Let L=(IN,OUT,UND) be a stable labelling of GΠ. Then L is a complete labelling of GΠ s.t. OUT=∅. Hence, I=Int(L)=⟨T,F⟩ is a P-stable model of Π. But, from the definition of Label it is easy to check that no atom of Π can receive the value u, i.e., IN∪OUT=HB(Π). Thus, I=Int(L) is a stable model of Π.
Label(L) is a stable labelling ⇐ I is a stable model
Let I=⟨T,F⟩ be a stable model of Π. Then I is P-stable model of Π s.t. T∪F=∅. Hence, L=Label(I)=(IN,OUT,UND) is a complete labelling of GΠ. But, from the definition of Int it is easy to check that UND=∅ Thus, L=Label(I) is a stable labelling of GΠ.

Semi-stable labelling vs L-stable model

L is a semi-stable labelling ⇏ Int(L) is an L-stable model
Consider a counter-example. We take the LP Π with the rules: {(x):c→not c;(y):a→not b;(z):c→not c;(u):c→not c;(v):c→not c}. The corresponding AFN using Definition 5.3 is GΠ=⟨AΠ,RΠ,NΠ⟩ with AΠ={x,y,z,u,v}, RΠ={(x,x),(x,u),(y,z),(z,y),(u,u),(u,x),(v,v)} and N={(z,u),(y,v)}. GΠ has two semi-stable labellings: L1=({y},{z,u},{x,v}) and L2=({z},{y,v},{x,u}). We can verify that Int(L1)=⟨{a},{b}⟩ and Int(L2)=⟨{b},{a,g}⟩ but Int(L2) is an L-stable model of Π but Int(L1) is not.
Label(I) is a semi-stable labelling ⇍ I is an L-stable model
Consider a counter-example. We take the LP Π with the rules: {(x):c→e not c;(y):a→not b;(z):b→not a;(u):c→b,not c;(v):g→a not g;(w):d→not e;(k):e→not d}. The corresponding AFN using Definition 5.3 is GΠ=⟨AΠ,RΠ,NΠ⟩ with AΠ={x,y,z,u,v,w,k}, RΠ={(x,x),(x,u),(y,z),(z,y),(u,u),(u,x),(v,v),(w,k),(k,w)} and N={(z,u),(y,v),(k,x)}. Π has three L-stable models: I1=⟨{a,d},{b,c,e}⟩, I2=⟨{b,d},{a,e,g}⟩ and I3=⟨{b,e},{a,d,g}⟩. We can verify that Label(I1)=({y,w},{x,z,u,k},{v}), Label(I2)=({z,w},{x,y,v,k},{u}) and Label(I3)=({z,k},{y,v,w},{x,u}). Only Label(I1) and Label(I2) are semi-stable labellings. Label(I3) is not a semi-stable labelling.

□

Proof of Theorem 5.7.

Follows from Theorem 5.6 and Definitions 5.4 and 5.5. □

Proof of Theorem 5.11.

Complete labelling – P-stable model

⇒) Let L be a complete labelling of G and IL=Int′(L). We prove that IL is a least fix point of Ψ.

(1) Case 1. a∈A
- prove that Ψ(IL)(a)=t iff IL(a)=t
  Ψ(IL)(a)=t iff there is a rule r:a←e1,…,em,not a1,not an s.t. ∀i∈{1,…,m}, IL(ei)=t and ∀j∈{1,…,n}, IL(aj)=f.
  iff there is a rule r:a←e1,…,em,not a1,not an s.t. ∀i∈{1,…,m} there is a rule: ei←ai with L(ai)=in and ∀j∈{1,…,n}, IL(aj)=f.
  iff there is a rule r:a←e1,…,em,not a1,not an s.t. ∀Ei⊆A with EiNr, ∃ai∈Ei s.t. L(ai)=in and ∀j∈{1,…,n}, L(aj)=out.
  iff L(a)=in.
  iff IL(a)=t.
- prove that Ψ(IL)(a)=f iff IL(a)=f
  Ψ(IL)(a)=f iff for all rule r:a←e1,…,em,not a1,not an, ∃i∈{1,…,m}s.t.IL(ei)=f or ∃j∈{1,…,n} s.t. IL(aj)=t.
  iff for all rule r:a←e1,…,em,not a1,not an, ∃i∈{1,…,m} s.t; for all rule: ei←ai, L(ai)=out or ∃j∈{1,…,n} s.t. IL(aj)=t.
  iff for all rule r:a←e1,…,em,not a1,not an, ∃Ei⊆A with EiNr, ∀ai∈Ei, L(ai)=out or ∃j∈{1,…,n} s.t. ajRr and L(aj)=in.
  iff L(a)=out.
  iff IL(a)=f.
- The proof that Ψ(IL)(a)=u iff IL(a)=u follows immediately from the previous two proofs.
(2) Case 2. e∈A′
- prove that Ψ(IL)(e)=t iff IL(e)=t
  Ψ(IL)(e)=t iff there is a rule r:e←a s.t. IL(a)=t.
  iff there is a rule r:e←a s.t. L(a)=in.
  iff IL(e)=t.
- prove that Ψ(IL)(e)=f iff IL(e)=f
  Ψ(IL)(e)=f iff for all rule r:e←a, IL(a)=f.
  iff for all rule r:e←a, L(a)=out.
  iff IL(e)=f.
- The proof that Ψ(IL)(e)=u iff IL(e)=u follows immediately from the previous two proofs.

To prove minimality of IL it suffices to show (in a similar way as in theorem 5.6) that the successive application of the operator Ψ on ΠG starting from I0 yields to an interpretation in which all true (resp. false) atoms of IL are true (resp. false).

⇐) Let I=⟨T,F⟩ be a P-stable model of ΠG and prove that LI=(I)(T∩A,F∩A,A∖(T∪F)) is a complete labelling of G, i.e., all arguments of G are labelled legally in LI and LI is safe.

Let a be an argument of G labelled in. Then, there is in ΠG a unique rule r:a←e1,…,em,not a1,…,not an with I(a)=t. It follows that ∀i∈{1,…,m}, I(ei)=t and ∀j∈{1,…,m}, I(aj)=f. Thus, for all E⊆A s.t. ENa, there exists ai∈E s.t. LI(ai)=in and for all aj∈A s.t. ajRa, L(aj)=out. It follows that a is legally in.
Let a be an argument of G labelled out. Then, there is in ΠG a unique rule r:a←e1,…,em,not a1,…,not an with I(a)=f. It follows that either ∃i∈{1,…,m}, I(ei)=f or ∃j∈{1,…,m}, I(aj)=t. Thus, either there exists E⊆A s.t. ENa and for all ai∈E, LI(ai)=out or there exists aj∈A s.t. ajRa and L(aj)=in. It follows that a is legally out.
Let a be an argument of G labelled undec. Then, there is in ΠG a unique rule r:a←e1,…,em,not a1,…,not an with I(a)=u. It follows that ∀i∈{1,…,m}, I(ei)≠f and ∀j∈{1,…,m}, I(aj)≠t and either ∃i∈{1,…,m} s.t. I(ei)≠t or ∃j∈{1,…,n} s.t. I(aj)≠f. Thus, for all E⊆A s.t. ENa, E⊈out(LI) and for all aj∈A s.t. ajRa, L(aj)≠in and either there is E⊆A s.t. ENa and E∩in(LI)≠∅ or there is aj∈A s.t. ajRa and L(aj)≠out. It follows that a is legally undec.

To show safety of LI, observe that if we suppose the contrary, then by assigning f to each atom corresponding to an argument which is not powerful in in(LI) and to the corresponding atoms ei, the obtained interpretation is still a fixpoint of ΠG which contradicts the minimality of I.

Grounded labelling – Well-founded model

⇒) If L is the grounded labelling of G then it is also complete, thus IL=Int′(L) is a P-stable model of ΠG. Suppose that IL is not well-founded, i.e., that there is a P-stable model I′=⟨T′,F′⟩ of ΠG with T′⊂T. It follows that the labelling LI′=(T′∩A,F′∩A,A∖(T′∪F′)) is a complete labelling of G. It is easy to check that in(LI′)⊂in(L) which contradicts the fact that L is the grounded labelling of G.

⇐) If I=⟨T,F⟩ is the well-founded model of ΠG then it is also P-stable, thus LI=Label′(I) is a complete labelling of G. Suppose that LI is not grounded, i.e., that there is a complete labelling L′ s.t; in(L′)⊂in(LI). It follows that the labelling Int(L′)=⟨T′,F′⟩ is a P-stable model of ΠG. It is easy to check that T′⊂T which contradicts the fact that I is the well-founded model of ΠG.

Preferred labelling – M-stable model

The proof is similar to the previous one.

Stable labelling – Stable model

⇒) If L is a stable labelling of G then it is complete and undec(L)=∅. Thus, IL=Int′(L) is a P-stable model of ΠG. Moreover, for each atom of A in ΠG there is one and only one rule of ΠG which labelled in L either in or out but never undec. From the definition of the function Int′, it is easy to check that for each atom a∈A∪A′, we have that I(L)(a) equals either t or f but never u. Thus I(L) is a P-stable model of ΠG without undefined atoms, i.e., a stable model of ΠG.

⇐) If I⟨T,F⟩ is a stable model of ΠG then it is a P-stable model and T∪F=HBΠG. Thus, LI=Label′(I) is a complete labelling of G. Moreover, for each argument of G there is one and only one rule of ΠG whose any body’s atom has either the truth value t or f by I but never the value u. From the definition of the function Label′, it is easy to check that for each argument a in G, we have that L(I)(a) is either in or out but never undec. Thus L(I) is a complete labelling of G without arguments labelled undec, i.e., a stable labelling of G.

Semi-stable labelling – L-stable model

The proof is similar to that for the link between grounded (resp. preferred) labelling of G and well-founded (resp. M-stable) models of ΠG. □

References

[1]	J. Alcântara, S. Sá and J. Acosta-Guadarrama, On the equivalence between abstract dialectical frameworks and logic programs, Theory and Practice of Logic Programming 19: (5–6) ((2019) ), 941–956. doi:10.1017/S1471068419000280.
[2]	G. Alfano, S. Greco, F. Parisi and I. Trubitsyna, Defining the semantics of abstract argumentation frameworks through logic programs and partial stable models (extended abstract), in: Proc. of 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), (2016) , pp. 4735–4739.
[3]	G. Alfano, S. Greco, F. Parisi and I. Trubitsyna, On the semantics of abstract argumentation frameworks: A logic programming approach, Theory and Practice of Logic Programming 20: (5) ((2020) ), 703–718. doi:10.1017/S1471068420000253.
[4]	L. Amgoud, Stable semantics in logic-based argumentation, in: Proceedings of 6th International Conference on Scalable Uncertainty Management (SUM-12), (2012) , pp. 58–71. doi:10.1007/978-3-642-33362-0_5.
[5]	L. Amgoud, The outcomes of logic-based argumentation systems under preferred semantics, in: Proceedings of 6th International Conference on Scalable Uncertainty Management (SUM-12), (2012) , pp. 72–84. doi:10.1007/978-3-642-33362-0_6.
[6]	L. Amgoud and P. Besnard, Bridging the gap between abstract argumentation systems and logic, in: Proceedings of 3rd International Conference on Scalable Uncertainty Management (SUM-09), (1990) , pp. 12–27.
[7]	L. Amgoud and P. Besnard, A formal characterization of the outcomes of rule-based argumentation systems, in: Proceedings of 7th International Conference on Scalable Uncertainty Management (SUM-13), (2013) , pp. 78–91. doi:10.1007/978-3-642-40381-1_7.
[8]	L. Amgoud, C. Cayrol, M.C. Lagasquie-Schiex and P. Livet, On bipolarity in argumentation frameworks, International Journal of Intelligent Systems. Special issue: Bipolar representations of information and preference (Part 2. reasoning and learning) 23: (10) ((2008) ), 1062–1093.
[9]	L. Amgoud, C. Devred and M.C. Lagasquie-Schiex, Generating possible intentions with constrained argumentation systems, International Journal of Approximate reasoning 52: ((2011) ), 1363–1391. doi:10.1016/j.ijar.2011.07.005.
[10]	L. Amgoud, Y. Dimopoulos and P. Moraitis, Making decisions through preference-based argumentation, in: Proceedings of 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-08), (2008) , pp. 113–123.
[11]	L. Amgoud, S. Parsons and N. Maudet, Arguments, dialogue, and negotiation, in: Proceedings of 14th European Conference on Artificial Intelligence (ECAI-00), (2000) , pp. 338–342.
[12]	L. Amgoud and H. Prade, Using arguments for making and explaining decisions, Artificial Intelligence 173: ((2009) ), 413–436. doi:10.1016/j.artint.2008.11.006.
[13]	L. Amgoud and S. Vesic, A formal analysis of the role of argumentation in negotiation dialogues, Journal of Logic and Computation 22: (5) ((2012) ), 957–978. doi:10.1093/logcom/exr037.
[14]	P. Baroni, F. Cerutti, M. Giacomin and G. Guida, AFRA: Argumentation framework with recursive attacks, Int. J. Approx. Reasoning 52: (1) ((2011) ), 19–37. doi:10.1016/j.ijar.2010.05.004.
[15]	T. Bench-Capon and P. Dunne, Argumentation in artificial intelligence, Artificial Intelligence 171: ((2007) ), 619–641.
[16]	P. Besnard, E. Grégoire and B. Raddaoui, A conditional logic-based argumentation framework, in: Proceedings of 7th International Conference on Scalable Uncertainty Management (SUM-13), (2013) , pp. 44–56. doi:10.1007/978-3-642-40381-1_4.
[17]	P. Besnard and A. Hunter, Elements of Argumentation, The MIT Press, (2008) .
[18]	G. Betz, M. Hamann, T. Mchedlidze and S.V. Schmettow, Applying argumentation to structure and visualize multi-dimensional opinion spaces, Argument & Computation 10: ((2019) ), 23–40. doi:10.3233/AAC-181004.
[19]	G. Boella, D.M. Gabbay, V.D. Torre and S.L. Villata, Support in abstract argumentation, in: Proceedings of 3rd International Conference on Computational Models of Argument (COMMA-10), (2010) , pp. 40–51.
[20]	G. Brewka, S. Ellmauthaler, H. Strass, J.P. Wallner and S. Woltran, Abstract dialectical frameworks, in: Handbook of Formal Argumentation, M.G.P. Baroni, D. Gabbay and L. van der Torre, eds, College Publications, (2018) , pp. 237–285.
[21]	G. Brewka, S. Polberg and S. Woltran, Generalizations of Dung frameworks and their role in formal argumentation, intelligent systems, IEEE 29: (1) ((2013) ), 30–38.
[22]	G. Brewka and S. Woltran, Abstract dialectical frameworks, in: Proceedings of 12th International Conference on Principles Knowledge Representation and Reasoning (KR-10), (2010) , pp. 102–111.
[23]	P. Cabalar, S. Odintsov and D. Pearce, Logical foundations of well-founded semantics, in: Proceedings of 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-06), (2006) , pp. 25–35.
[24]	P. Cabalar, S. Odintsov, D. Pearce and A. Valverde, Analysing and extending well-founded and partial stable semantics using partial equilibrium logic, in: Proceedings of 22nd International Conference on Logic Programming (ICLP-06), (2006) , pp. 346–360.
[25]	P. Cabalar, S. Odintsov, D. Pearce and A. Valverde, Partial equilibrium logic, Annals of Mathematics and Artificial Intelligence 50: (3) ((2007) ), 305–331. doi:10.1007/s10472-007-9075-0.
[26]	E. Cabrio and S. Villata, Detecting bipolar semantic relations among natural language arguments with textual entailment: A study, in: Joint Symposium on Semantic Processing (JSSP-2013), (2013) , pp. 24–32.
[27]	E. Cabrio and S. Villata, A natural language bipolar argumentation approach to support users in online debate interactions, Argument & Computation 4: (3) ((2013) ), 209–230. doi:10.1080/19462166.2013.862303.
[28]	E. Cabrio and S. Villata, Abstract dialectical frameworks for text exploration, in: Proc. of 8th International Conference on Agents and Artificial Intelligence (ICAART 2016), (2016) , pp. 85–95.
[29]	M. Caminada, S. Harikrishnan and S. Sá, Comparing logic programming and formal argumentation; the case of ideal and eager semantics, Argument & Computation ((2021) , in press), 1–28.
[30]	M. Caminada, S. Sá, J. Alcântara and W. Dvor˘ák, On the equivalence between logic programming semantics and argumentation semantics, International Journal of Approximate Reasoning 58: ((2015) ), 87–111. doi:10.1016/j.ijar.2014.12.004.
[31]	M.W.A. Caminada, Semi-stable semantics, in: Proceedings of 1st International Conference on Computational Models of Argument (COMMA-06), (2006) , pp. 121–130.
[32]	M.W.A. Caminada, A labelling-based justification status of arguments, Studies in Logic 3: (4) ((2010) ), 12–29.
[33]	M.W.A. Caminada and D. Gabbay, Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Studia logica 93: (2–3) ((2009) ), 383–403. doi:10.1007/s11225-009-9210-5.
[34]	C. Cayrol, A. Cohen and M.C. Lagasquie-Schiex, Higher-order interactions (bipolar or not) in abstract argumentation: A state of the art, Journal of Applied Logics – IfCoLoG Journal of Logics and their Applications 8: (6) ((2021) ), 1339–1436.
[35]	C. Cayrol, J. Fandinno, L.F. del Cerro and M.C. Lagasquie-Schiex, Structure based semantics of argumentation frameworks with higher-order attacks and supports, in: Proc. of 8th Computational Models of Argument Conference (COMMA 2018), (2018) , pp. 29–36.
[36]	C. Cayrol, J. Fandinno, L.F. del Cerro and M.C. Lagasquie-Schiex, Argumentation frameworks with recursive attacks and evidence-based supports, in: Proc. of 10th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2018), (2018) , pp. 150–169.
[37]	C. Cayrol, J. Fandinno and M.C.L.-S.L. Fariñas del Cerro, Valid attacks in argumentation frameworks with recursive attacks, Ann. Math. Artif. Intell. 89: (1–2) ((2021) ), 53–101. doi:10.1007/s10472-020-09693-4.
[38]	C. Cayrol and M.C. Lagasquie-Schiex, On the acceptability of arguments in bipolar argumentation frameworks, in: Proceedings of 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU-05), (2005) , pp. 378–389. doi:10.1007/11518655_33.
[39]	C. Cayrol and M.C. Lagasquie-Schiex, Bipolar abstract argumentation systems, in: Argumentation in Artificial Intelligence, I. Rahwan and G. Simari, eds, (2009) , pp. 65–84. doi:10.1007/978-0-387-98197-0_4.
[40]	C. Cayrol and M.C. Lagasquie-Schiex, Coalitions of arguments: A tool for handling bipolar argumentation frameworks, Int. J. Intell. Syst. 25: (1) ((2010) ), 83–109. doi:10.1002/int.20389.
[41]	C. Cayrol and M.C. Lagasquie-Schiex, Bipolarity in argumentation graphs: Towards a better understanding, International Journal of Approximate Reasoning 54: (7) ((2013) ), 876–899. doi:10.1016/j.ijar.2013.03.001.
[42]	C. Cayrol and M.C. Lagasquie-Schiex, Logical encoding of argumentation frameworks with higher-order attacks and evidential supports, Int. J. Artif. Intell. Tools 29: (3–4) ((2020) ), 2060003:1–2060003:50.
[43]	A. Cohen, A.J. García and G.R. Simari, Backing and undercutting in defeasible logic programming, in: 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU-11), (2011) , pp. 50–61. doi:10.1007/978-3-642-22152-1_5.
[44]	A. Cohen, A.J. García and G.R. Simari, Backing and undercutting in abstract argumentation frameworks, in: Proceedings of 7th Int. Symp. on Foundations of Information and Knowledge Systems (FoIKS-12), (2012) , pp. 107–123. doi:10.1007/978-3-642-28472-4_7.
[45]	A. Cohen, S. Gottifredi, A.J. García and G.R. Simari, A survey of different approaches to support in argumentation systems, The Knowledge Engineering Review 29: (5) ((2014) ), 513–550. doi:10.1017/S0269888913000325.
[46]	A. Cohen, S. Gottifredi, A.J. Garcia and G.R. Simari, An approach to abstract argumentation with recursive attack and support, J. Applied Logic 13: (4) ((2015) ), 509–533. doi:10.1016/j.jal.2014.12.001.
[47]	S. Coste-Marquis, C. Devred and P. Marquis, Constrained argumentation frameworks, in: Proceedings of 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-06), (2006) , pp. 112–122.
[48]	M. Diller, A.K. Zafarghandi, T. Linsbichler and S. Woltran, Investigating subclasses of abstract dialectical frameworks, Argument & Computation 11: ((2020) ), 191–219. doi:10.3233/AAC-190481.
[49]	D. Dubois, J. Lang and H. Prade, Possibilistic logic, in: Handbook of Logic in AI and Logic Programming, D.M. Gabbay et al., eds, Vol. 3: , Oxford University Press, (1994) , pp. 439–513.
[50]	D. Dubois and H. Prade, Possibility theory: Qualitative and quantitative aspects, in: Handbook of Defeasible Reasoning and Uncertainty Management Systems, D.M. Gabbay and P. Smets, eds, Vol. 1: , Kluwer Academic, Dordrecht, (1998) , pp. 169–226.
[51]	D. Dubois and H. Prade, Generalized possibilistic logic, in: Proceedings of 5th International Conference on Scalable Uncertainty Management (SUM-11), (2011) , pp. 428–432. doi:10.1007/978-3-642-23963-2_33.
[52]	D. Dubois, H. Prade and S. Schockaert, Stable models in generalized possibilistic logic, in: Proceedings of 13th International Conference on Principles of Knowledge Representation and Reasoning (KR-12), (2012) , pp. 519–529.
[53]	P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77: (2) ((1995) ), 321–357. doi:10.1016/0004-3702(94)00041-X.
[54]	P.M. Dung and P.M. Thang, Representing the semantics of abstract dialectical frameworks based on arguments and attacks, Argument & Computation 9: ((2018) ), 249–267. doi:10.3233/AAC-180427.
[55]	U. Egly, S.A. Gaggl and S. Woltran, Answer-set programming encodings for argumentation frameworks, Argument and Computation 1: (2) ((2010) ), 147–177. doi:10.1080/19462166.2010.486479.
[56]	S.A. Gaggl, Towards a general argumentation system based on answer set programming, in: Proceedings of 26th International Conference on Logic Programming (ICLP-10), (2010) , pp. 265–269.
[57]	A. García and G. Simari, Defeasible logic programming: An argumentative approach, Theory and Practice of Logic Programming 4: (1) ((2004) ), 95–138. doi:10.1017/S1471068403001674.
[58]	M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in: Proceedings of 5th International Conference on Logic Programming (ICLP-88), (1988) , pp. 1070–1080.
[59]	M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Computing 9: ((1991) ), 365–385. doi:10.1007/BF03037169.
[60]	M.G.E. Gonzalez, M.C.D. Budán, G.I. Simari and G.R. Simari, Labeled bipolar argumentation frameworks, Artif. Injtell. Res. 70: ((2021) ), 1557–1636.
[61]	N. Gorogiannis and A. Hunter, Instantiating abstract, argumentation with classical logic arguments: Postulates and properties, Artificial Intelligence 175: ((2011) ), 1479–1497. doi:10.1016/j.artint.2010.12.003.
[62]	S. Gottifredi, A. Cohen, A.J. Garcia and G.R. Simari, Characterizing acceptability semantics of argumentation frameworks with recursive attack and support relations, Artificial Injtelligence 262: ((2018) ), 336–368. doi:10.1016/j.artint.2018.06.008.
[63]	N.L. Green, M. Branon and L. Roosje, Argument schemes and visualization software for critical thinking about international politics, Argument & Computation 10: ((2019) ), 41–53. doi:10.3233/AAC-181003.
[64]	S. Heras, J. Jordan, V. Botti and V. Julian, Argue to agree: A case-based argumentation approach, International Journal of Approximate Reasoning 54: ((2012) ), 82–108. doi:10.1016/j.ijar.2012.06.005.
[65]	A.C. Kakas, P. Moraitis and N.I. Spanoudakis, GORGIAS: Applying argumentation, Argument & Computation 10: ((2019) ), 55–81. doi:10.3233/AAC-181006.
[66]	D.C. Martínez, A.J. García and G.R. Simari, On acceptability in abstract argumentation frameworks with an extended defeat relation, in: 1st International Conference on Computational Models of Argument (COMMA-06), (2006) , pp. 273–278.
[67]	S. Modgil and M.W.A. Caminada, Proof theories and algorithms for abstract argumentation frameworks, in: Argumentation in Artificial Intelligence, Springer, (2009) , pp. 105–129. doi:10.1007/978-0-387-98197-0_6.
[68]	S. Modgil and H. Prakken, The ASPIC+ framework for structured argumentation: A tutorial, Argument and Computation 5: ((2014) ), 31–62. doi:10.1080/19462166.2013.869766.
[69]	F. Nouioua, Generalizing naive and stable semantics in argumentation frameworks with necessities and preferences, in: Proceedings of 6th International Conference on Scalable Uncertainty Management (SUM-12), (2012) , pp. 44–57. doi:10.1007/978-3-642-33362-0_4.
[70]	F. Nouioua, AFs with necessities: Further semantics and labelling characterization, in: Proceedings of 7th International Conference on Scalable Uncertainty Management (SUM-13), (2013) , pp. 120–133. doi:10.1007/978-3-642-40381-1_10.
[71]	F. Nouioua and V. Risch, Argumentation frameworks with necessities, in: Proceedings of 5th International Conference on Scalable Uncertainty Management (SUM-11), (2011) , pp. 163–176. doi:10.1007/978-3-642-23963-2_14.
[72]	N. Oren and T.J. Norman, Semantics for evidence-based argumentation, in: Proceedings of 2nd International Conference on Computational Models of Argument (COMMA-08), (2008) , pp. 276–284.
[73]	M. Osorio and J.C. Nieves, Range-based argumentation semantics as two-valued models, TPLP 17: (1) ((2017) ), 75–90.
[74]	D. Pearce, A new logical characterization of stable models and answer sets, in: Proceedings of Non-monotonic Extensions of Logic Programming (NMELP-1997), (1997) , pp. 57–70. doi:10.1007/BFb0023801.
[75]	S. Polberg, Understanding the abstract dialectical framework, in: Proc. of 15th European Conference on Logics in Artificial Intelligence (JELIA 2016), (2016) , pp. 430–446.
[76]	S. Polberg and D. Doder, Probabilistic abstract dialectical frameworks, in: Proc. of 14th European Conference on Logics in Artificial Intelligence (JELIA 2014), (2014) , pp. 591–599.
[77]	S. Polberg and A. Hunter, Empirical evaluation of abstract argumentation: Supporting the need for bipolar and probabilistic approaches, International Journal of Approximate Reasoning 93: ((2018) ), 487–543. doi:10.1016/j.ijar.2017.11.009.
[78]	S. Polberg and N. Oren, Revisiting support in abstract argumentation systems, in: Proceedings of 5th International Conference on Computational Models of Argument (COMMA-14), (2014) , pp. 369–376.
[79]	J.L. Pollock, Defeasible reasoning, Cognitive Science 11: (4) ((1987) ), 481–518. doi:10.1207/s15516709cog1104_4.
[80]	H. Prakken, On support relations in abstract argumentation as abstractions of inferential relations, in: Proceedings of 21st European Conference on Artificial Intelligence (ECAI-14), (2014) , pp. 735–740.
[81]	H. Prakken and G. Sartor, Argument-based extended logic programming with defeasible priorities, Journal of Applied Non-classical Logics 7: ((1997) ), 25–75. doi:10.1080/11663081.1997.10510900.
[82]	H. Prakken and G. Vreeswijk, Logics for defeasible argumentation, Handbook of Philosophical Logic 4: ((2002) ), 218–319.
[83]	T. Przymusinski, The well-founded semantics coincides with the three-valued stable semantics, Fundamenta Informaticae 13: (4) ((1990) ), 445–463. doi:10.3233/FI-1990-13404.
[84]	I. Rahwan and G.E. Simari, Argumentation in Artificial Intelligence, Springer, (2009) .
[85]	C. Sakama and T. Rienstra, Representing argumentation frameworks in answer set programming, Fundamenta Informaticae 155: (3) ((2017) ), 261–292. doi:10.3233/FI-2017-1585.
[86]	I. Sassoon, S. Zillessen, J. Keppens and P. McBurney, A formalisation and prototype implementation of argumentation for statistical model selection, Argument & Computation 10: ((2019) ), 83–103. doi:10.3233/AAC-181002.
[87]	G.R. Simari and R.P. Loui, A mathematical treatment of defeasible reasoning and its implementation, Artificial Intelligence 53: (2–3) ((1992) ), 125–157.
[88]	S.E. Toulmin, The Uses of Argument, Cambridge University Press, (1958) .
[89]	C. Trojahn, P. Quaresma and R. Vieira, An argumentation framework based on confidence degrees to combine ontology mapping approaches, International Journal of Metadata, Semantics and Ontologies 2: (3) ((2008) ), 142–150. doi:10.1504/IJMSO.2008.021892.
[90]	B. Verheij, The Toulmin argument model in artificial intelligence. Or: How semi-formal, defeasible argumentation schemes creep into logic, in: Argumentation in Artificial Intelligence, I. Rahwan and G. Simari, eds, (2009) , pp. 219–238. doi:10.1007/978-0-387-98197-0_11.
[91]	S. Villata, G. Boella, D.M. Babbay and L.W.N.V.D. Torre, Modelling defeasible and prioritized support in bipolar argumentation, Annals of Mathematics and Artificial Intelligence 66: ((2012) ), 163–197. doi:10.1007/s10472-012-9317-7.
[92]	R. Wannous and C. Trojahn, Explaining argumentation over alignment agreements, in: IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies, (2013) , pp. 80–85.
[93]	A.P. Young, S. Joglekar, G. Boschi and N. Sastry, Ranking comment sorting policies in online debates, Argument & Computation 12: ((2021) ), 265–285. doi:10.3233/AAC-200909.
[94]	X. Zhang, An approach to generating arguments over DL-Lite ontologies, Computing and Informatics 32: ((2013) ), 1001–1025.