You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Argumentation frameworks with necessities and their relationship with logic programs

Abstract

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

1.Introduction

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

Roughly speaking, works on argumentation may be divided into two classes. The first one is interested in the internal structure of arguments. We find in this class approaches that instantiate arguments from knowledge bases expressed in propositional logic [46,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,3841,44,46,47,6972]).

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 RA×A is a binary attack relation.

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

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 EA. E is conflict-free iff a,bE s.t. aRb; E defends an argument a iff bA, if bRa, then ERb; the characteristic function FH is defined by: FH:2A2A s.t. for EA, FH(E)={aAE defends a}; E is admissible iff E is conflict-free and aE, E defends a.

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

Definition 2.3

Definition 2.3(Acceptability semantics).

Let H=A,R be an AF and EA. 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+=AE); E is a semi-stable extension iff it is a complete extension s.t. EE+ 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.

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.

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:

a0a1,,am,not am+1,,not anwith 0mn
ai (0ain) are atoms. We read such a rule as follows: if a1am are true and none of the atoms am+1an 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.: aT iff I(a)=t, aF iff I(a)=f and aHB(TF) 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. fut and v{f,t,u}, vv. 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:a0a1,,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 aHB:

  • Ψ(I)(a)=t iff there is a rule aa1,,am,not am+1,,not an in Π s.t. I(ai)=t for all i s.t. 1im and I(aj)=f for all j s.t. m+1jn.

  • Ψ(I)(a)=u iff Ψ(I)(a)t and there is a rule aa1,,am,not am+1,,not an in Π s.t. I(ai)f for all i s.t. 1im and I(aj)t for all j s.t. m+1jn.

  • Ψ(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,FT,F iff TT and FF. 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 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

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. TF=HB (no atom is undefined).

  • I is an L-stable model of Π iff I is a P-stable model having the ⊆-maximal set TF 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.

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={pq;qp;st}. 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 II 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}=TF, 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}TF, 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}TiFi (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}TF, Π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, RA×A is a binary attack relation and N2A×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

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

Definition 3.2

Definition 3.2(closure under N1).

Let G=A,R,N be an AFN and EA. E is closed under N1 iff for each argument aE, if ENa for some EA, then EE.

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

Definition 3.3

Definition 3.3(N-cycle freeness).

Let G=A,R,N be an AFN, EA and aE. We say that a is N-Cycle-Free in E iff for all EA s.t. ENa, we have either EE= or there is bEE s.t. b is N-Cycle-Free in E. E is N-Cycle-Free iff every aE 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 EA. E is coherent iff it is closed under N1 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 EA. An argument aA is powerful in E iff aE and there is a sequence a0,,ak of elements of E s.t. ak=a; there is no EA s.t. ENa0 and for 1ik: for all EA, if ENai, then E{a0,,ai1}.

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

Proposition 3.6.

Let G=A,R,N be an AFN and EA. E is coherent iff each aE 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, EA and aE.

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

iff EA s.t. ENa and EA s.t. ENa, bEE, 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 EA. E is strongly coherent iff it is coherent and conflict-free.

Example 3.

Let us consider the four AFNs Gi=Ai,Ri,Ni (1i4) 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.

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 N1 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 N1 but not N-Cycle-Free, whereas the sets {b}, {c}, {a,b}, {c,d} are N-Cycle-Free but not closed under N1 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, EA and aA. We say that E defends a iff E{a} is coherent and for all bA, if bRa then for every coherent subset CA s.t. bC, 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 EA. The characteristic function of G is defined by FG:2A2A with FG(E)={aE 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 EA be a strongly coherent subset of arguments. The set of arguments deactivated by E is Ed={aif CA is a coherent subset s.t. aC 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 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 EA.

  • E is an admissible set iff it is strongly coherent and aE, E defends a.

  • E is a complete extension iff it is admissible and aA, if E defends a then aE.

  • 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 aAE, a is deactivated by E.

  • E is a semi-stable extension iff it is a complete extension and EEd 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 EA be a strongly coherent set.

  • (1) E is an admissible set iff EFG(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.

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)={aA|L(a)=in}, out(L)={aA|L(a)=out} and undec(L)={aA|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) bA, if bRa then bout(L) (all attackers of a are labelled out) and

    • (2) EA, if ENa then Ein(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 bA s.t. bRa and bin(L) (at least one attacker of a is labelled in) or

    • (2) EA, s.t. ENa and Eout(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) bA, if bRa then bin(L) (no attacker of a is labelled in) and

    • (2) EA, if ENa then Eout(L) (not all the arguments of any necessary set for a are labelled out) and

    • (3) either bA s.t. bRa and bout(L) or EA s.t. ENa and Ein(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 aA: if a is not powerful in A then aout(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, EA and L be a labelling of G.

  • If E is an admissible set of G then the labelling L=(E,Ed,A(EEd)) 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(EEd)) 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: G1G4.

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 aout(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 EA. 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,yA) 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 aA. A meta-argument associated to a is a minimal (w.r.t. set inclusion) coherent set CA 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,C2A, C1RC2 iff there is aC1 and there is bC2 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 aA. If a is not powerful in A, then CA s.t. aC.

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 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 EA is an admissible set (resp. a complete, the grounded, a preferred, a stable, a semi-stable extension) of G then ΓE={CaaE,Ca is a meta-argument associated to a and CaE} 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 (1Gi4) 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}A1An, each Ai contains p arguments (p>1) and AiNa (for 1in). Let H be the corresponding AF. The number of arguments in G is 1+p×n. Each set {a,b1,bn} s.t. biAi for 1in 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. aHead(Π). 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=FHBΠ.

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=FHBΠ.

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

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 aHBΠ:

  • 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)|rUND} 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)|rUND}.

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 xE 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 aA with EiNa. We associate to each Ei an atom (denoted ei) in ΠG. Thus, the Herbrand base of ΠG is HBΠG=AA where A={e1,,ep}.

  • For every argument aA, let b1,,bm be its attackers and let E1,,Ek be all the subsets of A s.t. EiNa for 0ik. The argument a gives rise in ΠG to the rule: ra:ae1,,ek,not b1,,not bm.

  • For every atom ei associated to a set Ei we add |Ei| rules as follows: for every xEi, the rule: eix 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 aA, 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 eA:

    • if there is a rule r:ea 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:ea 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:ea 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)=(TA,FA,A(TF)).

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.

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 N1. 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 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 baE. 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=cb 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 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 [2325]. 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: ERa. 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 EA be a coherent set. To prove that every argument aE 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) aE1, EA s.t. ENa (arguments of E1 does not require any other argument) and (3) for i>1, then aEi, EA s.t. ENa, E1j<iEi (the necessities on any argument of Ei are satisfied by the preceding sets E1,Ei1). Indeed if such a sequence is constructed, then for every argument aE, let aEi. 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,Ei1 (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={aEEA s.t. ENa}. We have E1 for if E1= then aE, EA s.t. ENa. Since E is closed under N1, EE. But this means that E is not coherent, contradiction.

Now, let E2={aEE1EA s.t. EE1= and ENa}. We have E2 for if E2= then aEE1, EA s.t. ENa and EE1=. Since E is closed under N1, EE, hence E(EE1) (because EE1=), 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 EA s.t. aE, a is powerful in E, i.e., aE, there is a sequence of arguments a0,,ak of E s.t. ak=a; there is no EA s.t. ENa0 and for 1ik: for all EA, if ENai, then E{a0,,ai1}.

It is straightforward from this definition that aE, if ENa for some EA, then EE, i.e., that E is closed under N1. From the definition (first item), it is clear that aE s.t. EA, aac--1-aac210028-i001.jpg. This condition implies that: aE s.t. EA, aac--1-aac210028-i002.jpg or EE. 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. aC.

    ) Let EA and let aE be a non powerful argument of E. Suppose that there is CE s.t. C is coherent and aC. 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 EA and aE 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,,akE s.t. ak=a; there is no EA s.t. ENa0 and for 1ik: for all EA, if ENai, then E{a0,,ai1}. It is then easy to check that the set {a0,,ak} is coherent. Contradiction.

  • a is not powerful in E iff EA s.t. ENa and EA s.t. ENa, bEE, b is not powerful in E.

    ) Let EA and a an argument which is not powerful in E. If we suppose that EA s.t. ENa, then clearly {a} is a coherent set containing a, contradiction. If we suppose that EA s.t. ENa and bEE s.t. b is powerful in E. Then, there is CE s.t. C is coherent and bC. It follows that C{a} is a coherent set too. But thus contradicts the fact that a is not powerful in E.

    ) Let EA and a an argument s.t.: EA s.t. ENa and EA s.t. ENa, bEE, b is not powerful in E. Suppose that a is powerful in E. Thus, there is CE s.t. C is coherent and aC. From the definition of coherence, for every EA s.t. ENa, EC, i.e., there exists bEE s.t. bC. 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 EA be a strongly coherent set.

  • (1) E is an admissible set iff EFG(E):

    ) Suppose that E is an admissible set. Thus, if aE then E defends a, i.e. aFG(E).

    ) Suppose that EFG(E). aE we have aFG(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 EFG(E). Now, let aFG(E). Then, a is defended by E but since E is a complete extension, aE. Thus FG(E)E, so FG(E)=E.

    ) Suppose that E=FG(E). Then EFG(E) and E is admissible (from point 1. of the current theorem). Now, let a be an argument defended by E, then aFG(E). Since FG(E)E, aE. 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 aA s.t. E defends a and aE. 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 EA be a stable extension. Then from the definition of stable extensions we have Ed=AE. Thus, EEd=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. EE then EdEd.

    Proof of Lemma 1.

    Let E and E be two complete extensions s.t. EE. Thus, any argument deactivated by E is clearly deactivated by E, hence EE. Now, suppose for the sake of contradiction that Ed=Ed. Let aEE. For every bRa, bEd because E defends all its elements. It follows that bEd, i.e. that E also defends a. But aE and this contradicts the fact that E is a complete extension. Then, it follows that EdEd. □

    Now, let EA be a semi-stable extension. Suppose for the sake of contradiction that E is not a preferred extension. Thus, there is EA s.t. EE and E is a complete extension. From the above lemma, it holds that EdEd. It follows that EEdEEd. 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(EEd)) 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 CA containing a (see proposition 3.7) which implies that aEd.

Let aE and show that a is legally in in L. Let b be an argument s.t. bRa. Clearly bE follows from conflict-freeness of E. Suppose that bA(EEd). Then, there exists a coherent set CA containing b and aac--1-aac210028-i003.jpg since bEd. This means that E does not defend a which contradict the fact that E is an admissible set. Thus bEd, i.e. bout(L). Now let EA s.t. ENa. From closure of E under N1, it holds that EE, i.e. Ein(L). Hence, a is legally in in L.

Now, let aEd and show that a is legally out in L (i.e. either ERa or EA s.t. ENa and EEd). To do so, let us suppose that EA s.t. ENa, EEd and prove that ERa. Then we have: EA s.t. ENa, bE s.t. bEd, i.e. there is a coherent set C containing b s.t. aac--1-aac210028-i004.jpg. Thus, we can construct a coherent set C satisfying EA s.t. ENa, CE and aac--1-aac210028-i005.jpg. But then the set C{a} is coherent too, and since aEd, it holds (from the definition of Ed) that ERC. Since aac--1-aac210028-i006.jpg, it must be the case that ER{a}. This means that every aEd 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,bE 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 aout(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., bE, but in this case, every coherent set C containing a is attacked by b, hence by E, i.e., aEd. The second case is that there is EA s.t. ENa and Eout(L). In this case either there is no coherent set containing a, so aEd or such coherent sets exists and every coherent set C containing a contains at least an argument bE. Since a1 is labelled out and is legally out we have again two cases: either ERa1 so ERC or there is E1A s.t. E1Na1 and E1out(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. aiC and ERai, i.e., each coherent set C containing a is attacked by E, hence aEd.

Now, for all aE, 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 bEd, 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(EEd)) is a complete labelling.

From the previous proof, it follows that every aE (resp. aEd) is legally in (resp. legally out). It remains to show that every argument aA(EEd) is legally undec.

Let aA(EEd). Thus, there is a coherent set C containing a s.t. aac--1-aac210028-i007.jpg. 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: EA s.t. ENa and Eout(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: bin(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: bA, if bRa then bout(L)=Ed and EA, if ENa then Ein(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 aE. This contradicts the fact that E is a complete extension. It follows that: every argument in A(EEd) 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 Edout(L).

Let us start by proving that Edout(L). Let aEd. 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 aout(L). Then, either ain(L) or aundec(L). ain(L) is impossible because in(L)=E. If aundec(L) then a is legally undec because L is a complete labelling. It follows from the definition of legally undec arguments that aac--1-aac210028-i008.jpg and EA s.t. ENa, Eout(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. aac--1-aac210028-i009.jpg. This contradicts the fact that aEd. So Edout(L).

Now let us suppose that there is aE, hence a is labelled either out or undec and E defends a, i.e., Ea is coherent and bA, if bRa then E attacks any coherent set of arguments containing b. It follows from this statement that: EA, if ENa then EE, i.e., Ein(L) and bA, if bRa then bEd, i.e. bout(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(EEd)) 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(EEd)) 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 EA s.t. EE and E is a complete extension. From the ) part of the proof for complete semantics, it follows that (E,Ed,A(EEd)) 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(EEd)) 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 EA s.t. EE and E is a complete extension. Then, from the ) part of the proof for complete semantics, it follows that (E,Ed,A(EEd)) 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(EEd)) is a stable labelling. if E is a stable extension, then from its definition: A(EEd)=. Since it is also complete, form the ) part of the proof for complete semantics, the labelling L=(E,Ed,A(EEd)=) 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=AE, i.e. E is a stable extension.

Semi-stable

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

From the ) part of the proof for complete semantics, it follows that L=(E,Ed,A(EEd)) 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)(EEd). 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. (EEd)(EEd). From the ) part of the proof for complete semantics, it follows that L=(E,Ed,A(EEd)) is a complete labelling. Moreover, it is easy to check that (EEd)(EEd) 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 EA be an admissible set of G and let ΓE be the set of subsets of arguments defined by: ΓE={CaaE,CaE 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. CaRCb, i.e., there is aCa and bCb s.t. aRb. But since Ca,CbE, a,bE. Contradiction with the fact that E is conflict-free.

Let CaΓE be a meta-argument of an argument aE. Let CbΓE be a meta-argument of an argument bAE and CbRCa. From the definition of R, it follows that there is b in Cb, hence in AE and there is a in Ca, hence in E s.t. bRa. Since E defends all its elements. Namely, E defends a against b. So, for every coherent set C containing b there is cE 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 aE, bE and bRa. Then for every meta argument CbΓ associated to b and every meta-argument CaΓ associated to a, it holds that: CbRCa. Since Γ is admissible, there is a meta-argument CΓ s.t. CRCb, 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 EA be a complete extension of G and let ΓE be the set of subsets of arguments defined by: ΓE={CaaE,CaE 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 aE defended by ΓE, i.e., C s.t. CRCa, ΓERC.

First, let us precise that a first consequence of our hypotheses is that ΓE{Ca} is conflict-free. Indeed if we suppose that ΓERCa 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, ΓERCa 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 a0Ca s.t. there is no EA with ENa0. Ea0 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 CbRCa. Since ΓE defends Ca it follows that ΓERCb. 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 ΓERC, i.e. ERC. This means that E defends a0E. 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 aEΓ 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 aEΓ 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. CbRCa then two cases are possible. The first case is that CbRa with aa hence aEΓ, then there is at least a meta-argument associated to a in Γ. Consequently, CbRΓ. But since Γ is admissible it follows that ΓRCb. The second case is that CbRa,i.e., there is bCb s.t. bRa. 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. CRCb. 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 EEΓ 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 EEΓ 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 EEΓ 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 EEΓ 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 aE s.t. aac--1-aac210028-i010.jpg. Thus, there is an argument aE and a coherent set Ca containing a s.t. aac--1-aac210028-i011.jpg. 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 aEΓ and a coherent set C containing a s.t. aac--1-aac210028-i012.jpg. This means, there exists a meta-argument CaC 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 CaC containing a always exists) s.t. CaΓ and aac--1-aac210028-i013.jpg. 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)(EEd). 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 EA s.t. E is a complete extension of G and (EEd)(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 (EEd)(EΓEΓd) it is easy to check that (ΓEΓEd)ΓΓ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Π(TF)=HBΠ(TF). □

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ΠaHead(Π) for some aBody+(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 aHead(Π) for some aBody(r)}. Then, clearly Π=Π1Π3 where Π3 is obtained from Π3 by removing any expression not a s.t. aHead(Π). Let ΠI (resp. ΠI) be the generalized reduct of Π (resp. of Π) by I (resp. by I). Then, ΠI=Π1IΠ2IΠ3I and ΠI=Π1IΠ3I where Π1I (resp. Π2I, Π3I, Π1I, Π3I) 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 Π3I 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 n0, Tn=Tn and Fn=FnHBΠ. 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 aHBΠ s.t. In+1(a)=t, then there is a rule r:aa1,,ak in ΠI s.t. for all ik, 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