Introduction

Argumentation theory is a formal discipline within Artificial Intelligence (AI) where the aim is to make a computer assist in or perform the act of argumentation. During the last years, argumentation has been gaining increasing importance in Multi-Agent Systems (MAS), mainly as a vehicle for facilitating rational interaction (i.e.interaction which involves the giving and receiving of reasons) [4,14]. A single agent may also use argumentation techniques to perform its individual reasoning because it needs to make decisions under complex preferences policies, in a highly dynamic environment.

Although several approaches have been proposed for capturing representative patterns of inference in argumentation theory, Dung's approach, presented in [7], is a unifying framework which has played an influential role on argumentation research and AI. The kernel of Dung's framework is supported by four extension-based argumentation semantics (we will refer to them also as abstract argumentation semantics): grounded semantics, stable semantics, preferred semantics, and complete semantics. When Dung introduced his argumen-tation approach, he proved that it can be regarded as a special form of logic programming with negation as failure. In fact, he showed that the grounded and stable semantics can be characterized by the well-founded and stable model semantics respectively. This result has at least two main implications:

1. It defines a general method for generating metainterpreters for argumentation systems 2. It defines a general method for studying abstract argumentation semantics ' properties in terms of logic programming semantics' properties.

As we can see, the study of abstract argumentation semantics in terms of logic programming semantics has important implications for closing the gap between theoretical results and argumentation systems. Despite these implications, until 2007 the only extension-based argumentation semantics characterized in terms of logic programming semantics were the grounded and stable semantics. Recently, there are novel results which have shown that extension-based argumentation semantics (such as the preferred) semantics can be characterized in terms of logic programming semantics [5,11]. In fact, there are results which show that not only a logic programming approach can characterize extension-based argumentation semantics but also it can define new extension based argumentation semantics [12].

In this paper, we present a survey of recent results w.r.t. the close relationship between extension-based semantics and logic programming semantics with negation as failure. These results are in two directions:

1. The identification of dual characterizations between extension-based argumentation semantics and logic programming semantics. These results represent an extension of Theorem 17 presented in [7]. These results are based on regarding argumentation frameworks into logic programs. 2. The implementation of logic programming metainterpreters for inferring extension-based argumentation semantics. These metainterpreters are based on the platform of Answer Set Programming (ASP) 1 and a characterization of extension-based argumentation semantics in terms of labels (IN, OUT, UNDEC). This labeling process has shown to be a practical approach for defining interactive algorithms for inferring extension-based argumentation semantics [10]. However, there are results that show that the declarative specification of a labeling process defines an easy approach for computing extension-based argumentation semantics [16,15].

The rest of the paper is divided as follows: In §2, the syntax of valid logic programs in ASP is introduced, some basic concepts of the Dung's argumentation approach are defined and the characterization of extension-based argumentation semantics in terms of the labels: IN, OUT, UNDEC is presented. In §3, some recent results w.r.t. the relationship between extension-based argumentation semantics and logic programming semantics are presented. In §4, some approaches for implementing logic programming metainterpreters for inferring extension-based argumentation semantics are presented. Finally, in the last section some conclusions are presented.

Background

In this section, we present some basic concepts on: a) the syntax of logic programs b) extension-based argumentation semantics c) a labeling approach for characterizing extension-based argumentation semantics.

Syntax of Logic Programs

A signature L is a finite set of elements that we call atoms. A literal is an atom, a (positive literal), or the negation of an atom not a (negative literal). Given a set of atoms {a 1 , . . . , a n }, we write not {a 1 , . . . , a n } to denote the set of literals {not a 1 , . . . , not a n }. A disjunctive clause is a clause of the form:

a 1 ∨ • • • ∨ a m ← a m+1 , .

. . , a j , not a j+1 , . . . , not a n where a i is an atom, 1 ≤ i ≤ n. When n = m and m > 0, the disjunctive clause is an abbreviation of the fact

a 1 ∨ • • • ∨ a m ←

where is an atom that always evaluate to true. When m = 0 and n > 0 the clause is an abbreviation of ⊥ ← a 1 , . . . , a j , not a j+1 , . . . , not a n where ⊥ is an atom that always evaluate to false. Clauses of this form are called constraints (the rest non-constraints). A disjunctive logic program is a finite set of disjunctive clauses.

We denote by L P the signature of P , i.e., the set of atoms that occur in P. Given a signature L, we write P rog L to denote the set of all the programs defined over L.

Extension-based Argumentation Semantics

We are going to present a short introduction of Dung's argumentation approach. A fundamental Dung's definition is the concept called argumentation framework which is defined as follows: Dung also defined a skeptical semantics which is called grounded semantics and it is defined in terms of a characteristic function. Definition 6. [7] The characteristic function, denoted by F AF , of an argumentation framework AF = AR, attacks is defined as follows:

Definition 1. [7]F AF : 2 AR → 2 AR F AF (S) = {A| A is acceptable w.r.t. S } Definition 7. [7]

The grounded extension of an argumentation framework AF, denoted by GE AF , is the least fixed point of F AF Dung defined the concept of complete extension which provides the link between preferred extensions (credulous semantics), and grounded extension (skeptical semantics). Definition 8. [7] An admissible set S of arguments is called complete extension if and only if each argument which is acceptable w.r.t. S, belongs to S.

In [7], a general method for generating metainterpreters in terms of logic programming for argumentation systems was suggested. This is the first approach which regards an argumentation framework as a logic program. This metainterpreter is divided in two units: Argument Generation Unit (AGU), and Argument Processing Unit (APU). The AGU is basically the representation of the attacks upon an argumentation framework and the APU consists of two clauses. In order to define these clauses, let us introduce the predicate d(x), where the intended meaning of d(x) is: "the argument x is defeated" and the predicate acc(x), where the intended meaning of acc(x) is: "the argument x is acceptable".

(C1) acc(x) ← not d(x) (C2) d(x) ← attack(y, x), acc(y)

The first one (C1) suggests that the argument x is acceptable if it is not defeated and the second one (C2) suggests that an argument is defeated if it is attacked by an acceptable argument. Formally, the Dung's metainterpreter is defined as follows: This result is really important in argumentation semantics, in fact it has at least two main implications:

1. It defines a general method for generating metainterpreters for argumentation systems and 2. It defines a general method for studying abstract argumentation semantics' properties in terms of logic programming semantics' properties.

As we can see, the study of abstract argumentation semantics in terms of logic programming semantics has important implications.

Extension-based Argumentation Semantics via Labeling

A common approach for deciding acceptability of arguments is by considering a labeling process. The labeling approach is a suitable approach for characterizing argumentation semantics [9,10].

The labeling process is based in a labeling mapping. In this paper, we are going to consider the mapping presented in [10] which considers three labels: in, out and undec. This mapping is defined as follows: Given an argumentation framework AF = AR, attacks , for any argument a ∈ AR one can define functions IN (a) , OU T (a) and U N DEC(a) that return true if the argument a is labeled in, out and undec respectively, and false otherwise. Also, the sets IN , OU T and U N DEC can be defined as the sets containing all the arguments in the framework labeled in, out and undec respectively. A special type of labeling is the reinstatement labeling. A reinstatement labeling is a labeling that, given an Argumentation framework AF = AR, attacks and attacks(a, b) if f (a, b) ∈ attacks meets the following two properties:

∀a ∈ AR : OU T (a) = true if f ∃b ∈ AR : attacks(b, a) ∧ IN (b) = true ∀a ∈ AR : IN (a) = true if f ∀b ∈ AR : attacks(b, a) then OU T (b) = true

Some authors have shown that by considering a mapping process one can characterize the extension-based argumentation semantics defined by Dung in [7] and also some other new argumentation semantics that have been defined by the argumentation community. Some of these characterizations are [10]: In the following sections, we are going to present some recent results which extend Theorem 1 and its implications.

-

Extension-Based Semantics as Logic Programming Semantics with Negation as Failure

In this section, we are going to introduce some recent results which extend Theorem 1. For this aim, we are going to introduce some simple mappings in order to regard argumentation frameworks in terms of logic programs.

Definition 10. Let AF = AR, attacks be an argumentation framework, then P 1 AF , P2 AF and P 3 AF are defined as follows: The intuitive ideas behind these mappings are:

P 1 AF = a∈AR

-P 1 AF suggests that an argument a will be defeated if one of its adversaries is not defeated. It is not hard to see that P 1 AF is equivalent to P AF (introduced in Definition 9). -P 2 AF suggests that the argument a is defeated when all the arguments that defend 2 a are defeated.

-P 3 AF suggest that any arguments which is not defeated is accepted.

The conditions captured by P 1 AF and P 2 AF are standard settings in argumentation theory for expressing the acceptability of an argument. In fact, these conditions are also standard setting in Defeasible Logic [8].

In order to present some relevant properties of the defined mappings, let us define the function tr as follows: Given a set of arguments E, tr(E) is defined as follows: tr(E) = {acc(a)|a ∈ E} ∪ {d(b)|b is an argument and b ∈ E} Now, let us introduce a theorem that essentially summarizes some relevant characterizations of extension-based argumentation semantics in terms of logic programming semantics with negation as failure.

Theorem 2. Let AF be an argumentation framework and E be a set of arguments. Then:

-E is the grounded extension AF iff tr(E) is the well-founded model of

Ψ 1 AF ∪ Ψ 2 AF ∪ Ψ 3 AF . -E is a stable extension of AF iff tr(E) is a stable model of P si 1 AF ∪ Ψ 2 AF ∪ Ψ 3 AF . -E is a preferred extension of AF iff tr(E) is a p-stable model of Ψ 1 AF ∪ Ψ 2 AF ∪ Ψ 3 AF .

This theorem was proved in [5]. Observe that essentially, this theorem is extending Theorem 1 and suggests that one can capture three of the well accepted argumentation semantics in one single logic program and three different logic programming semantics. The interesting part of this kind of results is that one can explore meta-interpreters of these argumentation semantics in terms of solvers of logic programming semantics . Also, one can explore non-monotonic reasoning properties of argumentation semantics in terms of their corresponding logic programming semantics. For instance, a possible research issue in this line is to explore the non-monotonic properties of the preferred semantics via p-stable semantics. It is worth mentioning that the p-stable semantics is based on paraconsistent logics. This suggests that one can characterize the preferred semantics in terms of paraconsistent logics.

The identification of non-monotonic reasoning properties which could represent a good-behavior of an argumentation semantics represents a hot topic since recently the number of new argumentation semantics in the context of Dungs argumentation approach has increased. The new semantics are motivated by the fact that the extension based semantics introduced by Dung in [7] have exhibited a variety of problems common to the grounded, stable and preferred semantics [13,3].

One of the approaches that has been emerging for building new extensionbased argumentation semantics was introduced in [3]. This approach is based on a solid concept in graph theory: strongly connected components (SCC). In [3], several alternative argumentation semantics were introduced; however, from them, CF2 is an argumentation semantics that has shown to have good-behavior [2].

In [12], an new approach for building argumentation semantics was introduced. In this approach the author suggests to use any logic programming semantics. By considering this approach, the authors were able to characterize the argumentation semantics CF2. Theorem 3. [12] Let AF be an argumentation framework and E be a set of arguments. Then,

E is a CF2 extension AF iff tr(E) is M M r model of Ψ 1 AF ∪ Ψ 3 AF .

theorem suggests that the relationship between the approach presented in [3] and [12] is close. In fact, both Theorem 2 and Theorem 3 suggest that not only one can characterize argumentation semantics in terms of logic programming semantics but also one can define new argumentation semantics in terms of logic programming semantics.

Inferring Extension-Based Semantics via NonMonotonic

Reasoning Tools

So far, we have shown that logic programming semantics can be a suitable approach for exploring properties of extension-based argumentation semantics and defining new argumentation semantics. In this section, we show that the use of nonmonotic tools represent a potential approach for building intelligent systems based on an argumentation reasoning process.

Preferred Semantics by Positive Disjunctive Logic Programs

Taking advantage of the mappings presented in Definition 10, in [11], it was shown that by considering Ψ 1 AF ∪ Ψ 2 AF as a propositional formula its minimal models characterize the preferred extensions of the given argumentation framework. In fact, by transforming This theorem suggest that one can any disjunctive answer set solver as DLV [6] for inferring the preferred semantics. It is worth mentioning that by considering P 1 AF , P 2 AF and P 3 AF one can use any answer solver for computing the stable and grounded semantics.

Computing Extension-Based Argumentation Semantics by Labeling

Until now, we have shown that we can infer extension-based argumentation semantics by regarding an argumentation framework as a logic program. However, as we saw in §2.3 some extension-based argumentation semantics can be characterized by considering labeling process. The labeling represents an alternative approach for computing extension-based argumentation semantics in terms of logic programming with negation as failure. In particular, there are results that show that by considering a labeling process one is able to compute the grounded, stable, preferred and complete argumentation semantics in terms of answer set semantics. An outstanding trend of computing such labellings is via answer set solvers.

The following two sections present studies that explore ASP applications that are able to compute various argumentation semantics, as well as decide whether an argument is sceptically or credulously accepted with reference to the chosen semantics. The idea behind these works is to transform an argumentation framework into a single normal logic program that references an argumentation semantics (either preferred, grounded, stable or complete). The answer set of the resulting program is a labeling [10] that expresses an argument-based extension for the chosen semantics.

Once programs to compute every available semantics are available, a procedure to decide if an argument is sceptically or credulously accepted in the semantic can be introduced. The following mapping between skeptical or credulous arguments, argumentation frameworks and argumentation semantics is defined. Given an argumentation framework AF = AR, attacks , an argument a ∈ AR, and an argumentation semantics S: a) a is credulously justified if a ∈ IN in, at least, one possible labeling that matches the restrictions defined by the semantic S. b) a is sceptically justified if a ∈ IN in every possible labeling that matches the restrictions defined by the semantic S.

First Approach for Implementing an Argumentation MetaInterpreter in ASP

This section presents an approach for implementing an argumentation metainterpreter presented in [16] based on answer-set semantics to compute admissible, preferred, stable, semi-stable, complete, and grounded extensions.

following programs are specified given an Argumentation Framework AF = AR, attacks , two variables X and Y , the predicate symbol arg that denotes that the variable a is an argument of AF , and the functions IN (X) , OU T (X) defined before.

The program formed by the set of rules Π CF is able to compute complete extensions. The set of rules Π CF is as follows:

IN (x) ← arg(x), not OU T (x). OU T (x) ← arg(x), not IN (x). ⊥ ← IN (x), IN (Y ), def eat(X, Y ). def eat(X, Y ) ← (X, Y ) ∈ attacks.

The program formed by the set of rules Π CF ∪ Π stable is able to compute stable extensions. The set of rules Π stable is as follows:

def eated(X) ← IN (Y ), attack(Y, X) ∈ attacks. ← OU T (X), not def eated(X).

The program formed by the set of rules Π CF ∪ Π stable ∪ Π complete is able to compute complete extensions. The set of rules Π complete is as follows:

not def ended(X) ← def eat(Y, X), not def eated(Y ). ← OU T (X), not not def ended(X).

Computing grounded, preferred and semi-stable extensions is a bit harder, because they require a labeling that maximizes or minimizes the elements in a set. In order to compute these extensions, this approach makes use of a stratified program [1]. This program defines the order operator ( < ) between the arguments in the domain, and derives predicates for minimal, maximal and successor. For doing so, the following program, Π < is defined:

lt(X, Y ) ← arg(X), arg(Y ), X < Y . nsucc(X, Z) ← lt(X, Y ), lt(Y, Z). succ(X, Y ) ← lt(X, Y ), not nsucc(X, Y ). ninf (Y ) ← lt(X, Y ).

inf (X) ← arg(X), not ninf (X). nsup(X) ← lt(X, Y ). sup(X) ← arg(X), not nsup(X).

Using the program above, the predicate def end(X) is defined. This predicate is derived if for a given Argumumentation Framework AF = AR, attacks , each argument Y : Y ∈ AR def end(X, Y ). In order ensure that def end(X, Y ) is checked for every available argument, variable Y ranges from the minimal to the maximal using successor relations. The program Π def end that defines the above mentioned predicate, is as follows:

def end upto(X, Y ) ← inf (Y ), arg(X), not def eat(Y, X). def end upto(X, Y ) ← inf (Y ), in(Z), def eat(Z, Y ), def eat(Y, X). def end upto(X, Y ) ← succ(Z, Y ), def end upto(X, Z), not def eat(Y, X). def end upto(X, Y ) ← succ(Z, Y ), def end upto(X, Z), in(V ), def eat(V, Y ), def eat(Y, X). def end(X) ← sup(Y ), def end upto(X, Y ).

The program formed by the set of rules Π < ∪ Π def end ∪ Π ground computes grounded extensions. The set of rules Π ground is as follows: in(X) ← def ended(X).

Computing both preferred and semi-stable extensions will make use of the programs Π < and Π def end defined above. However this process is a bit more complicated, because it requires computing maximal sets instead of minimal ones. For tackling this issue the approach makes use of a saturation technique. This technique consists in building a labeling S such that every other possible labeling T that complies with certain conditions (either maximal IN or U N DEC labels) does not characterize an admissible extension.

First of all, in order to model the maximal sets that both preferred and semistable extensions require, the program Π def end presented above is slightly modified, to include predicates inN and outN . The meaning of the predicates varies depending the type of semantic computed (either preferred or semi-stable) so they are defined later, in the program associated to this semantics. The program Π undef eated is defined as follows:

undef eated upto(X, Y ) ← inf (Y ), outN (X), outN (Y ).

undef eated upto(X, Y ) ← inf (Y ), outN (X), not def eat(Y, X).

undef eated upto(X, Y ) ← succ(Z, Y ), undef eated upto(X, Z), outN (Y ).

undef eated upto(X, Y ) ← succ(Z, Y ), undef eated upto(X, Z), not def eat(Y, X).

undef eated(X) ← sup(Y ), undef eated upto(X, Y ).

The program formed by the sets of rules Π adm ∪ Π < ∪ Π undef eated ∪ Π pref erred computes preferred extensions. The set of rules Π pref erred is as follows:

eq upto(Y ) ← inf (Y ), in(Y ), inN (Y ). eq upto(Y ) ← inf (Y ), out(Y ), outN (Y ). eq upto(Y ) ← succ(Z, Y ), in(Y ), inN (Y ), eq upto(Z).

eq upto(Y ) ← succ(Z, Y ), out(Y ), outN (Y ), eq upto(Z).

eq ← sup(Y ), eq upto(Y ). inN (X) ∨ outN (X) ← out(X). inN (X) ← in(X) spoil ← eq. spoil ← inN (X), inN (Y ), def eat(X, Y ).

spoil ← inN (X), outN (Y ), def eat(Y, X), undef eated(Y ). inN (X) ← spoil, arg(X). outN (X) ← spoil, arg(X). ⊥ ← not spoil.

Last but not least, the program formed by the sets of rules Π adm ∪ Π < ∪ Π undef eated ∪ Π semi−stable computes semi-stable extensions.. The set of rules Π semi−stable is as follows:

eqplus upto(Y ) ← inf (Y ), in(Y ), inN (X), def eat(X, Y ). eqplus upto(Y ) ← inf (Y ), in(X), inN (Y ), def eat(X, Y ). eqplus upto(Y ) ← inf (Y ), in(X), inN (Z), def eat(X, Y ), def eat(Z, Y ). eqplus upto(Y ) ← inf (Y ), out(Y ), outN (Y ), not def eated(Y ), undef eated(Y ).← sup(Y ), eqplus upto(Y ). inN (X) ∨ outN (X) ← arg(X). spoil ← eqplus. spoil ← inN (X), inN (Y ), def eat(X, Y ). ← inN (X), outN (Y ), def eat(Y, X), undef eated(Y ).

spoil ← inN (X), outN (X), undef eated(X).

spoil ← inN (Y ), def eat(Y, X), outN (X), undef eated(X). inN (X) ← spoil, arg(X). outN (X) ← spoil, arg(X). ⊥ ← not spoil.

Second Approach for Implementing an Argumentation

MetaInterpreter in ASP

The work presented in this section [15] is an approach for computing Dung's standard argumentation semantics as well as semi-stable semantics via ASP.

The base of all this programs is a set of rules defining the Argumentation Framework, that is, both the available arguments and the attack relations between them. Given an argumentation framework AF = AR, attacks , and two constants a and b the following ASP program , known as Π AF can be defined: The program formed by the set of rules Π AF ∪ Π Complete ∪ Π Stable is able to compute stable extensions. The set of rules Π Stable is as follows:

⊥ ← U N DEC(x)

Computing grounded, preferred and semi-stable extensions is a bit harder, because it implies the need to minimize or maximize the elements in certain sets. In order to be able to compute such semantics, the following program, known as Π AF M AX is defined:

c(Y ) ← cno(Y ), m1(X), i(X), not m2(X, Y ). d(Y ) ← m2(X, Y ), i(X), not m1(X). ⊥ ← d(Y ), not c(Y ).

The program formed by the set of rules Π AF ∪ Π AF M AX ∪ Π Complete ∪ Π Grounded is able to compute grounded extensions. The set of rules Π Grounded is as follows: c(Y ) ← cno(Y ), m1(X), i(X), not m2(X, Y ). d(Y ) ← m2(X, Y ), i(X), not m1(X). ⊥ ← c(Y ), not d(Y ).

The program formed by the rules Π AF ∪ Π AF M AX ∪ Π Complete ∪ Π semi−stable is able to compute semi-stable extensions. The set of rules Π semi−stable is as follows: c(Y ) ← cno(Y ), m1(X), u(X), not m2(X, Y ). d(Y ) ← m2(X, Y ), u(X), not m1(X). ⊥ ← c(Y ), not d(Y ).

Discussion w.r.t. Label Process

Labeling provides an easy and intuitive approach to argumentation theory. It is based on simple and easy principles that are simpler to explain and understand than extension-based approaches.

Computing the labels that are to be assigned to nodes via an ASP program allows to build and interpreter that processes the Argumentation Framework as input, in contrast to using a fixed logic program which depends on the Argumentation Framework to process. In this sense, the interpreter is easier to understand, extend and debug. Moreover, it eases the process of formally proving the correspondence between answer sets and extensions. Finally, having an interpreter which is independent of the Argumentation Framework allows to easily change the framework without having to re-generate the logic program. However, it must be noted that a full decoupling between the input Argumentation Framework and the programs used to compute its labellings has not been achieved. Both works present programs that are bounded to the Argumentation Framework when computing grounded, preferred and semi-stable extension. In the first work analyzed if the Argumentation Framework changes, predecessor, successor and maximal properties of arguments must be re-built, whereas in the second one constant ξ must be updated.

Conclusions

In this paper, we have presented a survey of resent results w.r.t. the dual relationship between extension-based argumentation semantics and logic programming semantics (see §3). We have presented as well results that show that answer set programming is suitable approach for building Argumentation MetaInterpreters (see §4). We have presented two approaches for exploring extension-based argumentation semantics in terms of logic programming. On the one hand, the first approach [16] presents a more complex but more versatile code due to the usage of the stratified programming and saturation techniques. On the other hand, the second one [15] presents a more simple code, but it has to be meta-coded by an external program due to being bound to the number of available arguments in the argumentation framework. Both approaches are based on mapping the argumentation framework to a labeling system, this facilitates the computational