Characterizing Argumentation Frameworks with an Extension*

Kang Xu Beishui Liao

Abstract. According to a given criterium,from the structure of an argumentation framework,a set of extensions can be decided.Conversely,an extension or a set of extensions can identify a set of argumentation frameworks.The direction from argumentation frameworks to their semantics has been discussed a lot,but little attention has been paid to the opposite direction.In this paper,we focus on characterizing argumentation frameworks with a given set of arguments as an extension,and show its applications on the update of argumentation frameworks and monotony.

1 Introduction

Formal argumentation is a very active research area in the field of knowledge representation and reasoning,in which Dung’s abstract argumentation([11])has been extensively studied in the past two and a half decades,including argumentation semantics([20,1]),algorithms([15,19]),computational complexity([14,13]),dynamics([3,7]),etc..

An abstract argumentation framework can be modeled as a graph(A,R),whereArepresents a set of arguments andR ?A×Aa binary relation called “attack”.Given such a graph,an interesting question is which sets of arguments,i.e.extensions,can reasonably be accepted.This question is stated as semantics that is a function from an argument graph to a set of extensions.There is a rich variety of semantics,defined in terms of intuitions and principles([1]),each of which represents a kind of attitude to select acceptable arguments in practice.

Example 1.AF1is an argumentation framework illustrated in Figure 1.Argumentsaandcare accepted simultaneously under grounded semantics wich represents a caucious choice.Then{a,c}is the grounded extension ofAF1.The semantics ofAF1is a mapping fromAF1to{{a,c}}.

Figure 1 :Argumentation frameworks

Conversely,from an extension or a set of extensions,a set of argumentation frameworks can be decided.

Example 2.LetE1={a,c}be a set of arguments.There are infinite argumentation frameworks that haveE1as the grounded extension.All of them can be put in a set,denoted asAF1andAF2illustrated in Figure 1 are two argumentation frameworks inThe direction from argumentation frameworks to semantics has been discussed a lot([20,1,15,19]),but little attention has been paid to the opposite direction from semantics to frameworks.Example 2 gives rise to a research question:Given a setEof arguments,under grounded semantics,what kinds of conditionsshould satisfy? It can be seen from the structures of bothAF1andAF2that one argument inEis unattacked,and it can be seen more from the structure ofAF2that the circle identified by{a,d}is attacked bycinE.There should be a precise characterization ofthat covers all of these conditions.We will discuss this problem in this paper,and will focus on characterizing the set of argumentation frameworks with an extension or a set of extensions.

In our previous works([17]),we simplifed the computation of semantics of probabilistic argumentation by characterizing subgraphs.After that,we introduced this idea to“enforcement”,one question of the dynamics of argumentation frameworks.Enforcement is to change an argumentation framework to make a set or sets of arguments accepted.Baumann et al.firstly investigated whether enforcing an extension is possible in [4].We discussed the conditions under which an enforcement achieves([22,21]).In[22],we classified the change of an argumentation framework into two directions:expansion and contraction.The expansion of an argumentation framework is defined by adding arguments or attacks to the framework.The contraction of an argumentation framework is defined by deleting arguments or attacks from the framework.We formulated methods to expand or contract argumentation frameworks to enforce an extension under complete,grounded,preferred and stable semantics respectively.In[21],we discussed how to update an argumentation framewok to enforce an extension under complete,grounded,preferred and stable semantics,where updating an argumentation framework is not to change it in one direction,i.e.,either expansion or contraction,but to form a new framework.

The way of characterizing subgraphs in [17] sparks an idea of characterizing argumentation frameworks from a fixed extension or a set of extensions.“Enforcement” in [22] and [21] provides methods to do the characterization of frameworks.This paper is motivated by these two points and to be an extension of [21] which incorporates the principle behind the enforcement in[21]and the idea of characterizing frameworks.It shows the relations between the structures of argumentation frameworks and some semantics,making a progress on the research direction from semantics to frameworks.Furthermore,it can be applied to the dynamics of argumentation frameworks which are about the interaction between the change of frameworks and that of semantics.

The structure of this paper is as follows.Section 2 introduces some basic notions of abstract argumentation.Section 3 is the main part of this paper,studying the characterization of argumentation frameworks with a given extension,and a given set of extensions.Section 4 shows the applications of our work to updating argumentation frameworks and monotony.Section 5 concludes.

2 Preliminaries

2.1 Argumentation frameworks

To make this paper self-contained,in this section,we introduce some basic notions on the abstract argumentation,including argumentation frameworks and their semantics.We consider only finite argumentation frameworks for the sake of simplicity,and all presentations here are adjusted to the studies in the following sections.

Definition 1.LetUbe the universe of all possible arguments.An argumentation frameworkGis a tuple(A,R)whereAis finite,A ?UandR ?A×Ais a binary relation onA.

LetB ?AandRB=R∩(B×B).(B,R*)is a sub-framework ofGifB ?AandR* ?RB.G ↓B=(B,RB)is the restriction ofGtoB,and it is a sub-framework ofG.

Givena,b ∈A,(a,b)∈Rmeansaattacksb.We writeaRbinstead of(a,b)∈R,andinstead of (a,b)R.GivenB,C ?A,we sayBRa(respectively,aRB)if there existsb ∈Bsuch thatbRa(respectively,aRb),andBRCif there existb ∈Bandc ∈Csuch thatbRc.

We useto denote the indirect relation between two arguments:if there exist a series of argumentsx1,x2,...xnsuch thataRx1,x1Rx2,...,andxnRb.

Circles play a key role to dicide the content of an extention and the number of extensions of an argumentation framework.It is defined as follows.

Definition 2.LetG=(A,R)be an argumentation framework,andB ?A.G ↓Bis a circle ofGif and only if for any argumentsa,b ∈B,The set of all circles ofGis denoted asCIRG,and the set{B|G ↓Bis a circle ofG}is denoted asSCIRG.

Example 3.LetAF3be an argumentation framework illustrated in Figure 2.={AF3↓{a,b},AF3↓,AF3↓{c,d}}andSCIRAF3={{a,b},,{c,d}}.

Figure 2 :An argumentation framework

The notion of circle is different from that of strongly connected component of an argumentation framework in[2].

Definition 3.LetG=(A,R)be an argumentation framework,PEGis a relation onAand satisfies:

· for anyx ∈A,(x,x)∈PEG?

· for anyx,y ∈Awithx／=y,(x,y)∈PEGif and only if

PEGis an equivalence relation and we call it the relation of path-equivalence.Leta ∈A.The equivalence class ofamoduloPEGis a strongly connected component ofG.The set of strongly connected components ofGis denoted asSCCSGand it is a partition ofA.

It can be seen from Definitions 2 and 3 that any cyclic graph of a strongly connected component is a circle,but not vice versa.ConsideringAF3in Example 3,={{a,b},{c,d},{e},{f}}in which two subframeworks induced by{a,b}and{c,d}depict circles ofAF3.

All circles in an argumentation framework make a contribution to the constitution of semantics,while the strongly connected components in a framework have some relations to the properties of semantics([2]).

2.2 Semantics of argumentation

Given an argumentation framework,a fundamental problem is to determine which arguments can be regarded as collectively acceptable.There are mainly two approaches:extension-based approach and labelling-based approach.The idea underlying the extension-based approach is to identify sets of arguments,called extensions,that can be accepted according to a given criterion.The idea underlying the labellingbased approach is to assign a label to each argument according to a given criterion.

The extension-based approach starts from the notions of conflict-freeness and defense.

Definition 4.LetG=(A,R) be an argumentation framework,a,b ∈ AandE ?A.

·Eis conflict-free if and only if for anya,b ∈E,

·Edefendsaif and only if for anybRa,ERb.

The set of all arguments defended by a subset ofAcan be denoted by the characteristic function ofG.The characteristic function makes a contribution to symplify the definitions in the extension-based approach.

Definition 5.The characteristic function of an argumentation frameworkG=(A,R)isF:2A2A,where for anyB ?A,F(B)={a ∈A|Bdefendsa}.

Based on conflict-freeness and the characteristic function,a set of extensions can be defined as follows([6,9,15]).

Definition 6.LetG=(A,R)be an argumentation framework,a ∈AandE ?A.

·Eis an admissible set if and only ifEis conflict-free andE ?F(E)?

·Eis a complete extension ofGif and only ifEis conflict-free andE=F(E)?

·Eis the grounded extension ofGif and only ifEis the minimal complete extension(with respect to set inclusion)?

·Eis a preferred extension ofGif and only ifEis a maximal admissible set(with respect to set inclusion)?

·Eis a stable extension ofGif and only ifEis admissible andER(AE)?

·Eis the ideal extension ofGif and only ifEis the maximal admissible extension(with respect to set inclusion)contained in all preferred extensions ofG.

The labelling-based approach is defined in terms of labellings.A labelling is a function assigning a label to each argument of an argumentation framework to indicate its status.There are usually three labels:in,outandundec.The labelinindicates that the argument is accepted,outindicates that the argument is rejected andundecindicates that the argument is undecided which means that it can not be decided to be accepted or rejected([1]).

Definition 7.LetG=(A,R)be an argumentation framework.The labelling ofGis a total functionL:in,out,undec}.

Letin(L)={a ∈A | L(a)=in},out(L)={a ∈A | L(a)=out}andundec(L)={a ∈A | L(a)=undec}.Lis often represented as a triple(in(L),out(L),undec(L)).

LetB ?A.L ↓B=(in(L)∩B,out(L)∩B,undec(L)∩B) is called the restriction ofLtoB.

The central criterion for labelling-based approach is legality.

Definition 8.LetG=(A,R)be an argumentation framework,a ∈A,andLbe a labelling ofG.

·L(a)=inis legal if and only if for anyb ∈A,bRaimpliesL(b)=out?

·L(a)=outis legal if and only if there existsb ∈Asuch thatbRaandL(b)=in?

·L(a)=undecis legal if and only if the above two cases are unsatisfied,i.e.

-there existsb ∈Asuch thatbRaandL(b)／=out?

-for anyc ∈A,ifcRathenL(c)／=in.

Based on Definition 8,various kinds of labellings can be defined as follows.

Definition 9.LetG=(A,R)be an argumentation framework,andLbe a labelling ofG.

·Lis an admissible labelling if and only if arguments inin(L)andout(L)are legally labeled byL?

·Lis a complete labelling if and only if it is admissible,and arguments inundec(L)are legally labeled byL?

·Lis the grounded labelling if and only if it is complete,andin(L)is minimal(with respect to set inclusion)among all complete labellings ofG?

·Lis a preferred labelling if and only if it is admissible,andin(L)is maximal(with respect to set inclusion)among all admissible labellings ofG?

·Lis a stable labelling if and only if it is complete,andundec(L)=??

·Lis the ideal labelling if and only if it is the maximal admissible labelling that is smaller than or equal to each preferred labelling(with respect to set inclusion).Here,we say that a labellingLis smaller than or equal to another labellingL′if and only ifin(L)?in(L′).

In this paper,we usead,co,pr,gr,standidto denote admissible,complete,preferred,grounded,stable and ideal respectively,and useσto represent one of them,i.e.σ ∈{ad,co,pr,gr,st,id}.The set of allσ-extensions(sets)ofGis denoted asEσ(G).The set of allσ-labellings onGis denoted asLσ(G).

The relation between labellings and extensions is:for anyσ-labelling ofG,there is aσ-extension(set)Esuch thatE=in(L)?for anyσ-extension(set)EofG,there is aσ-labelling such thatE=in(L)([1]).In the following part of this paper,we callin(L)aσ-extension(set)whileLis aσ-labelling.

It is not the case for eachσin{ad,co,pr,gr,st,id}that theσ-labellings are in one-to-one correspondence to theσ-extensions(sets)of an argumentation framework.ad-labellings are not uniquelly identified by theirinlabeled part,but it does hold forco-labellings([12]).The following proposition indicates this unique identification forco-labellings.

Proposition 1.Let G=(A,R)be an argumentation framework,and L1,L2be colabellings of G.It holds that:

·in(L1)?in(L2)if and only ifout(L1)?out(L2);

·in(L1)?in(L2)if and only ifout(L1)?out(L2).

2.3 Directionality and sub-frameworks

Directionality is a property of semantics with respect to the structures of argumentation frameworks.In this paper,we adopt the definition based on the labellingbased approach in[1].

Definition 10.LetG=(A,R)be an argumentation framework,andB ?A.Bis unattacked if and only if there is no argumenta ∈ABsuch thataRB.

Definition 11.A semanticsσis directional if and only if for any argumentation frameworkGand for any set of argumentsBwhich is unattacked,Lσ(G)↓B=Lσ(G ↓B),whereLσ(G)↓B={L ↓B |L ∈Lσ(G)}.

In[15],Liao et al.calledG ↓BwithBunattacked unconditioned sub-framework ofG,otherwise conditioned sub-framework.Furthermore,they proposed the partially labeled sub-framework which is a combination of a conditioned sub-framework and its outside attackers.In this paper,we stick “partially labeled” to sub-frameworkG ↓B.

Definition 12.LetG=(A,R) be an argumentation framework,andB ?A.A partially labeled sub-framework ofGis denoted as(G ↓B)L,whereLis a labelling covers all attackers outsideG ↓B.

In Definition 12,we do not restrict the attackers outsideBto be nonempty,which is different from[15].The legality of labellings for a partially labeled sub-framework needs to incorporate the labels of its external attackers if there are.

Definition 13.LetG=(A,R) be an argumentation framework,B ?A,a ∈BandL*be a labelling of(G ↓B)L.

·L*(a)=inis legal if and only if for anyb ∈AB,bRaimpliesL(b)=out,and for anyc ∈B,bRaimpliesL*(c)=out?

·L*(a)=outis legal if and only if there existsb ∈AB,such thatbRaandL(b)=inor there existsb ∈B,such thatbRaandL*(b)=in?

·L*(a)=undecis legal if and only if the above two cases are unsatisfied.

The definitions ofad,co,gr,prandid-labellings of a partially labeled subframework are defined as follows.

Definition 14.LetG=(A,R)be an argumentation framework,B ?AandL*be a labelling of(G ↓B)L.

·L*is anad-labelling of (G ↓B)Lif and only if all arguments inin(L*) andout(L*)are legally labeled byL*?

·L*is aco-labelling of (G ↓B)Lif and only if it is anad-labelling,and all arguments inundec(L*)are legally labeled byL*?

·L*is thegr-labelling of(G ↓B)L,if and only ifL*is aco-labelling,andin(L*)is minimal(with respect to set inclusion)among all co-labellings of(G ↓B)L?

·L*is apr-labelling of(G ↓B)Lif and only ifL*is anad-labelling,andin(L*)is maximal(with respect to set inclusion)among all ad-labellings of(G ↓B)L?

·L*is an st-labelling of(G ↓B)Lif and only if it is a co-labeling,andundec(L)=??

·L*is theid-labelling of(G ↓B)Lif and only if it is the maximalad-labelling that is smaller than or equal to eachpr-labelling of (G ↓B)L(with respect to set inclusion).

Example 4.AF3↓{a,b}andAF3↓{e,f}are two sub-frameworks ofAF3(see Figure 2).AF3↓{a,b}is unconditioned,and given any labellingL,Lco((AF3↓{a,b})L)={({a},,?)}.

AF3↓{e,f}is conditioned,and is attacked outside bycandd.SupposeL1=({c},j5i0abt0b,?),L2=(j5i0abt0b,{c},?),andL3=(?,?,{c,d}),then we have:

If a sub-framework is attacked outside by arguments that are all labeledout,then its semantics is imprevious.The following theorem shows this condition.

Theorem 2.σ ∈{ad,co,gr,pr,st,id}.Let G=(A,R)be an argumentation framework,B,C ?A,and C={c ∈A|c/∈B and cRB}.If there is a labelling L on C such that for any c ∈C,L(c)=out,then Lσ((G ↓B)L)=Lσ(G ↓B).

It is easy to prove Theorem 2 by Definitions 13 and 14.

3 Characterizing Argumentation Frameworks

In this section,we will discuss how to characterizeσ-argumentation frameworks with an extension.This kind of conditioned argumentation frameworks are defined followingσ-subgraphs with respect to an extension proposed in[17].Aσ-subgraph with respect to an extension is a sub-framework that has a fixed set of arguments as aσ-extension.For example,AF2,AF2↓{a,b,c},AF2↓{a,d,c}andAF2↓{a,c}are allgr-subgraphs ofAF2with respect to{a,c}(see Figure 1).

Aσ-argumentation framework with an extension is defined as follows.

Definition 15.LetG=(A,R) be an argumentation framework.IfEis aσextension ofG,then we callGaσ-argumentation framework withE.is used to denote the set of allσ-argumentation frameworks withE.

AF1andAF2illustrated in Figure 1 are twogr-argumentation frameworks with{a,c}.AF3illustrated in Figure 2 is aco-argumentation framework with{a,c,f}.

Eis the key point to the construction ofGinTwo factors related toEjointly make a contribution to this construction:arguments that attackEand arguments that are attacked byE.In the remaining part of this paper,the following sets related toEwithin any argumentation frameworkG=(A,R) will be frequently used,which are previously presented in[17].={x ∈AE|xRE},denoting the set of arguments inAthat attacksE?={x ∈AE|ERx},denoting the set of arguments inAthat is attacked byE?denoting the set of arguments inAthat attackEbut is not attacked byE?denoting the set of arguments inAwhich is unrelated toE(neither attacks nor is attacked byE).

E,make a partition ofA,and determine whetherGis aσ-argumentation framework withE.

The following parts of this section show the characterizations of argumentation frameworks with an extension under complete,grounded,preferred and stable semantics.

3.1 Complete semantics

Before discussing argumentation frameworks inwe first show how anad-argumentation framework withEis.

Given an argumentation frameworkG,ifGis anad-argumentation framework withE,then there exists an ad-labellingLofGsuch thatin(L)is equal toE.Alladsets are conflict-free,then any two arguments inEdo not attack each other.According to Definition 9,arguments inin(L)andout(L)should be legally labeled.This implies that all arguments inare labeledoutbyL.According to Definition 8,any argument labeledoutis attacked by at least one argument labeledin.Then it can be concluded thatEattacks,i.e.is included in

Theorem 3.Let G=(A,R)be an argumentation framework,and E ?A.G ∈if and only if

From Theorem 3,thatis included inand thatEis conflict-free are not only sufficient but also necessary conditions forGbeing anad-argumentation framework withE.

Example 5.LetE2={a,d}.According to Theorem 3,AF4illustrated in Figure 3 is anad-argumentation framework withE2.

Figure 3 :An ad-argumentation framework with E2

Figure 4 : co-argumentation frameworks with E2

On the basis of Theorem 3,aco-argumentation framework withEcan be described as follows.

Theorem 4.Let G=(A,R)be an argumentation framework,and E ?A.G ∈if and only if

Comparing with Theorem 3,Theorem 4 adds a new condition onwhich makes sure that all arguments unrelated toEare legally labeledundec.Theorem 4 provides sufficient and necessary conditions forGbeing aco-argumentation framework withE.

3.2 Grounded semantics

IfGis agr-argumentation framework withE,then there is agr-labelling ofG,sayL,such thatin(L)is equal toE.As thegr-labelling is also complete,Gfirst is aco-argumentation framework withE.Then we know thatEis conflict-free,is included inis self-attacked.As the grounded extension is the minimal complete extension,Gshould have no otherco-extension that is properly included inE.This implies that the sub-frameworkshould not have arguments that can be labeledundec,i.e.is thegr-labeling ofG

SupposeGis aco-argumentation framework withE,andis thegrlabelling ofthenis aco-labelling ofG,and there is no smallerco-extension ofGthanE.Thenbecomes thegr-labelling ofG,andGis agr-argumentation framework withE.

In[19],Modgil and Caminada provided an algorithm to compute thegr-labelling of an argumentation framework.The algorithm started by assigninginto all arguments that are unattacked,and then iteratively assignoutto any argument that is attacked by an argument which has been assignedin,andinto those arguments whose attackers are all assignedout.The iteration continues until no more new arguments can be assignedinorout,then all the arguments left are assignedundec.In this process of assignment,for any circle,if it is unattacked or attacked only by arguments assignedout,then all arguments in it can only be decided to beundec.But if it is attacked by arguments assignedin,then some arguments in this circle can be decided to beinorout.

Example 7.are argumentation frameworks with circles(see Figure 5).The assigning process of grounded semantics foris:a(in)→b(out)→c(undec).The assigning process of grounded semantics foris:a(in)→b(out)→c(in).

Figure 5 :Argumentation frameworks with circles

Figure 6 :A gr-argumentation framework with E2

Based on Theorem 4 and the algorithm of computinggr-labellings,agr-argumentation framework withEcan be described as follows.

Theorem 5.Let G=(A,R)be an argumentation framework,and E ?A.G ∈if and only if

3.3 Preferred semantics

The following theorem shows how to characterize argumentation frameworks in

Theorem 6.Let G=(A,R)be an argumentation framework,and E ?A.G ∈if and only if

3.4 Stable semantics

Based on Theorem 3,argumentation frameworks inare constructed as follows.

Theorem 7.Let G=(A,R)be an argumentation framework,and E ?A.G ∈if and only if

Theorem 7 provides sufficient and necessary conditions forGbeing anst-argumentation framework withE.

Example 10.E2={a,d}.AF4in Figure 3 is anad-argumentation framework withE2.One of thead-labellings ofAF4is({a,d},{b,e},{c,f}).Since={c,f},then from Theorem 7,AF4is not anst-argumentation framework withE2.andillustrated in Figure 7 are qualified argumentation frameworks in

Figure 7 : st-argumentation frameworks with E2

Figure 8 :The update of AF1 to enforce E3

We call all above theorems for the characterizations of argumentation frameworks inchracterizing theorems,whereσ ∈{ad,co,gr,pr,st}.

3.5 Properties of σ-argumentation frameworks with E

There is a series of inclusion relations between admissible sets,complete,grounded,preferred,stable and ideal extensions of an argumentation framework.They actually indicate a kind of ordering on these semantics if we treat“admissible”also as a kind of semantics.

Definition 16.Letσandτbe two kinds of semantics,andbe a relation between them.if and only if for any argumentation frameworkG,for anyE ∈Eσ(G),E ∈Eτ(G).

The fact that every stable extension is also a preferred extension was first stated in[18].All other relations between admissible sets,complete,grounded and preferred extensions have originally been stated in[11].Meanwhile,as proved in[8],an ideal extension is also a complete extension.All these indicates thatis an odering on admissible,complete,grounded,preferred,stable and ideal semantics:

Given a set of argumentsE,this odering implies inclusion relations between corresponding sets of argumentation frameworks withE.

Theorem 8.Let E be a set of arguments.Then we know that:

The definitions ofmakes a clear clue to prove Theorem 8.

At last,we extend the chatacterization ofσ-argumentation frameworks with a single extension to a set of extensions.

Theorem 9.Let G=(A,R)be an argumentation framework,and B={B |B ?A}.B ?Eσ(G)if and only if G ∈∩{|E ∈B}.

Theorem 9 can be proved directly from the definition of

4 Applications

In this section,we will discuss two applications of our work in Section 3 on the dynamics of argumentation frameworks.One application is updating an argumentation framework to enforce an extension.The other one is monotony.

4.1 Updating an argumentation framework to enfroce an extension

Updating an argumentation framework is to change the set of arguments and the attack relation of this tuple.In [16],Liao et al.treated it as an operation between an arguementation framework and a set of arguments and attacks.In this paper,we adopt the perspective that updating an argumentation framework is adding arguments or attacks to it,or deleting arguments or attacks from it,and after revising,it still becomes an argumentation framework.

Definition 17.LetG=(A,R)be an argumentation framework.The update ofGis an argumentation frameworkG′=(A′,R′),andG′satisfies

·A′=(AB)∪CwhereB ?AandC ∩(AB)=??

·R′=(RR1)∪R2whereR1andR2are two binary relations,(A×B)∪(B×B)∪(B×A)?R1andR2?A′×A′.

Updating an argumentation framework to enforce an extension,sayE,means updating an argumentation framework in such a way thatEbecomes one of its extensions.In[4],Baunman et al.have found the sufficient conditions for expanding an argumentation framework,i.e.adding arguments or attaks to it,to enforce an extension.In this paper,each characterizing theorem in Section 3 provides a way to update an argumentation framework,either expanding or restricting,to enforce aσ-extension whereσ ∈{co,gr,pr,st}.

Theorems 4,5 and 7 show direct ways to update an argumentation framework to enforce a complete,grounded and stable extension,respectively.

Theorem 6 shows an indirect way to update an argumentation framework to enforce a preferred extension.

Example 12.E3={a},andE3is not apr-extension but anad-set ofAF2(see Figure 1).is an updated argumentation framework ofAF2to enforceE3as apr-extension(see Figure 9).is formed by addinge,(e,c),(b,e)toAF2,where={b,c,e}and there is no arguments in it can be labeledin.

Figure 9 :The update of AF2 to enforce E3

Examples 11 and 12 show how to update an argumentation framework to enforce an extension.The general rules of these updates under complete,grounded,stable and preferred semantics are displayed in[21],and each rule corresponds to a characterizing theorem of the same semantics in Section 3.The ways to update argumentation frameworks in Examples 11 and 12 conform to the rules in [21],while the resulted frameworks satisfy the characterizing theorems.

4.2 Monotony

Monotony is an important conception in mathematics and logic.In abstract argumentation,monotony is a kind of property of the update from an argumentation framework,sayG,to the other one,sayG′,that represents the monotonic change of accepted arguments.In[10],Cayrol et al.proposed monotony,credulous monotony and skeptical monotony.Monotony indicates each extension ofGis included in at least one extension ofG′.Credulous monotony indicates the union of the extensions ofGis included in the union of the extensions ofG′.Skeptical monotony indicates the intersection of extensions ofGis included in the intersection of extensions ofG′.In[5],monotony is classified as expansive monotony and restrictive monotony.The update fromGtoG′is expansive monotony if every argument accepted inGis still accepted inG′,i.e.no accepted argument is lost or there is an expansion of acceptability.The update fromGtoG′is restrictive monotony if every argument accepted inG′was already accepted inG,i.e.no new acceptable arguments appear or there is a restriction of acceptability.In[4],monotony means that arguments accepted in the original argumentation framework survive,and the number of extensions can not decrease after updating.

In this paper we discuss some relations between theσ-argumentation frameworks with an extension and the monotonies proposed in[5].The definition of monotonies is defined as follows.

Definition 18.LetG=(A,R)andG′=(A′,R′)be argumentation frameworks.

· The update fromGtoG′is expansiveσ-monotony if and only if for anyσextensionEofG,there is aσ-extensionE′ofG′such thatE ?E′.

· The update fromGtoG′is restrictiveσ-monotony if and only if for anyσextensionEofG,there is aσ-extensionE′ofG′such thatE ?E′.

Theσ-argumentation framework with an extension can be used to show the conditions for monotony.

From Definition 6,we know that?is an ordering on the set ofco-extensions of an argumentation framework.If all the maximalco-extensions,i.e.allpr-extensions of the original argumentation frameworkGsurvive in the updated argumentation frameworkG′,then allco-extensions survive.Then the expansive monotony under complete and preferred semantics are satisfied.Since both thegr-extension and theid-extension are unique in a framework,then the expansive monotony under grounded and ideal semantics are satisfied if the correspondinggrandid-extensions survives.

The following theorem uses the set ofσ-argumentation frameworks with an extension to show some sufficient conditions for expansive monotony.

Theorem 10.Let G=(A,R)and G′=(A′,R′)be argumentation frameworks.

· If G′ ∈∩{|E ∈Epr(G)},then the update from G to G′ is expansive co and pr-monotony.

· If G′ ∈where E ∈Eid(G),then the update from G to G′ is expansive grand id-monotony.

Proof.

· SupposeG′ ∈∩{|E ∈Epr(G)},then anypr-extensionEofGis anadset ofG′.For anyco-extensionE1ofG,there is apr-extensionE2ofGsuch thatE1?E2.SinceE2is anad-set ofG′,then there must be aco-extensionE3ofG′such thatE2?E3.Thus the update fromGtoG′is expansivecomonotony.

Thepr-extension is also aco-extension,then the update fromGtoG′is also expansivepr-monotony.

· SupposeG′ ∈andE ∈Eid(G),then theid-extensionEofGis thegr-extension ofG′.Since thegr-extension is included in theid-extension of an argumentation framework,thenEincludes thegr-extension ofG.Thus the update fromGtoG′is expansivegr-monotony.Eis also included in theid-extension ofG′.Thus the update fromGtoG′is expansiveid-monotony.□

Egr(AF9)=Eid(AF9)={E3}whereE3={a}.illustrated in Figure 12 hasE3as thegr-extension.According to Theorem 10,the update fromAF9tois expansivegrandid-monotony,and we can see from Figure 12 that{a,e}is theid-extension of

Figure 10 :An argumentation framework

Figure 11 :An updated argumentation framework of AF9

Figure 12 :An updated argumentation framework of AF9

Gis the original argumentation framework,andG′is the updated framework.If the minimalco-extention,i.e.thegr-extension ofGis restricted inG′,then allco-extensions are restricted inG′.The minimalgr,prandid-extensions of an argumentation framework are themselves.The restrictive monotony under grounded,preferred and ideal semantics are satisfied if the correspondinggr,prandid-extensions are restricted inG′.

The following theorem uses the set ofσ-argumentation frameworks with an extension to show some sufficient conditions for restrictive monotony.

Theorem 11.Let G=(A,R)and G′=(A′,R′)be argumentation frameworks.

· If E is the gr-extension of G and G′ ∈then the update from G to G′ isrestrictive co and gr-monotony.

· If E is the id-extension of G and G′ ∈then the update from G to G′ isrestrictive pr and id-monotony.

Proof.

· SupposeEis thegr-extension ofGandG′ ∈thenEis aco-extension ofG′.Sincegr-extension is the minimalco-extension of an argumentation framework,then the update fromGtoG′is restrictiveco-monotony.More over,there must be agr-extensionE′ofG′such thatE′ ?E,then the update fromGtoG′is also restrictivegr-monotony.

· SupposeEis theid-extension ofGandG′ ∈thenEis apr-extension ofG′and it is included in anypr-extension ofG.FromEis apr-extension ofG′we know that theid-extensionE′ofG′is included inE.Then the update fromGtoG′is restrictiveid-monotony.FromEis included in anypr-extension ofGwe know that there is apr-extensionE′′ofGsuch thatE ?E′′.SinceG′ ∈then the update fromGtoG′is restrictivepr-monotony.

Example 14.ConsiderAF9illustrated in Figure 10 andE3={a}.E3is thegrand theid-extension ofAF9,and it is also aco-extension and apr-extension ofillustrated in Figure 13.According to Theorem 11,the update fromAF9tois restrictiveco,gr,prandid-monotony:E4={a,c,j}andE5={a,i}arecoandpr-extensions ofAF9??is thegrand theid-extension of

Figure 13 :An updated argumentation framework of AF9

5 Conclusion

Given an argumentation framework,a set of extensions are generated from its structure.Reversely,given an extension,or a set of extensions,a set of argumentation frameworks can be decided.In this paper,we study how to characterize argumentation frameworks from an extension.

The main part of this paper is Section 3,in which we define,and characterize the argumentation framework,sayG,with a set of arguments,sayE,as an extension.A series of characterizing theorems are proposed.The characterizations ofGunder complete,grounded and stable semantics are in the syntax level,but the characterization ofGunder preferred semantics is decided partially by computing the admissible labelling of a related sub-frameworkThe last part of Section 3 shows the relations between the sets of argumentation frameworks with an extension under different semantics,and that how to characterize an argumentation framework with more than one extension.In [17],we characterize subgraphs of an argumentation framework with an extension under admissible,complete,stable,preferred and grounded semantics1“Admissible”is a kind of semantics in[17]..In this paper,we adjust the characterizations to whole argumentation frameworks.The most significant improvement of this paper is that we found a way to characterize the argumentation frameworkGwithout computing the semantics ofunder grounded semantics,while in[17],the counterpart ofGneeds to be checked whether hasEas the grounded extention.Section 3 is a groundwork for[22]and[21].All results related to revising/updating argumentation frameworks in[22]and[21]conform to the characterizing theorems.

Section 4 shows some applications of the work in Section 3.The first application is updating an argumentation framework to enforce an extension.We discuss this problem followed from Baumann et al.([4]),and this part of application is not a new idea but a review of[21].The second application is monotony which is a property of updating argumentation frameworks.The monotony is introduced followed from [5],and is separated as expansive monotony and restrictive monotony.There are some relations between the set ofσ-arguementation frameworks with an extension and monotony,and the set ofσ-arguementation frameworks with an extension is used in this paper to show some conditions for monotony.Comparing[4]and[5],where updating an arugmentation framework is just adding or deleting one argument and the related attacks([5]),or extending it([4]),we combine our work on characterizing theorems to the updating process and provide a discretionary way to update a framework for both enforcement and monotony.

Two conceptions are provided in this paper to help characterizing theσ-arguementation framework with an extension.The first is circle.The circles in an argumentation framework are the key points to the constitution of semantics.It is used to characterize thegr-arguementation framework with an extension.The second one is partially labeled sub-framework.It is a variation of the concept of the same name in[15],and it is used to prove the characterization ofpr-arguementation framework with an extension.Furthermore,the partially labeled sub-framework itself is a useful idea to study the merging of argumentation frameworks.

To conclude,there are three defects of our work.The first is on the characterization ofpr-argumentation frameworks with an extension,where computing semantics of sub-frameworks makes the process of constructing a requested argumentation framework complicated.The second is that the argumentation framework generated from the characterizing theorems may have one or more extensions undesired.We can not get a one-to-one match between the argumentation frameworks and a set of extensions.The third is that we do not get the characterizing theorems under some other kinds of semantics such as ideal and semi-stable.All of these problems will be worth discussing in the future.