Comparing logic programming and formal argumentation; the case of ideal and eager semantics

1.Introduction

The connection between logic programming and formal argumentation has been studied starting from the landmark paper of Dung [24]. Subsequent work of Wu et al. [47] defined a translation from logic programs to (instantiated) argumentation frameworks where each argument consists of a derivation for a particular conclusion, using the rules of the logic program; weak negation is used to determine the attack relation between those arguments. The idea is that a derivation (argument) for conclusion p attacks any derivation (argument) that has a rule containing notp. Based on this translation, Wu et al. [47] were able to show that the 3-valued stable model semantics for logic programming corresponds to the complete semantics for formal argumentation. More specifically, the conclusions associated with the complete argument labellings of the resulting argumentation framework coincide with the 3-valued stable models of the logic program one started with.

The translation from logic programs to argumentation frameworks of Wu et al. [47] has subsequently been used to identify additional semantic correspondences between logic programs and their associated argumentation frameworks. For instance, Caminada et al. [16] used this translation to show the additional correspondence between well-founded semantics for logic programming and grounded semantics for formal argumentation, between 2-valued stable semantics for logic programming and stable semantics for formal argumentation, and between regular semantics for logic programming and preferred semantics for formal argumentation.11

In the current paper, we identify an additional correspondence between logic programming semantics and formal argumentation semantics: the correspondence between ideal semantics for logic programming and ideal semantics for formal argumentation. To do so, we will make use of a recent reformulation of ideal semantics for logic programming [17], which brings it closer to ideal semantics for formal argumentation.

The reformulation of ideal semantics for logic programming of [17] allows eager semantics for logic programming to be defined in a similar way. We then examine whether this coincides with eager semantics for formal argumentation. We will show that the answer is negative, and our analysis allows us to pinpoint where precisely the difference is.

The current work is part of a line of research that examines the expressiveness of formal argumentation. This is done by translating a particular formalism for non-monotonic reasoning to formal argumentation, and examining whether the conclusions yielded by the thus obtained argumentation formalism coincide with what is entailed by the non-monotonic reasoning formalism one started with. In his original 1995 AIJ paper, Dung did this for logic programming under the (2-valued) stable and well-founded semantics, as well as for Default Logic [24]. Follow-up research did this for Nute’s Defeasible Logic [27], Pollock’s oscar system [28] and for logic programming under 3-valued stable [47] and regular [16] semantics. It has to be mentioned that not all forms of non-monotonic reasoning can be captured by formal argumentation, as evidenced by the impossibility result of Caminada et al. regarding logic programming under the L-stable semantics [16]. Hence, by pursuing this line of research, one gains insight in what forms of non-monotonic reasoning can and cannot be represented by formal argumentation. Apart from this, a successful translation of a particular form of non-monotonic reasoning to formal argumentation makes it possible to apply argumentation techniques for explaining its entailment, for instance by using dialectical explanation techniques [12,18,25,30,43].

The remaining part of the current paper is structured as follows. First, in Section 2, we review some of the basic theory regarding logic programming and formal argumentation, including the existing translation (from [47]) from a logic program to an (instantiated) argumentation framework. We explain that whereas argumentation semantics are defined by minimizing and maximizing labels on the argument level, logic programming semantics are defined by minimizing and maximizing labels on the conclusion level. In Section 3, we present one of the main results of the current paper: the correspondence between the ideal model of a logic program and the ideal labelling of its associated argumentation framework. In Section 4, we perform a similar analysis regarding the eager model of a logic program and the eager labelling of is associated argumentation framework, and observe that here correspondence does not hold. In Section 5, we examine the correspondence between argumentation and logic programming (under ideal and eager semantics) when translating from an argumentation framework to its associated logic program. We round off with a discussion of the obtained results and an overview of the overall correspondences and non-correspondences between argumentation semantics and logic programming semantics in Section 6.

2.Formal preliminaries

We start with a brief overview of some basic concepts in formal argumentation. For current purposes, we restrict ourselves to finite argumentation frameworks.

For current purposes, we apply the labelling versions of argumentation semantics. As is explained in [10,13,14], these coincide with their respective extension-based variants.

Given an argument labelling ArgLab, we write val(ArgLab) to refer to the set of arguments labelled as val∈{in,out,undec} in ArgLab. For convenience, we may as well refer to ArgLab as the tuple (in(ArgLab),out(ArgLab),undec(ArgLab)).

Each argumentation framework has one or more complete labellings, a unique grounded labelling, one or more preferred labellings, zero or more stable labellings and one or more semi-stable labellings.22

We now shift our attention to logic programming. We start with formally introducing the notion of a logic program. For current purposes, we restrict ourselves to normal logic programs, which are logic programs without strong negation where the head of each rule consists of a single atom.

Given a logic programming rule x←y1,…,yn,notz1, …, notzm (or simply a rule, for short), we say that x is the head of the rule and y1,…,yn, notz1,…,notzm is the body of the rule. Moreover, we say that y1,…,yn is the strong part of the body and that notz1,…,notzm is the weak part of the body. Each expression notw, where w is an atom, is called a NAF literal. We say that a rule is NAF-free iff it does not contain any NAF literals (that is, iff m=0).

Concerning logic programs (or simply programs, for short), we assume the availability of three special atoms TRUE, FALSE and UNDEFINED, which can only occur in the strong part of the body of a rule. The Herbrand Base of a logic program P (written as HBP) is the set of all atoms in P (excluding the special atoms TRUE, FALSE and UNDEFINED). Finally, we say that a logic program is NAF-free iff each of its rules is NAF-free.

In the following, we recall the definitions of logic programming semantics as described in [16,17,35].

When P is a NAF-free logic program (possibly containing TRUE, FALSE or UNDEFINED), we write ΦAtms(P) for its unique minimal 3-valued model ⟨T,F⟩ (w.r.t. Atms), i.e. ⟨T,F⟩ has minimal T and maximal F (w.r.t. ⊆) among all 3-valued models of P w.r.t. Atms [35].

Since PMod is a NAF-free program, it has a unique minimal 3-valued model, written as ΦHBP(PMod).

We now recall various logic programming semantics which are based on 3-valued interpretations. The presentation below was originally provided in [16], where correspondences to other equivalent concepts for the same semantics were also discussed. It is heavily based on Przymusinski’s three-valued stable semantics [35] and tailored to ease the comparison to argumentation semantics.33

Each logic program has one or more 3-valued stable models, a unique well-founded model, one or more regular models, zero or more 2-valued stable models and one or more L-stable models.

Next, we recall how logic programming semantics can be expressed in terms of formal argumentation. For this, we first need to translate a logic program to an argumentation framework, for which we apply the approach of [16].

In essence, an argument can be seen as a tree-like structure of rules (the only difference with a real tree is that a rule can occur at more than one place in the argument). If A is an argument then Conc(A) is referred to as the conclusion of A, Rules(A) is referred to as the rules of A, Vul(A) is referred to as the vulnerabilities of A and Sub(A) is referred to as the subarguments of A.

The next step in constructing the argumentation framework is to determine the attack relation: an argument attacks another iff its conclusion is one of the vulnerabilities of the attacked argument.

Based on the thus constructed argumentation framework, we can apply argumentation semantics and, based on the resulting argument labelling(s) determine the associated conclusion labelling(s), using the approach of [16].

Conclusion labellings are very close to logic programming models. One of the differences is that logic programming models have two explicit values (indicated by membership of the sets T and F) whereas conclusion labellings have three values (the labels in, out and undec). Converting between conclusion labellings and logic programming models can be done using the two functions ConcLab2Mod and Mod2ConcLab [16,47]. The former function converts a conclusion labelling to a logic programming model and is defined as ConcLab2Mod(ConcLab)=(in(ConcLab),out(ConcLab)). The latter function converts a logic programming model to a conclusion labelling and is defined as Mod2ConcLab((T,F))=(T,F,HBP∖(T∪F)). As mentioned in [16], ConcLab2Mod and Mod2ConcLab are bijective functions that are each other’s inverse, making conclusion labellings and logic programming models one-to-one related.

It has been shown in [16,47] that complete conclusion labellings coincide with 3-valued stable models.

Now that we observed the correspondence between 3-valued stable models and complete conclusion labellings, we turn to the question of what are the conclusion labellings that correspond to well-founded, regular, 2-valued stable, L-stable, pre-ideal, ideal, pre-eager and eager models.

It is not difficult to see that the conclusion labellings of Definition 13 are one-to-one related to the logic programming models of Definition 8.44

From Thereom 1 and Theorem 2 it follows that each logic program has one or more complete conclusion labellings, a unique conc-grounded conclusion labelling, one or more conc-preferred conclusion labellings, zero or more conc-stable conclusion labellings and one or more conc-semi-stable conclusion labellings.55

The way of defining conclusion labellings as stated in Definition 13 is fundamentally different from what is done by most argumentation formalisms (e.g. ASPIC+ [31–33], ABA [9,20,44] and logic-based argumentation [8,26]. The following definition is meant to reflect the process by which these formalisms derive their conclusions.

Definition 13 and Definition 14 allow us to observe the fundamental difference between logic programming and (instantiated) argumentation. Logic programming, in essence, does the maximization and the minimization on the conclusion level. That is, it (conceptually) takes all complete argument labellings, converts these to conclusion labellings, and then selects the maximal/minimal among these. Instantiated argumentation, on the other hand, does the maximization and minimization on the argument level. That is, it (conceptually) takes all complete argument labellings, selects the maximal/minimal among these, and then converts these to conclusion labellings. So whereas logic programming does the maximization/minimization after converting argument labellings to conclusion labellings, instantiated argumentation does the maximization/minimization before converting argument labellings to conclusion labellings.66

In order to assess whether logic programming semantics coincide with argumentation semantics, one therefore has to assess whether maximizing (or minimizing) a particular label on the argument level has the same effect as maximizing (or minimizing) the label on the conclusion level. Several such correspondences have been observed in [16]. An overview is provided by Theorem 3.

These results imply that:

Please notice that conc-semi-stable conclusion labellings do not coincide with arg-semi-stable conclusion labellings. That is, minimizing undec on the conclusion level yields different results than minimizing undec on the argument level. A counter example (taken from [16]) is provided in Section 4. As a result of this, L-stable semantics for logic programming is not the same as semi-stable semantics for formal argumentation. We refer to [16] for details.

In general, proving that for a particular semantics sem the conc-sem conclusion labellings coincide with the arg-sem conclusion labellings is not a trivial affair. Moreover (as is for instance the case when sem is semi-stable) the correspondence can turn out not to hold.

3.The equivalence between logic programming and formal argumentation under ideal semantics

In the current paper, we ask ourselves whether the correspondence between logic programming and (instantiated) argumentation also holds under ideal semantics. That is, does the ideal model of a logic program P coincide with the associated conclusion labelling of the ideal argument labelling of AFP? Before we can answer to this question, we first need to define ideal semantics in the context of formal argumentation and logic programming.

Each argumentation framework has one or more pre-ideal argument labellings and a unique ideal argument labelling [15]. The pre-ideal argument labelling where in(ArgLab) is minimal (w.r.t. ⊆) among all pre-ideal argument labellings of AF is the grounded labelling. For the purposes of the current paper, what matters is the ideal argument labelling; the notion of a pre-ideal argument labelling merely serves as an auxiliary concept, to support the construction of some of the proofs. Our definition of the ideal argument labelling is based on [13,15] where it is observed that it coincides with the extension-based definition of ideal semantics of [25].

The example bellow should help the reader differentiate the relevant semantics.

Example 1

Example 1(Based on [25]).

The argumentation framework AF1=({A,B,C,D,E,F},{(A,B),(B,A),(B,B),(C,D),(C,E),(D,C),(D,E),(E,F)}) (Fig. 1) has the following six complete labellings:

ArgLab1=({A},{B},{C,D,E,F})ArgLab2=({A,C,F},{B,D,E},∅)ArgLab3=({A,D,F},{B,C,E},∅)ArgLab4=(∅,∅,{A,B,C,D,E,F})ArgLab5=({C,F},{D,E},{A,B})ArgLab6=({D,F},{C,E},{A,B})

Of these, only ArgLab2 and ArgLab3 are preferred. This means that only ArgLab1 and ArgLab4 are pre-ideal and that ArgLab1 is the ideal argument labelling of AF1. Notice also that here in(ArgLab1)⊊in(ArgLab2)∩in(ArgLab3) and that in(ArgLab1)⊋in(ArgLab4), where ArgLab4 is the grounded labelling of AF1.

Fig. 1.

Argumentation framework AF1.

Given the definition of the pre-ideal and ideal argument labellings, defining the associated arg-pre-ideal and arg-ideal conclusion labellings is straightforward.

The concept of ideal semantics for logic programming was originally introduced by Alferes et al. in terms of scenaria [2]. The approach of [2] has been reformulated (in an equivalent way) in terms of models in [17, Appendix B]. This reformulation is used for our current characterisation of ideal semantics for logic programming.

Each logic program has one or more pre-ideal models and a unique ideal model. The pre-ideal models correspond to the Saccà and Zaniolo’s deterministic models [38], so the above characterization of the ideal model for logic programs corresponds to the MD-stable model of [38]. Furthermore, the pre-ideal model where T is minimal corresponds to the well-founded model [38]. For the purposes of the current paper, what matters is the ideal model; the notion of a pre-ideal model merely serves as an auxiliary concept, to support the construction of some of the proofs.

The next concepts to be defined are those of a conc-pre-ideal conclusion labelling and that of the conc-ideal conclusion labelling.

It turns out that the conc-pre-ideal conclusion labellings (resp. the ideal conclusion labelling) and the pre-ideal models (resp. the ideal model) are one-to-one related.

From the fact that there exists one or more pre-ideal models and a unique ideal model, it follows from Theorem 4 that there exist one or more conc-pre-ideal conclusion labellings and a unique conc-ideal conclusion labelling.

The next step will be to show the equivalence between the conc-pre-ideal (resp. conc-ideal) conclusion labellings and the arg-pre-ideal (resp. arg-ideal) conclusion labellings. In order to do so, we need to state the following lemma from [16].

We are now ready to state and prove one of the main theorems of this paper.

We are now ready to formally state the correspondence between ideal semantics for formal argumentation and ideal semantics for logic programming.

4.The difference between logic programming and formal argumentation under eager semantics

The eager semantics for formal argumentation was first introduced in [11], where it was defined in terms of extensions. For current purposes, we apply the equivalent notion of eager semantics from [13,15], where it is defined in terms of argument labellings. Roughly, the idea is that instead of selecting the maximal complete labelling that is part of every preferred labelling (as is the case for ideal semantics) one selects the maximal complete labelling that is part of every semi-stable labelling.

Each argumentation framework has one or more pre-eager argument labellings and a unique eager argument labelling [13]. Every pre-ideal argument labelling is also a pre-eager argument labelling, but the opposite does not hold. Finally, the pre-eager argument labelling where in(ArgLab) is minimal (w.r.t. ⊆) among all pre-eager argument labellings of AF is the grounded labelling. For the purposes of the current paper, what matters is the eager argument labelling; the notion of a pre-eager argument labelling merely serves as an auxiliary concept to support the construction of some of the proofs.

Given an argumentation framework AF, its ideal argument labelling ArgLabid and its eager argument labelling ArgLabea, it can be observed that in(ArgLabid)⊆in(ArgLabea) (as well as out(ArgLabid)⊆out(ArgLabea)). For formal argumentation, eager semantics can therefore be seen as more credulous than ideal semantics.

The example below should help the reader differentiate eager from the other relevant semantics.

Fig. 2.

Argumentation framework AF2.

Given the definition of the pre-eager and eager argument labellings, defining the associated arg-pre-eager and arg-eager conclusion labellings is straightforward.

In the context of logic programming, a concept similar to eager semantics has, as far as we are aware, not been defined before. In the current paper, we define it in a similar way as ideal semantics for logic programming, with the difference that instead of being based on regular models (as for the ideal model) it is based on L-stable models.

Each logic program has one or more pre-eager models and a unique eager model. The pre-eager model where T is minimal corresponds to the well-founded model. For the purposes of the current paper, what matters is the eager model; the notion of a pre-eager model merely serves as an auxiliary concept.

Given a logic program P, its ideal model Modid=⟨Tid,Fid⟩ and its eager model Modea=⟨Tea,Fea⟩, it can be observed that Tid⊆Tea (as well as Fid⊆Fea). For logic programming, eager semantics can therefore be seen as more credulous than ideal semantics.

The next concepts to be defined are those of a conc-pre-eager conclusion labelling and that of the conc-eager conclusion labelling.

It turns out that the conc-pre-eager conclusion labellings (resp. the eager conclusion labelling) and the pre-eager models (resp. the eager model) are one-to-one related.

From the fact that there exists one or more pre-eager models and a unique eager model, it follows from Theorem 8 that there exist one or more conc-pre-eager conclusion labellings and a unique conc-eager conclusion labelling.

Although logic programming and formal argumentation coincide for ideal semantics, they do not coincide for eager semantics. A counter example is the following.99

Example 3.

Consider the following logic program P:

r1:a←notbr2:b←notar3:c←notc,notar4:d←notd,notbr5:c←notc,noter6:e←note

Each of these rules corresponds to an argument (A1 to A6). See Table 1 for details. The associated argumentation framework AFP is shown in Fig. 3.

Table 1

The arguments constructed from P

	A1	A2	A3	A4	A5	A6
Conclusion	a	b	c	d	c	e
Vulnerabilities	{b}	{a}	{c,a}	{d,b}	{c,e}	{e}

Fig. 3.

Argumentation framework AFP.

Given logic program P and argumentation framework AFP, three complete argument labellings with associated conclusion labellings and logic programming models can be distinguished. These are shown in Table 2.

Table 2

Labellings and models of P and AFP

Complete argument labellings	Complete conclusion labellings	3-valued stable models
ArgLab1:	ConcLab1:	Mod1:
({A1},{A2,A3},{A4,A5,A6})	({a},{b},{c,d,e})	⟨{a},{b}⟩
ArgLab2:	ConcLab2:	Mod2:
({A2},{A1,A4},{A3,A5,A6})	({b},{a,d},{c,e})	⟨{b},{a,d}⟩
ArgLab3:	ConcLab3:	Mod3:
(∅,∅,{A1,A2,A3,A4,A5,A6})	(∅,∅,{a,b,c,d,e})	⟨∅,∅⟩

From Table 2 it can be observed that only ArgLab1 and ArgLab2 are semi-stable argument labellings. This means that only ArgLab3 is a pre-eager argument labelling, and therefore ArgLab3 is the eager argument labelling. This means that ConcLab3 is the arg-eager conclusion labelling.

From Table 2 it can also be observed that only ConcLab2 is a conc-semi-stable conclusion labelling. Therefore, ConcLab2 and ConcLab3 are both conc-pre-eager conclusion labellings, which means that ConcLab2 is the conc-eager conclusion labelling.

In a similar way, it can be observed that only Mod2 is an L-stable model, Mod2 and Mod3 are pre-eager models, and (more importantly) that Mod2 is the eager model.

As such, we have observed that the eager model coincides with the conc-eager conclusion labelling.1010 However, these do not coincide with the arg-eager conclusion labelling. Hence, eager semantics for argumentation does not coincide with eager semantics for logic programming.

Although in general, eager semantics for logic programming does not coincide with eager semantics for formal argumentation (as shown by Example 3) there are classes of logic programs for which these semantics do coincide. This critically depends on the logic program having its arg-semi-stable conclusion labellings coincide with its conc-semi-stable conclusion labellings.

Example classes of logic programs that are semi-stable-compatible are AF-programs, stable programs and stratified programs [16]. We now proceed to prove that for each semi-stable-compatible program, its eager model coincides with the eager argument labelling of its associated logic program. For this, we first need the following intermediate result.

5.Translating argumentation frameworks to logic programs

So far, we have studied the connection between logic programming semantics and argumentation semantics using a translation from a logic program to an argumentation framework. It is also possible to go the other way around, using a translation from an argumentation framework to a logic program. For this, we use a definition from [16,47]. Basically, the idea is that a rule is created for each argument in the argumentation framework. The argument itself goes in the head of the rule and its attackers go in the body of the rule (as weakly negated statements).

As an example, the argumentation framework of Fig. 3 (page 109) has the following associated logic program:

We first observe that this logic program is not the same as logic program P of Example 3 that generated the argumentation framework of Fig. 3. This illustrates that in general, if one translates a logic program to an argumentation framework (using Definition 11) and then translates the resulting argumentation framework back to a logic program (using Definition 24), the logic program one ends up with is not necessarily the same as what one started with.

One could also examine what happens when starting not with a logic program, but with an argumentation framework. That is, what happens when one translates an argumentation framework to a logic program (using Definition 24) and then back to an argumentation framework (using Definition 11)? It turns out that the argumentation framework one ends up with is isomorphic with the argumentation framework one started with [16, Theorem 33].

To understand the nature of this isomorphism, we observe that when translating an argumentation framework AF to a logic program (Definition 11) each argument Ai will yield a corresponding rule ri with Ai as its head and the attackers of Ai as weakly negated statements in its body. When one uses the thus obtained logic program PAF to construct the associated argumentation framework AFPAF (Definition 24) each rule ri will form an argument of its own.

As an example, consider again the argumentation framework AF2 that was depicted in Fig. 2 (page 107) and was previously discussed in Example 2. This argumentation framework has the following associated logic program PAF2:

The logic program PAF2 has the associated argumentation framework AFPAF2 shown in Fig. 4 with:

Fig. 4.

Argumentation framework AFPAF2.

It is not difficult to see that AF2 and AFPAF2 are isomorphic. Moreover, we observe that the complete argument labellings of AF2 (which are (∅,∅,{A,B,C,D,E}), ({A},{B},{C,D,E}) and ({B,D},{A,C,E},∅)) correspond also to the complete conclusion labellings of AFPAF2.

Given two isomorphic argumentation frameworks, we can translate an argument labelling of one to an argument labelling of the other. This is formally defined as follows.

Definition 25 allows us to prove the following lemma.