=Paper=
{{Paper
|id=None
|storemode=property
|title=Characterizing stage argumentation semantics
based on stable abducible semantics
|pdfUrl=https://ceur-ws.org/Vol-1659/paper6.pdf
|volume=Vol-1659
|authors=Mauricio Osorio,José Luis Carballido,Claudia Zepeda
|dblpUrl=https://dblp.org/rec/conf/lanmr/OsorioCZ16
}}
==Characterizing stage argumentation semantics
based on stable abducible semantics==
https://ceur-ws.org/Vol-1659/paper6.pdf
Characterizing stage argumentation semantics
based on stable abducible semantics
Mauricio Osorio1 , José Luis Carballido2 , and Claudia Zepeda2
1
Universidad de las Américas-Puebla,
osoriomauri@gmail.com
2
Benemérita Universidad Atónoma de Puebla
{jlcarballido7,czepedac}@gmail.com
Abstract We define a new logic programming semantics in terms of ab-
ducible atoms. We use it to characterize the stage extensions of an argu-
mentation framework AF by means of an associated normal program PAF .
We also define the stage semantics for a special type of normal programs
and present a similar characterization.
Keywords: Argumentation semantics, stage argumentation semantics, logic
programming semantics.
1 Introduction
Answer Set Programming (ASP) [7] has long being established as a new tool to
handle incomplete and inconsistent information. ASP is based on the stable model
(answer set) semantics of logic programming [5]. Its scope of applications includes
areas like planning, logical agents and artificial intelligence. It is well known that
not every logic program has stable models (or answer sets), however the implemen-
tation of stable abducible logic programming semantics is intended to fill this gap:
by adding facts (abducible atoms) to the original logic program P we can define a
new type of models for P . Stable abducible logic programming semantics has been
used in different ways, for instance to restore consistency [1]. Following [6,1], we
add abducible atoms to a program that does not have answer sets, but whereas
for the authors of [1] those atoms might not appear in the original language of
the program, we choose to select abducible atoms from the 2-valued models of the
given program. As some authors have done before [2], we associate a normal logic
program PAF to an argumentation framework AF in order to define a semantics
of extensions in terms of a logic programming semantics.
The contribution is the following:
– We characterize the stage logic programming semantics of n-programs (defini-
tion 12) in terms of the classical stable m-ab-m logic programming semantics
just defined (Theorem 5). Namely we establish a one to one correspondence
between the stage models of P and the classical stable m-ab-m models of P .
– We use this last result to characterize the stage argumentation semantics of an
argumentation framework in terms of the stable-abducible logic programming
semantics just defined (Corollary 1). According to this result the stage argu-
mentation semantics can be defined via a logic programming semantics with
abducible atoms.
41
The rest of the paper is divided as follows: In §2, we present some basic con-
cepts w.r.t. logic programming and argumentation theory. In §3, we characterize
the stage argumentation semantics of an argumentation framework based on a
stable abducible logic programming semantics. In the last section, we present our
conclusions.
2 Background
In this section, we review some theory about logic programming semantics and
argumentation semantics.
2.1 Logic programming semantics
A signature L is a finite set of elements that we call atoms. A literal is either an
atom a, called positive literal ; or the negation of an atom ¬a, called negative literal.
A normal clause is a clause of the form a ← b1 ∧ . . . ∧ bn ∧ ¬bn+1 ∧ . . . ∧ ¬bn+m
where a and each of the bi are atoms for 1 ≤ i ≤ n + m; a is called the head and
b1 ∧ . . . ∧ bn ∧ ¬bn+1 ∧ . . . ∧ ¬bn+m is called the body of the normal clause. If the
body of a normal clause is empty, then the clause is known as a fact and can be
denoted just by: a ← or a ← ⊤. We define a normal logic program P , as a finite set
of normal clauses. By normal program we will mean a normal logic program when
ambiguity does not arise. We define an n-program P , as a normal logic program
where every clause is of the form a ← ¬b. We write LP , to denote the set of atoms
that appear in the clauses of P . We want to point out that our negation symbol,
¬, corresponds to “not” in the standard use of Logic Programming.
From now on, we assume that the reader is familiar with the notion of an
interpretation and validity [9]. An interpretation M is called a 2-valued classical
model of P if and only if for each clause c ∈ P , M (c) = 1. By 2-valued model we
will mean a 2-valued classical model when ambiguity does not arise.
In this paper, a logic programming semantics S is a mapping defined on the
family of all programs which associates to a given program a subset of its 2-valued
models. We say that M is a minimal model of P if and only if there does not exist
a model M ′ of P such that M ′ ⊂ M [9].
2.2 Stable model semantics.
The stable model semantics was defined in terms of the so called Gelfond-Lifschitz
reduction [5]. Let us recall that a normal positive program always has a unique
minimal model.
Definition 1. Let P be a normal program. For a set M ⊆ LP we define the
program P M obtained from P by deleting each clause that has a literal ¬l in its
body with l ∈ M , and then all literals of the form ¬l in the bodies of the remaining
clauses. Clearly P M does not contain the symbol ¬. M is a stable model of P if
and only if M is a minimal model of P M . We will denote by stable(P) the set of
all stable models of P .
42
2.3 Argumentation theory
We review some basic concepts of the stage argumentation semantics defined by
Verheij [10]. First, we define an argumentation framework.
Definition 2. [4] An argumentation framework is a pair AF := ⟨AR, attacks⟩,
where AR is a finite set of arguments, and attacks is a binary relation on AR,
i.e., attacks ⊆ AR × AR.
Example 1. Let AF := ⟨{a, b, c, d}, {(a, a), (a, c), (b, c), (c, d)}⟩ be an argumenta-
tion framework.
We say that a attacks c (or c is attacked by a) if (a, c) ∈ attacks holds. Similarly,
we say that a set S of arguments attacks c (or c is attacked by S) if c is attacked
by an argument in S.
Intuitively speaking, for a set of arguments to be an extension of an argumenta-
tion framework, it is necessary that all of its arguments are consistent in the sense
that there are no attacks between them. The next definition states this idea.
Definition 3. [4] Let AF := ⟨AR, attacks⟩ be an argumentation framework and
S ⊆ AR. S is said to be conflict-free if there are no arguments a, b in S such that
a attacks b.
Now we present the definition of stage argumentation semantics. Given a set S
of arguments, S + = {b ∈ AR | ∃a ∈ S such that (a, b) ∈ attacks}.
Definition 4. [10] Let AF := ⟨AR, attacks⟩ be an argumentation framework. E
is a stage extension iff E is a conflict free set and E ∪ E + is maximal with respect
to set-inclusion.
Example 2. From definition 4, it follows that the set {b, d} is the only stage exten-
sion of the argumentation framework of Example 1.
2.4 Mapping from argumentation to logic programming
In [3], the authors show that it is possible to characterize semantics in argumenta-
tion framework with semantics in logic programming by means of a mapping. The
mapping defined in [3] associates a logic program PAF to an argumentation frame-
work AF . We present that characterization which is defined in terms of the clauses
that contain negative literals in their bodies. Hereafter and by abuse of notation,
we use PAF to denote this part of the mapping. We use the predicate d(x) to repre-
sent that “the argument x is defeated”, then the clauses such as d(x) ← ¬d(y) are
used to capture the idea that argument x is defeated when anyone of its adversaries
y is not defeated.
∪ 5. [3] Let AF = ⟨AR, attacks⟩ be an argumentation framework, then
Definition
PAF = x∈AR {d(x) ← ¬d(y) | (y, x) ∈ attacks}. We say that PAF is the normal
program associated to AF .
43
Example 3. Let AF be the argumentation framework of Example 1. We can see
that PAF = { d(a) ← ¬d(a), d(c) ← ¬d(a), d(c) ← ¬d(b), d(d) ← ¬d(c)}.
Now, we describe the characterization of stage extensions of an argumentation
framework AF in terms of the stage models of the normal program PAF . Here,
F acts is defined as a function on normal programs which returns the facts which
are present in a given normal program.
Definition 6. [8] Let AF = ⟨AR, Attacks⟩ be an argumentation framework and
M be a 2-valued model of PAF . M is a stage model of PAF iff M \ F acts((PAF )M )
is minimal with respect to set inclusion. Observe that F acts((PAF )M ) = (PAF )M .
We define the following mapping from 2LPAF to 2AR as E(M ) = {x|d(x) ∈
(LPAF \ M )}.
Theorem 1. [8] Let AF := ⟨AR, attacks⟩ be an argumentation framework. M is
a stage model of PAF iff E(M ) is a stage extension of AF .
Example 4. We can see that according to example 3, the normal program PAF of
the argumentation framework AF of Example 1 has five 2-valued models: {d(a), d(b), d(c), d(d)},
{d(a), d(c), d(d)}, {d(a), d(b), d(d)}, {d(a), d(b), d(c)}, and {d(a), d(c)}. Moreover,
we can verify that M = {d(a), d(c)} is the only stage model of PAF since M \
F acts((PAF )M ) is minimal with respect to set inclusion. Hence, according to The-
orem 1, {b, d} is the only stage extension of AF , which coincides with the result
showed in example 2.
We remark that definition 6 of a stage model can be obtained straightforwardly
from the definition of stage model in [8]. In [8], the authors express a stage model
in terms of the maximality of a set, for convenience we use a minimality condition
on a different set, both definitions are equivalent.
3 Abductive Logic programs and its applications in
argumentation
We use the idea of abducible atom to define a semantics on a very special class
of normal programs. The obtained semantics allows us to characterize the stage
extensions of an argumentation framework by means of the models of the related
normal program defined by this new semantics.
In what follows, the symbol ( means proper subset.
3.1 Abductive logic programs
The classical stable ab-m semantics of a normal program is the particular version
of the stable abducible logic programming semantics [6], where the abducibles are
taken from 2-valued models of the given program, in opposition to the general case
where the atoms are taken from a given arbitrary set.
In this subsection, we define our main semantics for normal programs, called
classical m-ab-m semantics, which is used to characterize the stage argumentation
44
semantics of an argumentation framework. Moreover, we describe two properties
of the classical m-ab-m semantics which are suitable for that characterization.
In order to define the classical m-ab-m semantics of normal programs, we define
a partial order on the set of classical ab-m models and then we find the set of
minimal classical ab-m models; these minimal elements define the classical m-ab-m
semantics.
We state the following useful fact as an observation.
Observation 1 : For any normal program P whose stable semantics is empty,
the program P ∪ LP has LP as a stable model. Here, each element of LP as a rule
in a normal program is interpreted as a fact.
Now, we define the classical stable ab-m semantics of a normal program, where
the sets of abducible atoms are taken from 2-valued models of the program. We
define also the stable m-ab-m semantics of a normal program.
Definition 7. Let M be a 2-valued model of a normal program P and Ab ⊆ M .
We say that the pair ⟨M, Ab⟩ denoted by MAb is a classical stable ab-m model of
P if M is a stable model of P ∪ Ab.
Definition 8. Let MAb be a classical stable ab-m model of a normal program P
with Ab ⊆ M . We say that the pair MAb is a classical stable m-ab-m model of P if
there does not exist another classical stable ab-m model NAb1 such that Ab1 ( Ab.
Example 5. Let P = {a ← ¬b b ← ¬c, c ← ¬a}. We can verify that P does not
have stable models. Table 1 shows the classical stable ab-m models of P respect to
each of the three 2-valued models of P . From Table 1, we can see that the classical
stable m-ab-m semantics of P is: {⟨{a, b}, {a}⟩, ⟨{b, c}, {b}⟩, ⟨{a, c}, {c}⟩}.
Table 1. Classical stable ab-m models of P
Model Abducibles classical stable ab-m model
{a, c} {c} ⟨{a, c}, {c}⟩
{b, c} {b} ⟨{b, c}, {b}⟩
{a, b} {a} ⟨{a, b}, {a}⟩
Now, we state two consequences of observation 1 related to the classical m-ab-m
semantics of a normal program.
Theorem 2. Let P be a normal program.
1. If the stable semantics of P is not empty, then the classical stable m-ab-m
semantics of P coincides with the stable semantics of P .
2. The classical stable m-ab-m semantics of P is always defined.
Definitions 7 and 8 could be extended to more general programs, for example
disjunctive programs.
45
3.2 n-programs
Here, we analyze the classical stable m-ab-m semantics for n-programs. We define
several semantics in terms of abducible atoms and look at some of their properties.
Then we characterize the stage extensions of an argumentation framework AF
based on one of these new semantics when they are applied to the associated n-
program PAF .
We recall from section 2 that a n-program is a normal logic program where
every clause is of the form a ← ¬b.
Now, we analyze some consequences of definitions 7 and 8 for the particular
case of n-programs.
Lemma 1. Let M be a model of a n-program P and let Ab ⊆ M , then MAb is a
classical stable ab-m model of P iff P M ∪ Ab = M .
Note that (P ∪ Ab)M = P M ∪ Ab.
Let us remark that in definition 8, M and N can be different, so the sets of
abducible atoms can be obtained from different sets. A particular case of defini-
tion 8 is given when the partial order among the classical stable ab-m models of
a n-program is defined respect to the set of abducible atoms but these subsets of
abducibles are taken from the same set of atoms. This corresponds to the definition
of classical normal stable ab-m semantics of a n-program.
Definition 9. Let MAb be a classical stable ab-m model of a n-program P with
Ab ⊆ M . We say that the pair ⟨M, Ab⟩ is a classical normal stable ab-m model
of P if there does not exist another classical stable ab-m model MAb1 such that
Ab1 ( Ab.
The next result tell us that, for a fixed model M of P there is always exactly
one classical normal stable ab-m model of P .
Lemma 2. Let P be any n-program.
1. For a given M , if MAb1 and MAb2 are two classical stable ab-m models of P ,
then M(Ab1∩Ab2) is a classical stable ab-m model of P .
2. Classical normal stable ab-m models for P always exist and for a given M a
classical normal stable ab-m model MAb of P is unique.
3. If MAb is a classical normal stable ab-m model of P then P M ∪ Ab = M and
P M ∩ Ab = ∅.
Definition 10. Let MAb be a classical normal stable ab-m model of a n-program
P with Ab ⊆ M . We say that the pair MAb is a classical normal stable m-ab-m
model of P if there does not exist another classical normal stable ab-m model of
P , NAb1 such that Ab1 ( Ab.
Example 6. Let us consider again the program PAF of the argumentation frame-
work AF of Example 1. Table 2 shows the classical stable ab-m models of PAF
respect to each of the five classical 2-valued models of PAF . For convenience, we
drop the prefix d of the atoms, for instance, for d(a) we only write a.
From Table 2, we can see the following:
46
Table 2. Classical stable ab-m models of PAF
Model Abducibles classical stable ab-m model
{a, c} {a} ⟨{a, c}, {a}⟩
{a, b, c} {a, b, c} ⟨{a, b, c}, {a, b, c}⟩
{a, b, d} {a, b} ⟨{a, b, d}, {a, b}⟩
{a, c, d} {a, d} ⟨{a, c, d}, {a, d}⟩
{a, b, c, d} {a, b, c, d} ⟨{a, b, c, d}, {a, b, c, d}⟩
1. The only classical stable m-ab-m model of PAF is ⟨{a, c}, {a}⟩.
2. The classical normal stable ab-m models of PAF are: ⟨{a, c}, {a}⟩, ⟨{a, b, c}, {a, b, c}⟩,
⟨{a, b, d}, {a, b}⟩, ⟨{a, c, d}, {a, d}⟩, and ⟨{a, b, c, d}, {a, b, c, d}⟩.
3. The only classical normal stable m-ab-m model of PAF is ⟨{a, c}, {a}⟩.
Finally, we prove that the classical normal stable m-ab-m semantics coincides
with the classical stable m-ab-m semantics of a given n-program.
Theorem 3. Let M be a model of a n-program P and Ab ⊆ M . MAb is a classical
normal stable m-ab-m model of P iff MAb is a classical stable m-ab-m model of P .
In next subsection, we characterize the stage argumentation semantics of an
Argumentation Framework AF based on the classical normal stable ab-m logic
programming semantics and classical stable m-ab-m logic programming semantics
when they are applied to the associated n-program PAF .
3.3 Characterization of stage argumentation semantics based on
classical stable ab-m semantics
In this section, we define the stage semantics for n-programs. We will see that this
semantics corresponds to the stage semantics of an argumentation framework under
the mapping presented in definition 5. Next we will show in one of our main results
(Theorem 5), that for n-programs this semantics can be characterized in terms of
the classical stable m-ab-m semantics. As a consequence of this result we prove
also that the stage semantics of an argumentation framework AF corresponds to
the classical m-ab-m semantics of the associated program PAF (Corollary 1). With
these results we see that the semantics we have defined in terms of abducible atoms
offer an alternative to define the semantics of stage extensions of an argumentation
framework as well as the stage semantics for n-programs. The definition of stage
logic programming semantics is based on an auxiliar logic programming semantics,
called c-Stage.
Definition 11. Let P be a n-program and M be a model of P . We say that the
pair ⟨M, (M \ P M )⟩ denoted by MX is a c-Stage-model of P . Here X = M \ P M .
Theorem 4. Let P be a n-program and M be a model of P . Let X be a set of
atoms. Then MX is classical normal stable ab-m model of P iff MX is a c-Stage-
model of P .
47
Definition 12. Let P be a n-program and MX be a c-Stage model of P . We say
that the pair MX is a stage-model of P if there does not exist a c-Stage model NX1
of P such that X1 ( X.
As we mentioned before, some of the semantics for logic programs as well as
for argumentation frameworks can be defined in terms of semantics with abducible
atoms. The next result, which is one of our main contributions, shows that for n-
programs the stage semantics and the classical stable m-ab-m sematics are equiv-
alent.
Theorem 5. Let P be a n-program, M be a model of P and let X ⊂ LP . MX is
a classical stable m-ab-m model of P iff MX is a stage-model of P .
Example 7. Let us consider again the program PAF of the argumentation frame-
work AF of Example 1. Table 3 shows the c-Stage models of PAF respect to each
of the five classical 2-valued models of PAF .
Table 3. c-Stage models of PAF
Model c-Stage model
{a, c} ⟨{a, c}, {a}⟩
{a, b, c} ⟨{a, b, c}, {a, b, c}⟩
{a, b, d} ⟨{a, b, d}, {a, b}⟩
{a, c, d} ⟨{a, c, d}, {a, d}⟩
{a, b, c, d} ⟨{a, b, c, d}, {a, b, c, d}⟩
From Table 3, we can see the following:
1. The set of c-Stage models of PAF coincides with the set of classical normal
stable ab-m models of PAF , as Theorem 4 indicates.
2. The only stage-model of PAF is ⟨{a, c}, {a}⟩.
3. The stage-model ⟨{a, c}, {a}⟩ is also the only classical stable m-ab-m model of
PAF , as Theorem 5 indicates.
We are now ready to present our second result, which is the characterization of
the stage extensions of an argumentation framework in terms of the classical stable
m-ab-m semantics for n-programs.
Corollary 1. Let AF := ⟨AR, attacks⟩ be an argumentation framework and PAF
be its associated n-program, then the stage extension semantics of AF is charac-
terized by the classical stable m-ab-m semantics of PAF .
Example 8. Let us take again the argumentation framework AF defined in Exam-
ple 1. As we have seen in example 7 the only classical stable m-ab-m model of PAF
is ⟨{a, c}, {a}⟩ which is also the only stage model of PAF . According to Theorem 1,
the only stage extension of AF is the set {b, d} which is the image of the set {a, c}
under the mapping E (see definition of mapping E in section 2.4). This coincides
with the result of example 4.
48
4 Conclusions
We recall the definition of the stage logic programming semantics for a very simple
type of normal programs, the n-programs, and we studied the relations between
this semantics and the semantics of stage extension for argumentation frameworks.
The n-programs we have defined here, besides having a simple structure, have the
property that any of them is the associated normal program of an argumenta-
tion framework. We characterized both semantics in terms of an abductive logic
programming semantics, the classical stable m-ab-m semantics.
References
1. M. Balduccini and M. Gelfond. Logic programs with consistency-restoring rules.
In International Symposium on Logical Formalization of Commonsense Reasoning,
AAAI 2003 Spring Symposium Series, pages 9–18, 2003.
2. M. Caminada, S. Sá, J. Alcântara, and W. Dvořák. On the equivalence between
logic programming semantics and argumentation semantics. International Journal of
Approximate Reasoning, 58:87–111, 2015.
3. J. L. Carballido, J. C. Nieves, and M. Osorio. Inferring Preferred Extensions by
Pstable Semantics. Revista Iberomericana de Inteligencia Artificial, 13(41):38–53,
2009.
4. P. M. Dung. On the acceptability of arguments and its fundamental role in non-
monotonic reasoning, logic programming and n-person games. Artificial Intelligence,
77(2):321–358, 1995.
5. M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming.
In R. Kowalski and K. Bowen, editors, 5th Conference on Logic Programming, pages
1070–1080. MIT Press, 1988.
6. A. C. Kakas. Generalized stable models: a semantics for abduction. In Proc. ECAI’90,
pages 385–391, 1990.
7. V. Lifschitz. What is answer set programming?. In AAAI, volume 8, pages 1594–1597,
2008.
8. M. Osorio and J. C. Nieves. Range-based argumentation semantics as 2-valued mod-
els. To appear in Theory and Practice of Logic Programming, 2016.
9. D. van Dalen. Logic and structure. Springer-Verlag, Berlin, 3rd., augmented edition,
1994.
10. B. Verheij. Two approaches to dialectical argumentation: admissible sets and argu-
mentation stages. Proc. NAIC, 96:357–368, 1996.
49