We look at a general way of inducing semantics in argumentation theory by means of a mapping defined on the family of 2-valued models of a normal program, which is constructed in terms of the argumentation framework. In this way we define a new argumentation semantics called stable abducible which lies in between the stable and the preferred semantics. The relevance of this new semantics is that it is nonempty for any argumentation framework, and coincides with the stable argumentation semantics whenever this is non-empty. We study some of the properties of this semantics.
In the non-monotonic reasoning community, it is well-accepted that the stable
model semantics (also called answer set semantics) [
Even though the stable model semantics enjoys a good reputation in the
nonmonotonic reasoning community, it is also well-known that the stable model
semantics does not satisfy some desired properties pointed out by several authors
[
In argumentation theory, the philosophy of the stable model semantics is
characterized by the so called stable argumentation semantics [
Since abstract argumentation semantics were introduced [
In this paper, we study an extension of the stable argumentation semantics
based on logic-based inference. To this end, we consider the abductive approach
introduced in [
On the argumentation side, by considering a declarative specification of admissible sets in terms of logic normal programs and an order between strong generalized stable models, an abductive stable argumentation semantics is introduced. We show that this abductive stable argumentation semantics is an extension of the stable argumentation semantics and has a similar behavior to that of the semi-stable semantics. Moreover, a relationship between the abducible stable semantics and the preferred semantics is proved. In the last part of the paper, we show that the abducible stable argumentation semantics satisfies some intuitions of relevance.
The rest of the paper is divided as follows: In §2, we present some basic concepts w.r.t. logic programming and argumentation theory. In §3, we define a new logic programming semantics that we call stable abducible based on the concept of strong generalized stable models. In §4, we review the relationships between two argumentation semantics and the stable abducible logic programming semantics. Theorem 3 is our main contribution. In §5, we review the definition of weak relevance for argumentation frameworks. Theorem 4 is our contribution in this section. In the last section, we present our conclusions. 2
In this section, we review some theory about argumentation semantics and logic programming semantics. We present a short description of Dung’s argumentation approaches, and also the definitions of the logic programming semantics stable and p-stable for normal programs. 2.1
We review some basic concepts of the preferred argumentation semantics defined
by Dung [
Definition 1. 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.
Any argumentation framework can be regarded as a directed graph. For instance, if AF := {a, b, c, d}, {(a, a), (a, c), (b, c), (c, d)} , then AF is represented as in Figure 1. We say that a attacks c (or c is attacked by a) if attacks(a, c) holds. Similarly, we say that a set S of arguments attacks c (or c is attacked by
c.
Given an argumentation framework AF = AR, attacks , if A ⊆ AR then we write AF |A as a shorthand for A, {(a, b)|(a, b) ∈ attacks and a, b ∈ A} .
Dung defined his argumentation semantics based on the basic concept of admissible set. Definition 2. 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. 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. A conflict-free set of arguments S is admissible if and only if each argument in S is acceptable w.r.t. S.
Definition 3. A preferred extension of an argumentation framework AF is a maximal (w.r.t. inclusion) admissible set of AF . The set of preferred extensions of AF , denoted by preferred extensions(AF ), will be referred to as the preferred semantics of AF .
The only preferred extension of the argumentation framework of Figure 1 is {b, d}.
Definition 4. Let AF := AR, attacks be an argumentation framework. We say that E ⊆ AR is an stable extension of AF if E is an admissible set of AF that attacks every argument in AR \ E. The set of stable extensions of AF , denoted by stable extensions(AF ), will be referred to as the stable semantics of AF .
The argumentation framework of Figure 1 does not have stable extensions. The argumentation framework defined as AF1 = {a, b, c, d, e}, {(a, b), (c, b), (c, d), (d, c), (d, e), (e, d)} has two stable extensions: {a, d} and {a, c, e}. 2.2
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. Given a set of atoms {a1, ..., an}, we write ¬{a1, ..., an} to denote the set of atoms {¬a1, ..., ¬an}. A normal clause, C, is a clause of the form a ← b1 ∧ . . . ∧ bn ∧ ¬bn+1 ∧ . . . ∧ ¬bn+m where a and each of the bi are atoms for
the formula a ← B+ ∪ ¬B− where the set {b1, . . . , bn} will be denoted by B+, and the set {bn+1, . . . , bn+m} will be denoted by B−. Given a normal clause a ← B+ ∪ ¬B−, denoted by r, we say that a = H(r) is the head and B+(r) ∪ ¬B−(r) is the body of the clause. If the body of a 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. We write LP , to denote the set of atoms that appear in the clauses of P . We denote by Head(P ) the set {a | a ← B+ ∪ ¬B− ∈ P }. From now on, by program we will mean a normal logic program when ambiguity does not arise. 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 [
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
2valued (classical) 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 , M = M [
Let us recall that a normal positive program always has minimal models. Definition 5. Let P be a normal program. For a set S ⊆ LP we define the program P S from P by deleting each rule that has a literal ¬l in its body with l ∈ S, and then all literals of the form ¬l in the bodies of the remaining rules. Clearly P S does not contain ¬. S is a stable model of P if and only if S is a minimal model of P S . We will denote by stable(P) the set of all stable models of P .
Example 1. Let S = {b} and P = {b ← ¬a, c ← ¬b, b ←, c ← a}. Notice that P S has three models: { }
b , {b, c} and {a, b, c}. Since the minimal model among
these models is {b}, we can say that S is a stable model of P .
p-stable semantics. Logical inference in propositional classical logic is denoted
by . Given a set of proposition symbols S and a theory (a set of well-formed
formulae) Γ , Γ S if and only if ∀s ∈ S, Γ s. When we treat a program as a
theory, each negative literal ¬a is regarded as the standard negation operator in
classical logic. Given a normal program P, if M ⊆ LP , we write P M when:
P M and M is a classical 2-valued model of P . The p-stable semantics is
defined in terms of a single reduction which is defined as follows:
Definition 6. [
RED(P, M ) = {a ← B+ ∪ ¬(B− ∩ M ) | a ← B+ ∪ ¬B− ∈ P }
Now, we define the p-stable semantics for normal programs (introduced in [
Example 2. Let us consider P = {a ← ¬b ∧ ¬c, a ← b, b ← a} and M = {a, b}.
a model of P since for each clause C of P we have that M evaluates C to true. We also see that RED(P, M ) M . Thus RED(P, M ) M and M is a p-stable model of P .
In this section, we define a new logic programming semantics with interesting properties in logic programming and argumentation, we call it stable abducible and corresponds to the set of the strong generalized stable models of a given normal program. The strong generalized stable models correspond to the stable models of the given normal program joined to a particular subset of facts. In this paper, the stable abducible semantics will help to characterize some argumentation semantics in terms of logic programming.
Definition 8. Let P be a normal program and X, MX be sets of atoms. We say that MX is a strong generalized stable model of P if MX is a stable model of P ∪ X and X ⊆ {y | RED(P, MX ) y}.
We define a partial order on the set of strong generalized stable models of a program.
Definition 9. Let MX1 and MX2 be two strong generalized stable models of a program P . We define a partial order between these two strong generalized stable models of P as follows: MX1 < MX2 , if X1 ⊂ X2.
Now we present the definition of the minimal strong generalized stable model of P .
Definition 10. Let P be a normal program. We say that MX is a stable abducible model of P , if it is a minimal strong generalized stable model of P with respect to the partial order <.
We will denote by stable abducible(P ) the set of all stable abducible models of P . It is clear that a stable model of P is a stable abducible model of P since it is a strong generalized stable model of P with X = ∅.
The following two examples illustrate our new logic programming semantics. Example 3. Let P = {a ← b, b ← ¬a}. We can verify that P does not have stable models. a) Let M = {a} and X = {a}. In this case, P ∪ X = {a ←, a ← b, b ← ¬a.} So, M is a stable model of P ∪ X, RED(P, M ) = {a ← b, b ← ¬a}, A = {y | RED(P, M ) y} = {a}, and X ⊆ A. Hence M is a strong generalized stable model of P . b) Let M = {a, b}, and X = {b}. In this case, P ∪X = {b ←, a ← b, b ← ¬a} So, M is a stable model of P ∪ X, RED(P, M ) = {a ← b, b ← ¬a.}, A = {y | RED(P, M ) y} = {a}, however X is not a subset of A. Hence M is not a strong generalized stable model of P .
Finally, since {a} is minimal, the stable abducible(P ) = {{a}}.
Next we present a theorem that shows that the strong generalized stable
models of a normal program are the same as its p-stable models. First we present
some lemmas and theorems useful to prove our main theorem.
Definition 11. [
Lemma 1. Let P be a normal program and let X, M be sets of atoms. If X ⊆ {y | RED(P, M ) y} then RED(P, M ) ≡ RED(P ∪ X, M ).
Proof. RED(P ∪ X, M ) = RED(P, M ) ∪ RED(X, M ). Hence, it is enough to show that RED(P, M ) RED(X, M ). But this is equivalent to the hypothesis X ⊆ {y | RED(P, M ) y}.
Theorem 1. If M is a strong generalized stable model of P then M is a p-stable model of P .
Proof. If M is a strong generalized stable model of P then there exists X such that (1) M is a stable model of P ∪ X. (2) X ⊆ {y | RED(P, M ) y}.
From (1) it follows that (i ) M is a classical model of P , since M models in classical logic P ∪ X and in particular it models P . (ii ) M is a p-stable model of P ∪ X since for normal programs the stable semantics is a subset of the p-stable semantics From (ii ) it follows that
(a) RED(P ∪ X, M ) M }.
From (a) and Lemma 1 we obtain
(b) RED(P ∪ X, M ) ≡ RED(P, M ).
From the last two relations (b) and (a) we obtain:
(c) RED(P, M ) M .
From (i ) and (c) it follows that M is a p-stable model of P .
Lemma 2. Let P be a normal program and M be a set of atoms. Then R(P ∪ M, M ) RED(P, M ), where R(T, M ) denotes the Gelfond and Lifschitz reduction of T with respect to M .
Proof. We consider two types of rules. (1) The positive rules of RED(P, M ) are also rules of R(P ∪ M, M ). (2) The negative rules of RED(P, M ) (the interesting case) are of the form r := x ← B+ ∪ ¬B−, where B− ⊆ M . Hence M B− and B− r. Hence M r but M ⊆ R(P ∪ M, M ). Therefore R(P ∪ M, M ) r.
Theorem 2. Let M be a p-stable model of the normal program P , then M is a strong generalized stable model of P . Proof. Let us assume that M is a p-stable model of P . Then (1) M is a classical model of P , and also of R(P, M ) (2) RED(P, M ) M .
It is clear that
(i ) R(P ∪ M, M ) M .
Hence,
(ii ) M is a stable model of P ∪ M .
Also,
(iii ) M ⊆ {y | RED(P, M )} by definition of p-stable model.
From (ii ) and (iii ) we conclude that M is a strong generalized stable model of
P (where M is the set MX in the Definition 10 with X = M ). 4
In this section, we review the relationships between two argumentation semantics
(the stable argumentation semantics and the preferred argumentation semantics)
and the stable abducible logic programming semantics. These relationships are
based on the proposal introduced in [
Now, we present the definitions of the two mappings and the theorem that specifies the relationship between the argumentation semantics and the stable ab− ducible logic programming semantics.
The first mapping uses the predicate d(x) to represent that “the argument x is defeated”. This mapping also includes clauses such as d(x) ← ¬d(y) to capture the idea of argument x is defeated when anyone of its adversaries y is not defeated.
Definition 12. [
PAF = PADF ∪ PAEF
in that case the corresponding conjunction ∧z:(z,y)∈attacksd(z) is empty leaving
the fact d(x) ← in PAEF . The reader familiar with argumentation theory can
observe that essentially, PADF captures the basic principle of conflict-freeness [
Now, we see how the second mapping, called f , can induce an argumentation semantics of an argumentation framework AF based on the stable abducible logic programming semantics. The mapping f assigns an extension (a set of accepted arguments) of AF to each stable abducible model of PAF . Specifically, it assigns the set of arguments that does not appear as defeated arguments in the stable abducible model of PAF . Each of these extensions will be called stable abducible extension. The induced argumentation semantics (the set of stable abducible extensions) of AF will be denoted by Exts a(AF ). Definition 13. Let AF = AR, Attacks be an argumentation framework. The stable abducible argumentation semantics of AF , denoted by Exts a, is defined as follows:
Exts a(AF ) = {N | N = f (M ), M ∈ stable abducible(PAF )} where f is the mapping from 2LPAF to 2AR, such that
f (M ) = {a | d(a) ∈ (LPAF \ M )} Example 5. Let us consider the argumentation framework AF of Figure 1 and its normal program PAF previously obtained in Example 4. We are going to obtain the stable abducible argumentation semantics of AF , namely Exts a(AF ). First of all, we have to obtain the stable abducible semantics of PAF . It is not difficult to verify that stable abducible(PAF ) corresponds to the following set: { {d(a), d(c)} }. Hence, Exts a(AF ) = {{d, b}}.
Now, we present the relationship between the stable abducible argumentation
semantics and two well known argumentation semantics: the stable
argumentation semantics and the preferred argumentation semantics. It is important to
remark that the semi-stable argumentation semantics defined by Caminada in
[
The following theorem shows four facts: there exists at least one stable abducible extension; a stable extension is also a stable abducible extension; a stable abducible extension is also a preferred extension; and if there exists at least one stable extension, then the stable abducible extensions coincide with the stable extensions.
Let us point out that, according to the next result, stable abducible extensions always exists, and in case the family of stable extensions of a program is non-empty, the two argumentation semantics coincide. Theorem 3. Let AF = AR, Attacks be an argumentation framework and L ⊆ AR, the following four statements hold: (1) Exts a(AF ) = ∅ (2) if L ∈ stable extensions(AF ) then L ∈ Exts a(AF ) (3) if L ∈ Exts a(AF ) then L ∈ pref erred extensions(AF ) (4) when AF has at least an stable extension, it holds that
Exts a(AF ) = stable extensions(AF )
Proof. In [
It is clear from the definition of stable abducible logic programming semantics that if P is a normal program and M ∈ stable(PAF ) then M ∈ stable abducible(PAF ), and that stable abducible(PAF ) ⊆ p − stable(PAF ). In fact, let us observe that if stable(PAF ) = ∅ then stable(PAF ) = stable abducible(PAF ), for if M ∈ stable(PAF ), it is known that M ∈p-stable(PAF ), and therefore M satisfies the definition of stable abducible(PAF ) with X = ∅.
We then have: stable(PAF ) ⊆ stable abducible(PAF ) ⊆ p-stable(PAF ). Since the stable semantics logic programming corresponds to the stable argumentation semantics and the p-stable semantics corresponds to the preferred argumentation semantics according to the mapping f of Definition 13, then we obtain stable extensions(AF )⊆ Exts a(AF ) ⊆ preferred extensions(AF ). This proves (2) and (3).
To prove (4), we observe that if AF has at least one stable extension then PAF has at least one stable model, then stable(PAF ) = stable abducible(PAF ). We conclude that stable extensions(AF )= Exts a(AF ).
The converse of Theorem 3 does not hold. That is, it is not the case that each extension in Exts a(AF ) is also a stable extension, see below Example 6; and it is not the case that each preferred extension is also in Exts a(AF ), see below Example 7.
Example 6. Let S be the stable abducible semantics. Let us consider the argumentation framework AF of Figure 1. In Example 5, we show that Exts a(AF ) = {{d, b}}. We can see that Exts a(AF ) does not coincides with the set of stable extensions of AF , i.e., Exts a(AF ) = stable extensions(AF ).
Example 7. Let us consider the argumentation framework AF = AR, attacks where AR = {a, b, c, d, e} and attacks = {(a, b), (b, a), (b, c), (c, d), (d, e), (e, c)}. We can see that L = {a} is a preferred extension and L ∈ Exts a(AF ). The only stable abducible extension is {b, d}. 5
Now, we present the definition of weak relevance for argumentation frameworks
which is called relevant by Caminada in [
If in Definition 14 we replace an undirected path between a and b with a directed path from a to b, we would be talking about a relevance relation which is stronger and which is used in the context of logic programming. Example 8. Let us consider the argumentation framework AF = AR, attacks where AR = {a, b, c, d} and attacks = {(a, a), (b, c), (c, d)}. In this AF , the arguments b, c, and d are weakly relevant with respect to each other, and argument a is not weakly relevant with respect to b, c and d. Yet, argument a is the reason why there is no stable extension containing b and d.
The following theorem indicates that irrelevant arguments do not determine whether an argument is justified under the stable abducible argumentation semantics.
Theorem 4. Let AF = AR, Attacks be an argumentation framework and let a ∈ AR and A ⊂ AR the set of all arguments that are weakly relevant w.r.t. a. 1. There exists a stable abducible extension of AF iff there exists a stable abducible extension of AF |A. 2. a is in every stable abducible extension of AF iff a is in every stable abducible extension of AF |A.
To prove this theorem first we should prove two things:
(1) If L is a stable abducible extension of AF then L∩A is a stable abducible extension of AF |A.
(2) If L is a stable abducible extension of AF |A then there exists a stable abducible extension L of AF with L ∩ A = L.
Finally, the theorem follows directly from these two results. 6
Argumentation theory and logic programming with negation as failure are two
approaches non-monotonicity which have been intensively explored the last years.
Moreover, these approaches share some common behaviors in their inference
process; in particular, by the relationships there exist between argumentation
semantics and logic programming semantics. In this paper, on the one hand, an
extension of the stable model semantics is introduced by the so called strong
generalized stable models. It is shown that the strong generalized stable models
capture the p-stable models (Theorem 2). By considering an order between strong
generalized stable models, the stable abducible semantics is defined. On the other
hand, by considering the stable abducible semantics, the stable abducible
argumentation semantics is defined. This new argumentation semantics is an
intermediate argumentation semantics between the stable argumentation semantics
and the preferred semantics (Theorem 3). It is shown that the stable
argumentation semantics is always defined and satisfies the notion of relevance introduced
by Caminada [
The results of Theorem 3 suggest that the stable abducible argumentation semantics has similar behavior to semi-stable semantics. Part of our future work will be to formalize the relationship between the stable abducible argumentation semantics and the semi-stable semantics. We want to point out that the stable abducible argumentation semantics does not characterize exactly the semi-stable semantics; because the stable abducible argumentation semantics satisfies a notion of relevance which semi-stable semantics does not satisfies. 7
This work was supported by the CONACyT [CB-2008-01 No.101581].