=Paper=
{{Paper
|id=Vol-533/paper-2
|storemode=property
|title=Extension-Based Argumentation Semantics via Logic Programming Semantics with Negation as Failure
|pdfUrl=https://ceur-ws.org/Vol-533/04_LANMR09_01.pdf
|volume=Vol-533
|dblpUrl=https://dblp.org/rec/conf/lanmr/NievesG09
}}
==Extension-Based Argumentation Semantics via Logic Programming Semantics with Negation as Failure==
https://ceur-ws.org/Vol-533/04_LANMR09_01.pdf
Extension-Based Argumentation Semantics via Logic
Programming Semantics with Negation as Failure
Juan Carlos Nieves and Ignasi Gomez-Sebastià
Universitat Politècnica de Catalunya
Software Department (LSI)
c/Jordi Girona 1-3, E08034, Barcelona, Spain
{jcnieves,igomez}@lsi.upc.edu
Abstract. Extension-based argumentation semantics have been shown to be a
suitable approach for performing practical reasoning. Since extension-based ar-
gumentation semantics were formalized in terms of relationships between atomic
arguments, it has been shown that extension-based argumentation semantics (such
as the grounded semantics and stable semantics) can be characterized by logic
programming semantics with negation as failure. Recently, it has been shown
that argumentation semantics such as the preferred semantics and the CF2 se-
mantics can be characterized in terms of logic programming semantics. In this
paper, we make a short overview w.r.t. recent results in the close relationship be-
tween extension-based semantics and logic programming semantics with nega-
tion as failure. We also show that there is enough evidence to believe that the use
of declarative approaches based on logic programming semantics with negation
as failure is a practical approach for performing practical reasoning following an
argumentation reasoning approach.
1 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 argumen-
tation. During the last years, argumentation has been gaining increasing im-
portance 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 per-
form 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 representa-
tive patterns of inference in argumentation theory, Dung’s approach, presented
in [7], is a unifying framework which has played an influential role on argu-
mentation 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, pre-
ferred semantics, and complete semantics. When Dung introduced his argumen-
31
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 argumenta-
tion 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. Re-
cently, there are novel results which have shown that extension-based argumen-
tation 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 argumenta-
tion semantics [12].
In this paper, we present a survey of recent results w.r.t. the close relation-
ship 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 argu-
mentation semantics and logic programming semantics. These results rep-
resent 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].
1
Answer Set Programming is a novel approach of logic programming which was suggested by
the non-monotonic reasoning community [1].
32
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 argumen-
tation approach are defined and the characterization of extension-based argu-
mentation semantics in terms of the labels: IN, OUT, UNDEC is presented. In
§3, some recent results w.r.t. the relationship between extension-based argumen-
tation 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 sec-
tion some conclusions are presented.
2 Background
In this section, we present some basic concepts on: a) the syntax of logic pro-
grams b) extension-based argumentation semantics c) a labeling approach for
characterizing extension-based argumentation semantics.
2.1 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 {a1 , . . . , an }, we write not {a1 , . . . , an } to denote the
set of literals {not a1 , . . . , not an }. A disjunctive clause is a clause of the
form: a1 ∨ · · · ∨ am ← am+1 , . . . , aj , not aj+1 , . . . , not an where ai is an
atom, 1 ≤ i ≤ n. When n = m and m > 0, the disjunctive clause is an
abbreviation of the fact a1 ∨ · · · ∨ am ← > where > is an atom that always
evaluate to true. When m = 0 and n > 0 the clause is an abbreviation of
⊥ ← a1 , . . . , aj , not aj+1 , . . . , not an 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 LP the signature of P , i.e., the set of atoms that occur in
P. Given a signature L, we write P rogL to denote the set of all the programs
defined over L.
2.2 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:
Definition 1. [7] An argumentation framework is a pair AF = hAR, attacksi,
where AR is a set of arguments, and attacks is a binary relation on AR, i.e.attacks
⊆ AR × AR.
33
Following Dung’s reading, we say that A attacks B (or B is attacked by A)
if attacks(A, B) holds. Similarly, we say that a set S of arguments attacks B
(or B is attacked by S) if B is attacked by an argument in S.
Definition 2. [7] A set S of arguments is said to be conflict-free if there are no
arguments A, B in S such that A attacks B.
Definition 3. [7] (1) An argument A ∈ AR is acceptable with respect to a set
S of arguments if and only if for each argument B ∈ AR: If B attacks A then B
is attacked by S. (2) A conflict-free set of arguments S is admissible if and only
if each argument in S is acceptable w.r.t. S.
The (credulous) semantics of an argumentation framework is defined by the
notion of preferred extensions.
Definition 4. [7] A preferred extension of an argumentation framework AF is a
maximal (w.r.t. inclusion) admissible set of AF.
Another relevant semantics that Dung introduced is the stable semantics of
an argumentation framework which is based in the notion of stable extension.
Definition 5. [7] A conflict-free set of arguments S is called a stable extension
if and only if S attacks each argument which does not belong to S.
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 FAF , of an argumen-
tation framework AF = hAR, attacksi is defined as follows:
FAF : 2AR → 2AR
FAF (S) = {A| A is acceptable w.r.t. S }
Definition 7. [7] The grounded extension of an argumentation framework AF,
denoted by GEAF , is the least fixed point of FAF
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.
34
In [7], a general method for generating metainterpreters in terms of logic
programming for argumentation systems was suggested. This is the first ap-
proach 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:
Definition 9. Given an argumentation framework AF = hAR, attacksi, PAF
denotes the logic program defined by PAF = AP U + AGU where AP U =
{C1, C2} and AGU = {attacks(a, b) ← >|(a, b) ∈ attacks}
For each extension E of AF , m(E) is defined as follows:
m(E) = AGU ∪ {acc(a)|a ∈ E} ∪ {d(b)|b is attacked by some a ∈ E}
Based on PAF , Dung was able to characterize the stable semantics and the
grounded semantics.
Theorem 1. Let AF be an argumentation framework and E be an extension of
AF. Then
1. E is a stable extension of AF if and only if m(E) is an answer set of PAF
2. E is a grounded extension of AF if and only if m(E) ∪ {not def eat(a)|a ∈
E} is the well-founded model of PAF
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 argumenta-
tion 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.
35
2.3 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 = hAR, attacksi, 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 = hAR, attacksi 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]:
– Complete extensions are equal to reinstatement labellings.
– Grounded extensions are equal to reinstatement labellings, where the set IN
is minimal. That is, there is no other possible reinstatement labeling in the
same Argumentation Framework with a set IN 0 such that IN 0 ⊆ IN .
– Preferred extensions are equal to reinstatement labellings, where the set IN
is maximal. That is, there is no other possible reinstatement labeling in the
same Argumentation Framework with a set IN 0 such that IN ⊆ IN 0 .
– Stable extensions are equal to reinstatement labellings, where the set
U N DEC is empty. That is, ∀a ∈ AR : a ∈ / U N DEC.
– Semi-stable extensions are equal to reinstatement labellings, where the set
U N DEC is minimal. That is, there is no other possible reinstatement label-
ing in the same Argumentation Framework with a set U N DEC 0 such that
U N DEC 0 ∈ U N DEC.
In the following sections, we are going to present some recent results which
extend Theorem 1 and its implications.
36
3 Extension-Based Semantics as Logic Programming Semantics
with Negation as Failure
In this section, we are going to introduce some recent results which extend The-
orem 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 = hAR, attacksi be an argumentation framework, then
1 , P 2 and P 3 are defined as follows:
PAF AF AF
[ [
1
PAF = { {d(a) ← not d(b)}
a∈AR b:(b,a)∈attacks
[ [ ^
2
PAF = { {d(a) ← d(c)}}
a∈AR b:(b,a)∈attacks c:(c,b)∈attacks
[
3
PAF = {acc(a) ← not d(a)}
a∈AR
The intuitive ideas behind these mappings are:
1 suggests that an argument a will be defeated if one of its adversaries is
– PAF
1 is equivalent to P
not defeated. It is not hard to see that PAF AF (introduced
in Definition 9).
2 suggests that the argument a is defeated when all the arguments that
– PAF
defend2 a are defeated.
3 suggest that any arguments which is not defeated is accepted.
– PAF
The conditions captured by PAF 1 and P 2 are standard settings in argu-
AF
mentation 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 6∈ 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 argu-
ments. Then:
2
We say that c defends a if b attacks a and c attacks b.
37
– E is the grounded extension of AF iff tr(E) is the well-founded model of
1 ∪ Ψ2 ∪ Ψ3 .
ΨAF AF AF
– E is a stable extension of AF iff tr(E) is a stable model of
P si1AF ∪ ΨAF
2 ∪ Ψ3 .
AF
1 ∪
– E is a preferred extension of AF iff tr(E) is a p-stable model of ΨAF
2 ∪ Ψ3 .
ΨAF 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 ac-
cepted 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 correspond-
ing 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 rep-
resent 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 extension-
based 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 intro-
duced. In this approach the author suggests to use any logic programming se-
mantics. 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 ΨAF
1 ∪
3
ΨAF .
38
This 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 program-
ming semantics but also one can define new argumentation semantics in terms
of logic programming semantics.
4 Inferring Extension-Based Semantics via NonMonotonic
Reasoning Tools
So far, we have shown that logic programming semantics can be a suitable ap-
proach 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.
4.1 Preferred Semantics by Positive Disjunctive Logic Programs
Taking advantage of the mappings presented in Definition 10, in [11], it was
shown that by considering ΨAF 1 ∪ Ψ 2 as a propositional formula its minimal
AF
models characterize the preferred extensions of the given argumentation frame-
1 into a positive disjunctive logic program one
work. In fact, by transforming ΨAF
can characterize the preferred semantics in terms of stable model semantics as
follows:
Definition 11. Let AF = hAR, attacksi be an argumentation framework ,a ∈
AR and attacks(a, b) if f (a, b) ∈ attacks. We define the transformation func-
tion Γ (a) as follows:
[ [ ^
Γ (a) = { {d(a)∨d(b)}}∪{ {d(a) ← d(c)}}
b:attacks(b,a) b:attacks(b,a) c:attacks(c,b)
Now we define the function Γ in terms of an argumentation framework.
Definition 12. Let AF = hAR, attacksi be an argumentation framework. We
define its associated general program as follows:
[
ΓAF = Γ (a)
a∈AR
Theorem 4. Let AF = hAR, attacksi be an argumentation framework and
S ⊆ AR. S is a preferred extension of AF if and only if compl(S) is a stable
model of ΓAF .
39
This theorem suggest that one can use any disjunctive answer set solver as
DLV [6] for inferring the preferred semantics. It is worth mentioning that by
considering PAF1 , P 2 and P 3 one can use any answer solver for computing
AF AF
the stable and grounded semantics.
4.2 Computing Extension-Based Argumentation Semantics by Labeling
Until now, we have shown that we can infer extension-based argumentation se-
mantics by regarding an argumentation framework as a logic program. However,
as we saw in §2.3 some extension-based argumentation semantics can be char-
acterized 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 pro-
cedure to decide if an argument is sceptically or credulously accepted in the
semantic can be introduced. The following mapping between skeptical or cred-
ulous arguments, argumentation frameworks and argumentation semantics is de-
fined. Given an argumentation framework AF = hAR, attacksi, 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.
4.3 First Approach for Implementing an Argumentation MetaInterpreter
in ASP
This section presents an approach for implementing an argumentation metain-
terpreter presented in [16] based on answer-set semantics to compute admissi-
ble, preferred, stable, semi-stable, complete, and grounded extensions.
40
The following programs are specified given an Argumentation Framework
AF = hAR, attacksi, 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, be-
cause 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 pro-
gram [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 = hAR, attacksi, 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
41
ones. For tackling this issue the analyzed 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 semi-
stable extensions require, the program Πdef end presented above is slightly mod-
ified, 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:
ag(a) ←. for any argument a ∈ AR def (a, b). for any pair (a, b) ∈ attacks
eqplus upto(Y ) ← inf (Y ), in(Y ), inN (Y ).
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 ).
eqplus upto(Y ) ← succ(Z, Y ), in(Y ), inN (Y ), eqplus upto(Z).
eqplus upto(Y ) ← succ(Z, Y ), in(Y ), inN (X), def eat(X, Y ), eqplus upto(Z).
eqplus upto(Y ) ← succ(Z, Y ), in(Y ), inN (Y ), def eat(X, Y ), eqplus upto(Z).
eqplus upto(Y ) ← succ(Z, Y ), in(X), inN (U ), def eat(X, Y ), def eat(U, Y ), eqplus upto(Z).
eqplus upto(Y ) ← succ(Z, Y ), out(Y ), outN (Y ), not def eated(Y ), undef eated(Y ), eqplus upto(Z).
eqplus ← sup(Y ), eqplus upto(Y ). inN (X) ∨ outN (X) ← arg(X). spoil ← eqplus.
spoil ← inN (X), inN (Y ), def eat(X, Y ).
42
spoil ← 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.
4.4 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 be-
tween them. Given an argumentation framework AF = hAR, attacksi, and
two constants a and b the following ASP program , known as ΠAF can be de-
fined:
ag(a) ←. for any argument a ∈ AR def (a, b). for any pair (a, b) ∈ attacks
The program formed by the set of rules ΠAF ∪ΠComplete is able to compute
complete extensions. Given two variables X and Y , the predicate symbols ng
and arg and the functions IN (x), OU T (x), U N DEC(x) defined before, the
set of rules ΠComplete is as follows:
IN (x) ← ag(x), not ng(x). ng(x) ← IN (y), def (y, x). ng(x) ← U N DEC(y), def (y, x).
OU T (x) ← IN (y), def (y, x). U N DEC(x) ← ag(x), not IN (x) , not OU T (x).
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:
m1(Lt) ← L. for any set of arguments Lt : ∀a ∈ LtIN (a) ∪ U N DEC(a) m2(Lt, j) ← >. cno(j) ← >.
1 ≥ j ≥ ξ where ξ is the number of possible labellings in the framework, and Lt is a set of arguments labeled IN or UNDEC in the
labeling number j.
i(Lt) for any set of arguments Lt : ∀a ∈ Lt IN (a) u(Lt) for any set of arguments Lt : ∀a ∈ Lt U N DEC(a)
The program formed by the set of rules ΠAF ∪ ΠAFM AX ∪ ΠComplete ∪
ΠP ref erred is able to compute preferred extensions.. The set of rules ΠP ref erred
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).
⊥ ← d(Y ), not c(Y ).
The program formed by the set of rules ΠAF ∪ ΠAFM 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 ).
43
The program formed by the set of rules ΠAF ∪ ΠAFM 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 ).
4.5 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 Ar-
gumentation Framework to process. In this sense, the interpreter is easier to
understand, extend and debug. Moreover, it eases the process of formally prov-
ing 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 Argumenta-
tion 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.
5 Conclusions
In this paper, we have presented a survey of resent results w.r.t. the dual relation-
ship 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 argu-
mentation 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 ar-
gumentation framework to a labeling system, this facilitates the computational
44
treatment of the argumentation semantics in terms of declarative specifications.
There are still several open issues to explore in the close relationship between
argumentation theory and logic programming with negation as failure. One of
the most appealing issues is exploring the inference of CF2 semantics in terms
of answer set models.
References
1. C. Baral. Knowledge Representation, Reasoning and Declarative Problem Solving. Cam-
bridge University Press, Cambridge, 2003.
2. P. Baroni and M. Giacomin. On principle-based evaluation of extension-based argumentation
semantics. Artificial Intelligence., 171(10-15):675–700, 2007.
3. P. Baroni, M. Giacomin, and G. Guida. SCC-recursiveness: a general schema for argumen-
tation semantics. Artificial Intelligence, 168:162–210, October 2005.
4. T. J. M. Bench-Capon and P. E. Dunne. Argumentation in artificial intelligence. Artificial
Intelligence, 171(10-15):619–641, 2007.
5. J. L. Carballido, J. C. Nieves, and M. Osorio. Inferring Preferred Extensions by Pstable
Semantics. Iberoamerican Journal of Artificial Intelligence (Inteligencia Artificial) ISSN:
1137-3601, 13(41):38–53, 2009 (doi: 10.4114/ia.v13i41.1029).
6. S. DLV. Vienna University of Technology. http://www.dbai.tuwien.ac.at/proj/dlv/, 1996.
7. P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming and n-person games. Artificial Intelligence, 77(2):321–358,
1995.
8. G. Governatori, M. J. Maher, G. Antoniou, and D. Billington. Argumentation semantics for
defeasible logic. J. Log. Comput., 14(5):675–702, 2004.
9. H. Jakobovits and D. Vermeir. Robust semantics for argumentation frameworks. Journal of
logic and computation, 9(2):215–261, 1999.
10. S. Modgil and M. Caminada. Argumentation in Artificial Intelligence, chapter Proof Theories
and Algorithms for Abstract Argumentation Frameworks, pages 105–129. Springer, 2009.
11. J. C. Nieves, M. Osorio, and U. Cortés. Preferred Extensions as Stable Models. Theory and
Practice of Logic Programming, 8(4):527–543, July 2008.
12. J. C. Nieves, M. Osorio, and C. Zepeda. Expressing Extension-Based Semantics based on
Stratified Minimal Models. In H. Ono, M. Kanazawa, and R. de Queiroz, editors, Proceed-
ings of WoLLIC 2009, Tokyo, Japan, volume 5514 of FoLLI-LNAI subseries, pages 305–319.
Springer Verlag, 2009.
13. H. Prakken and G. A. W. Vreeswijk. Logics for defeasible argumentation. In D. Gabbay and
F. Günthner, editors, Handbook of Philosophical Logic, volume 4, pages 219–318. Kluwer
Academic Publishers, Dordrecht/Boston/London, second edition, 2002.
14. I. Rahwan and P. McBurney. Argumentation technology: Introduction to the special issue.
IEEE Intelligence Systems, 22(6):21–23, 2007.
15. K. N. Toshiko Wakaki. New Frontiers in Artificial Intelligence, volume 5447/2009 of Lecture
Notes in Computer Science, pages 254–269. 2009.
16. S. W. Uwe Egly, Sarah Alice Gaggl. Answer-set programming encodings for argumentation
frameworks. Technical report, DBAI, 2008.
45