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) [7] represents a prominent approach for performing non-monotonic reasoning. In fact it has given place to a new approach of logic programming with negation as failure. Usually an answer set program can be seen as a specification of a problem where each stable model of a program P represents possible solutions to the problem. Nowadays, there are efficient solvers such as dlv, clasp, and smodel. The efficiency of these answer set solvers have increased the list of the stable model semantics' applications, e.g., planning, bioinformatics, argumentation theory, etc.
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 [2,5,10,11]. Among these properties we can mention the existence of intended models in some normal logic programs. In fact, it is not hard to find a normal program which does not have stable models. However, the no existence of stable models for some normal program is not really a weakness because the no existence of stable models can be regarded as the no existence of solutions of a given problem. It all depends on the intended use of our logic programs. In the case of an approach motivated by argumentation theory it is desirable that normal programs (representing a dispute among arguments) always give an answer that infers the winning arguments in a dispute among arguments.
In argumentation theory, the philosophy of the stable model semantics is characterized by the so called stable argumentation semantics [6]. Like stable model semantics, stable argumentation semantics is undefined in some argumentation scenarios. Hence, it is not strange to find, in the literature, different extensions for both the stable model semantics and the stable argumentation semantics. On the one side, the extensions for the stable models semantics have been supported from different logic-based inference properties. On the other hand, the extensions for the stable argumentation semantics have been motivated mainly from counter-examples. Some authors in argumentation theory [1] have argued for supporting new argumentation semantics mainly by considering inferences reasoning properties. In this setting, argumentation semantics such as the semi-stable has been accepted as a good extension of the stable argumentation semantics. However, semi-stable argumentation still has been weak for satisfying properties such relevance [3,8]. Relevance is seemed to be a desired property for dealing with the non-existence of stable extensions.
Since abstract argumentation semantics were introduced [6], it was shown that these semantics can be viewed as a special form of logic programming semantics with negation as failure. Therefore, any extension of the stable argumentation semantics based on logic programming semantics looks as a sound approach for extending argumentation semantics based on logic-based inference.
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 [8]. In [8], an approach for extending logic programming semantics based on an abductive set of atoms was introduced. In this paper, this abductive set of atoms is characterized by classic-logic inference. Hence, by considering this set of abductive atoms, we generalize the stable model semantics by the so called strong generalized stable models. We show that these strong generalized stable models characterize a logic programming semantics which is based on paraconsistent logics, the so called p-stable models [9]. It is worth mentioning that the p-stable models capture the stable model semantics.
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 be-tween 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.
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.
We review some basic concepts of the preferred argumentation semantics defined by Dung [6] and some results about how to regard his argumentation approach as logic programming with negation as failure. The basic structure of Dung's argumentation approach is an argumentation framework which captures the relationships between the arguments. 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 S) if c is attacked by an argument in S. For instance in Figure 1, {a, b} attacks c. 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 (d, c), (d, e), (e, d)} has two stable extensions: {a, d} and {a, c, e}.
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 {a 1 , ..., a n }, we write ¬{a 1 , ..., a n } to denote the set of atoms {¬a 1 , ...,
where a and each of the b i are atoms for 1 ≤ i ≤ n + m. In a slight abuse of notation, we will denote such a clause by the formula a ← B + ∪ ¬B − where the set {b 1 , . . . , b n } will be denoted by B + , and the set {b n+1 , . . . , b n+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 L P , 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 [12]. An interpretation M is called a (2-valued classical) model of P if and only if for each clause c ∈ P , M (c) = 1. We say that c is a logic consequence of P , denoted by P c, if every model M of P holds that M (c) = 1.
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 [12].
Stable model semantics. The stable model semantics was defined in terms of the so called Gelfond-Lifschitz reduction [7] and it is usually studied in the context of syntax dependent transformations on programs. The following definition of a stable model for normal programs was presented in [7].
Let us recall that a normal positive program always has minimal models. Definition 5. Let P be a normal program. For a set S ⊆ L P 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 . 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 ⊆ L P , 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. [9] Let P be a normal program and M be a set of atoms. We define
Now, we define the p-stable semantics for normal programs (introduced in [9]).
Definition 7. [9] Let P be a normal program and M be a set of atoms. We say that M is a p-stable model of P if RED(P, M ) M . We will denote by p-stable(P) the set of all p-stable models of P . We can verify that RED(P, M ) is: {a ← ¬b, a ← b, b ← a}. We see that M is 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, M X be sets of atoms. We say that M X is a strong generalized stable model of P if M X is a stable model of P ∪ X and X ⊆ {y | RED(P, M X ) y}.
We define a partial order on the set of strong generalized stable models of a program. Definition 9. Let M X 1 and M X 2 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:
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 M X 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. 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.
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 . From ( 1) and (i ) it follows that M is a minimal model of R(P ∪ 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 M X in the Definition 10 with X = M ).
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 [8] which consists of the following steps: First, given an argumentation framework AF , we use a particular mapping that associates to AF a normal program denoted by P AF . Second, we obtain the stable abducible models of P AF . Finally, we use a second mapping, called f , to obtain the stable argumentation semantics of AF . The mapping f assigns to each stable abducible model of P AF a set of arguments from the argumentation framework AF . 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. [8] Let AF = AR, attacks be an argumentation framework, P D AF = x∈AR {d(x) ← ¬d(y) | (y, x) ∈ attacks} and P E AF = x∈AR {∪ y:(y,x)∈attacks {d(x) ← ∧ z:(z,y)∈attacks d(z)}}. We define:
For a given atom x in the definition of P E AF there may not be a z as described, in that case the corresponding conjunction ∧ z:(z,y)∈attacks d(z) is empty leaving the fact d(x) ← in P E AF . The reader familiar with argumentation theory can observe that essentially, P D AF captures the basic principle of conflict-freeness [8].
[3] Now, we illustrate the mapping P AF , let AF be the argumentation framework of Figure 1. We can see that P AF = P D AF ∪ P E AF where,
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 P AF . Specifically, it assigns the set of arguments that does not appear as defeated arguments in the stable abducible model of P AF . 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 Ext s a (AF ).
Definition 13. Let AF = AR, Attacks be an argumentation framework. The stable abducible argumentation semantics of AF , denoted by Ext s a , is defined as follows:
where f is the mapping from 2 L P AF to 2 AR , such that
Let us consider the argumentation framework AF of Figure 1 and its normal program P AF previously obtained in Example 4. We are going to obtain the stable abducible argumentation semantics of AF , namely Ext s a (AF ). First of all, we have to obtain the stable abducible semantics of P AF . It is not difficult to verify that stable abducible(P AF ) corresponds to the following set: { {d(a), d(c)} }. Hence, Ext s 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 [3] also has a similar relationship with these two argumentation semantics. As future work, it would be interesting to explore the relation between the semi-stable semantics and the stable abducible argumentation semantics.
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) 4) when AF has at least an stable extension, it holds that Ext s a (AF ) = stable extensions(AF ) Proof. In [6] it is proven that the preferred semantics of an AF is not empty, hence the p-stable semantics of P AF is not empty. Since, the stable abducible(P AF ) is defined as the set of p-stable models of P AF that satisfies certain minimality conditions, then stable abducible(P AF ) = ∅. Therefore, Ext s a (AF ) = ∅. This proves (1).
It is clear from the definition of stable abducible logic programming semantics that if P is a normal program and M ∈ stable(P AF ) then M ∈ stable abducible(P AF ), and that stable abducible(P AF ) ⊆ p − stable(P AF ). In fact, let us observe that if stable(P AF ) = ∅ then stable(P AF ) = stable abducible(P AF ), for if M ∈ stable(P AF ), it is known that M ∈p-stable(P AF ), and therefore M satisfies the definition of stable abducible(P AF ) with X = ∅. We then have: stable(P AF ) ⊆ stable abducible(P AF ) ⊆ p-stable(P AF ). 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 )⊆ Ext s 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 P AF has at least one stable model, then stable(P AF ) = stable abducible(P AF ). We conclude that stable extensions(AF )= Ext s a (AF ).
The converse of Theorem 3 does not hold. That is, it is not the case that each extension in Ext s a (AF ) is also a stable extension, see below Example 6; and it is not the case that each preferred extension is also in Ext s 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 Ext s a (AF ) = {{d, b}}. We can see that Ext s a (AF ) does not coincides with the set of stable extensions of AF , i.e., Ext s a (AF ) = stable extensions(AF ). (b, c), (c, d), (d, e), (e, c)}. We can see that L = {a} is a preferred extension and L ∈ Ext s a (AF ). The only stable abducible extension is {b, d}.
Now, we present the definition of weak relevance for argumentation frameworks which is called relevant by Caminada in [3]. Definition 14. Let AF = AR, Attacks be an argumentation framework. An argument a ∈ AR is weakly relevant w.r.t. an argument b ∈ AR if and only if there exists an undirected path between a and b.
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. The following theorem indicates that irrelevant arguments do not determine whether an argument is justified under the stable abducible argumentation semantics. Proof. Sketch.
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.
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 [3]. 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.
Definition 11. [4] Two programs P 1 and P 2 are equivalent, denoted by P 1 ≡ P 2 , if P 1 and P 2 have the same 2-valued models. Equivalently, if their sets of rules are equivalent in classical logic.
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
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 ).
(