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