Sage Journals: Discover world-class research

Abstract

The connection between logic programming and formal argumentation has been studied starting from the landmark 1995 paper of Dung. Subsequent work has identified a standard translation from logic programs to (instantiated) argumentation frameworks, under which pairwise correspondences hold between various logic programming semantics and various formal argumentation semantics. This includes the correspondence between 3-valued stable and complete semantics, between well-founded and grounded semantics and between 2-valued stable (LP) and stable (argumentation) semantics. In the current paper, we show that the existing translation is able to yield the additional correspondence between ideal semantics for logic programming and ideal semantics for formal argumentation. We also show that correspondence does not hold between eager semantics for logic programming and eager semantics for formal argumentation, at least when translating from logic programming to formal argumentation. Overall, the current work should be seen as completing the analysis of correspondences between mainstream admissibility-based argumentation semantics and their logic programming counterparts.

Keywords

Formal argumentation logic programming ideal semantics 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 $not p$ . 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.1

¹
The first two correspondences are also observed in [24], though in a different way.

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.

Definition 1 ([24]).

An argumentation framework is a pair $(Ar, att)$ where $Ar$ is a finite set of arguments and $att \subseteq Ar \times Ar$ .

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.

Definition 2.
Let $AF = (Ar, att)$ be an argumentation framework. An argument labelling is a function $ArgLab : Ar \to {in, out, undec}$ . An argument labelling is called a complete argument labelling iff for each $A \in Ar$ it holds that:
if $ArgLab (A) = in$ then for every $B \in Ar$ that attacks A it holds that $ArgLab (B) = out$

if $ArgLab (A) = out$ then there exists some $B \in Ar$ that attacks A such that $ArgLab (B) = in$

if $ArgLab (A) = undec$ then (i) not every $B \in Ar$ that attacks A has $ArgLab (B) = out$ and (ii) no $B \in Ar$ that attacks A has $ArgLab (B) = in$

Given an argument labelling $ArgLab$ , we write $val (ArgLab)$ to refer to the set of arguments labelled as $val \in {in, out, undec}$ in $ArgLab$ . For convenience, we may as well refer to $ArgLab$ as the tuple $(in (ArgLab), out (ArgLab), undec (ArgLab))$ .
Definition 3.
Let $ArgLab$ be an argument labelling of argumentation framework $AF = (Ar, att)$ . $ArgLab$ is called:
the grounded argument labelling iff $ArgLab$ is a complete argument labelling where $in (ArgLab)$ is minimal among all complete argument labellings of $AF$

a preferred argument labelling iff $ArgLab$ is a complete argument labelling where $in (ArgLab)$ is maximal among all complete argument labellings of $AF$

a stable argument labelling iff $ArgLab$ is a complete argument labelling where $undec (ArgLab) = \emptyset$

a semi-stable argument labelling iff $ArgLab$ is a complete argument labelling where $undec (ArgLab)$ is minimal among all complete argument labellings of $AF$

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.2 ²
This is because we only consider finite argumentation frameworks. An infinite argumentation framework can have zero or more semi-stable labellings [6,7,19,46].

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.
Definition 4.
A logic programming rule is an expression $x \leftarrow y_{1}, \dots, y_{n}, not z_{1}$ , …, $not z_{m}$ ( $n ⩾ 0$ , $m ⩾ 0$ ) where x, each $y_{i}$ ( $1 ⩽ i ⩽ n$ ) and each $z_{j}$ ( $1 ⩽ j ⩽ m$ ) is an atom, and $not$ represents negation as failure (NAF). A logic program P consists of a finite set of logic programming rules.

Given a logic programming rule $x \leftarrow y_{1}, \dots, y_{n}, not z_{1}$ , …, $not z_{m}$ (or simply a rule, for short), we say that x is the head of the rule and $y_{1}, \dots, y_{n}$ , $not z_{1}, \dots, not z_{m}$ is the body of the rule. Moreover, we say that $y_{1}, \dots, y_{n}$ is the strong part of the body and that $not z_{1}, \dots, not z_{m}$ is the weak part of the body. Each expression $not w$ , 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 ${HB}_{P}$ ) 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].
Definition 5.
A 3-valued interpretation of a logic program P with respect to a set of atoms $Atms \supseteq {HB}_{P}$ is a pair $⟨ T, F ⟩$ where $T, F \subseteq Atms$ and $T \cap F = \emptyset$ .
Definition 6.
A 3-valued interpretation $⟨ T, F ⟩$ of a NAF-free logic program P w.r.t. $Atms \supseteq {HB}_{P}$ is a 3-valued model of P w.r.t. $Atms$ if for all logic programming rules $x \leftarrow y_{1}, \dots, y_{n}$ in P it holds that
$x \in T$ or

$x \in F$ and $\exists i \in {1, \dots, n} : (y_{i} \in F \lor y_{i} = FALSE)$ or

$x \in Atms ∖ (T \cup F)$ and $\exists i \in {1, \dots, n} : (y_{i} \in F \lor y_{i} \in Atms ∖ (T \cup F) \lor y_{i} = FALSE \lor y_{i} = UNDEFINED)$

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].
Definition 7.
The reduct of a logic program P w.r.t. a 3-valued interpretation $Mod = ⟨ T, F ⟩$ , written as $P^{Mod}$ , is obtained by replacing in every rule each NAF literal $not x$ by $TRUE$ if $x \in F$ , by $FALSE$ if $x \in T$ , and by $UNDEFINED$ otherwise.

Since $P^{Mod}$ is a NAF-free program, it has a unique minimal 3-valued model, written as $Φ_{{HB}_{P}} (P^{Mod})$ .

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.3 ³
A similar characterization of these semantics (except well-founded) as special cases of the three-valued stable semantics (there called P-stable models) can also be found in [39].

Definition 8 ([16]).

Let P be a logic program and $Mod = ⟨ T, F ⟩$ be a 3-valued interpretation of P w.r.t. ${HB}_{P}$ . We say that $Mod$ is:

a 3-valued stable model iff $Φ_{{HB}_{P}} (P^{Mod}) = Mod$

the well-founded model iff $Mod$ is a 3-valued stable model where T is minimal (w.r.t. ⊆) among all 3-valued stable models of P

a regular model iff $Mod$ is a 3-valued stable model where T is maximal (w.r.t. ⊆) among all 3-valued stable models of P

a 2-valued stable model iff $Mod$ is a 3-valued stable model where $T \cup F = {HB}_{P}$

an L-stable model iff $Mod$ is a 3-valued stable model where $T \cup F$ is maximal (w.r.t. ⊆) among all 3-valued stable models of P

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].

Definition 9.
Let P be a logic program.
If $c \leftarrow not b_{1}, \dots, not b_{m}$ is a rule in P, then it is also an argument (say A) with

$Conc (A) = c$ ,

$Rules (A) = {c \leftarrow not b_{1}, \dots, not b_{m}}$ ,

$Vul (A) = {b_{1}, \dots, b_{m}}$ , and

$Sub (A) = {A}$ .

If $c \leftarrow a_{1}, \dots, a_{n}, not b_{1}, \dots, not b_{m}$ is a rule in P and for each $a_{i}$ ( $1 ⩽ i ⩽ n$ ) there exists an argument $A_{i}$ with $Conc (A_{i}) = a_{i}$ and such that $c \leftarrow a_{1}, \dots, a_{n}, not b_{1}, \dots, not b_{m}$ is not contained in $Rules (A_{i})$ , then $c \leftarrow (A_{1}), \dots, (A_{n}), not b_{1}, \dots, not b_{m}$ is an argument (say A) with

$Conc (A) = c$ ,

$Rules (A) = Rules (A_{1}) \cup \dots \cup Rules (A_{n}) \cup {c \leftarrow a_{1}, \dots, a_{n}, not b_{1}, \dots, not b_{m}}$

$Vul (A) = Vul (A_{1}) \cup \dots \cup Vul (A_{n}) \cup {b_{1}, \dots, b_{m}}$ , and

$Sub (A) = {A} \cup Sub (A_{1}) \cup \dots \cup Sub (A_{n})$ .

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.
Definition 10.
Let A and B be arguments in the sense of Definition 9. We say that A attacks B iff $Conc (A) \in Vul (B)$ .
Definition 11.
Let P be a logic program. We define its associated argumentation framework as ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ where ${Ar}_{P}$ is the set of arguments in the sense of Definition 9 and ${att}_{P}$ is the attack relation in the sense of Definition 10.

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].
Definition 12 ([16]).

Let P be a logic program. A conclusion labelling of P is a function $ConcLab : {HB}_{P} \to {in, out, undec}$ . Let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be the associated argumentation framework of P and $ArgLab$ be an argument labelling of ${AF}_{P}$ . We say that $ConcLab$ is the associated conclusion labelling of $ArgLab$ iff $ConcLab$ is a conclusion labelling such that for each $c \in {HB}_{P}$ it holds that $ConcLab (c) = max ({ArgLab (A) ∣ Conc (A) = c} \cup {out})$ where $in > undec > out$ . We say that a conclusion labelling is complete iff it is the associated conclusion labelling of a complete argument labelling. We define the function $ArgLab 2 ConcLab$ such that for any complete argument labelling $ArgLab$ , $ArgLab 2 ConcLab (ArgLab)$ is its associated conclusion labelling. We define $ConcLab 2 ArgLab$ as the inverse function of $ArgLab 2 ConcLab$ .

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 $ConcLab 2 Mod$ and $Mod 2 ConcLab$ [16,47]. The former function converts a conclusion labelling to a logic programming model and is defined as $ConcLab 2 Mod (ConcLab) = (in (ConcLab), out (ConcLab))$ . The latter function converts a logic programming model to a conclusion labelling and is defined as $Mod 2 ConcLab ((T, F)) = (T, F, {HB}_{P} ∖ (T \cup F))$ . As mentioned in [16], $ConcLab 2 Mod$ and $Mod 2 ConcLab$ 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.

Theorem 1 ([16,47]).

Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. It holds that:

if $Mod$ is a 3-valued stable model of P then $Mod 2 ConcLab (Mod)$ is a complete conclusion labelling of P

if $ConcLab$ is a complete conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a 3-valued stable model of P

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.

Definition 13.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:
the conc-grounded conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab)$ is minimal (w.r.t. ⊆) among all complete conclusion labellings of P

a conc-preferred conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all complete conclusion labellings of P

a conc-stable conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $undec (ConcLab) = \emptyset$

a conc-semi-stable conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $undec (ConcLab)$ is minimal (w.r.t. ⊆) among all complete conclusion labellings of P

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.4 ⁴
This has been observed informally in [16, Section 7.1]. However, for current purposes we would like to make this explicit in the form of a theorem with associated proof.

Theorem 2.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. It holds that:
if $Mod$ is the well-founded model of P then $Mod 2 ConcLab (Mod)$ is the conc-grounded conclusion labelling of P

if $ConcLab$ is the conc-grounded conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is the well-founded model of P

if $Mod$ is a regular model of P then $Mod 2 ConcLab (Mod)$ is a conc-preferred conclusion labelling of P

if $ConcLab$ is a conc-preferred conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a regular model of P

if $Mod$ is a 2-valued stable model of P then $Mod 2 ConcLab (Mod)$ is a conc-stable conclusion labelling of P

if $ConcLab$ is a conc-stable conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a 2-valued stable model of P

if $Mod$ is an L-stable model of P then $Mod 2 ConcLab (Mod)$ is a conc-semi-stable conclusion labelling of P

if $ConcLab$ is a conc-semi-stable conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is an L-stable model of P

Proof.

Let $Mod$ be the well-founded model of P. Therefore, using point 2 of Definition 8, $Mod$ is a 3-valued stable model where T is minimal among all 3-valued stable models of P. Let $ConcLab = Mod 2 ConcLab (Mod)$ . It was proved in Theorem 1 that the 3-valued stable models of P correspond to the complete conclusion labellings of P. Therefore, $ConcLab$ is a complete conclusion labelling of P, where $in (ConcLab)$ is minimal among all complete conclusion labellings of P. Therefore, using point 1 of Definition 13, it follows that $ConcLab$ is the conc-grounded conclusion labelling of P. That is, $Mod 2 ConcLab (Mod)$ is the conc-grounded conclusion labelling of P.

Let $ConcLab$ be the conc-grounded conclusion labelling of P. Therefore, using point 1 of Definition 13 $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab)$ is minimal among all complete conclusion labelling of P. Let $Mod = ConcLab 2 Mod (ConcLab)$ . By Theorem 1, $Mod$ is a 3-valued stable model where T is minimal among all 3-valued stable models of P. Therefore, using point 2 of Definition 8, it follows that $Mod$ is the well founded model of P. That is, $ConcLab 2 Mod (ConcLab)$ is the well founded model of P.
The proofs for the remaining parts of Theorem 2 are each analogous to one of the above. □

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.5 ⁵
Please notice that conc-grounded, conc-preferred, conc-stable and conc-semi-stable conclusion labellings were respectively called well-founded, regular, stable and L-stable conclusion labellings in [16].

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 14.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:
the arg-grounded conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is the grounded argument labelling of ${AF}_{P}$

an arg-preferred conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is a preferred argument labelling of ${AF}_{P}$

an arg-stable conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is a stable argument labelling of ${AF}_{P}$

an arg-semi-stable conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is a semi-stable argument labelling of ${AF}_{P}$

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.6 ⁶
It has to be mentioned that formalisms such as ASPIC+ [31–33], ABA [9,20,44] and logic-based argumentation [8,26] have been stated in terms of extensions instead of in terms of labellings. However, as extensions and labellings coincide [10,13,14] they could be viewed in terms of labellings as well.

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.
Theorem 3 ([16]).

Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. It holds that:

$ConcLab$ is the conc-grounded conclusion labelling iff $ConcLab$ is the arg-grounded conclusion labelling

$ConcLab$ is a conc-preferred conclusion labelling iff $ConcLab$ is an arg-preferred conclusion labelling

$ConcLab$ is a conc-stable conclusion labelling iff $ConcLab$ is an arg-stable conclusion labelling

These results imply that:

Well-founded semantics for logic programming coincides with grounded semantics for formal argumentation. That is:

if $Mod$ is the well-founded model of P then $Mod 2 ConcLab (Mod)$ is the arg-grounded conclusion labelling of P

if $ConcLab$ is the arg-grounded conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is the well-founded model of P

Regular semantics for logic programming coincides with preferred semantics for formal argumentation. That is:

if $Mod$ is a regular model of P then $Mod 2 ConcLab (Mod)$ is an arg-preferred conclusion labelling of P

if $ConcLab$ is an arg-preferred conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a regular model of P

2-valued stable semantics for logic programming coincides with stable semantics for formal argumentation. That is:

if $Mod$ is a 2-valued stable model of P then $Mod 2 ConcLab (Mod)$ is an arg-stable conclusion labelling of P

if $ConcLab$ is an arg-stable conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a 2-valued stable model of P

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 ${AF}_{P}$ ? Before we can answer to this question, we first need to define ideal semantics in the context of formal argumentation and logic programming.

Definition 15.
Let $ArgLab$ be an argument labelling of argumentation framework $AF = (Ar, att)$ . $ArgLab$ is called:
a pre-ideal argument labelling7 ⁷
A similar concept is also present in Dung et. al. [25] where the ideal extension is defined in terms of ideal sets. We opted for a slightly narrower concept based on the complete semantics (instead of the admissible semantics) for our convenience. This is merely a matter of choice, since the ideal extension of an argumentation framework is necessarily complete [25].
iff $ArgLab$ is a complete argument labelling where $in (ArgLab) \subseteq in ({ArgLab}_{pr})$ for each preferred argument labelling ${ArgLab}_{pr}$ of $AF$

the ideal argument labelling iff $ArgLab$ is a pre-ideal argument labelling where $in (ArgLab)$ is maximal (w.r.t. ⊆) among all pre-ideal argument labellings of $AF$

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 (Based on [25]).

The argumentation framework ${AF}_{1} = ({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: $\begin{array}{l} {ArgLab}_{1} = ({A}, {B}, {C, D, E, F}) \\ {ArgLab}_{2} = ({A, C, F}, {B, D, E}, \emptyset) \\ {ArgLab}_{3} = ({A, D, F}, {B, C, E}, \emptyset) \\ {ArgLab}_{4} = (\emptyset, \emptyset, {A, B, C, D, E, F}) \\ {ArgLab}_{5} = ({C, F}, {D, E}, {A, B}) \\ {ArgLab}_{6} = ({D, F}, {C, E}, {A, B}) \end{array}$ Of these, only ${ArgLab}_{2}$ and ${ArgLab}_{3}$ are preferred. This means that only ${ArgLab}_{1}$ and ${ArgLab}_{4}$ are pre-ideal and that ${ArgLab}_{1}$ is the ideal argument labelling of ${AF}_{1}$ . Notice also that here $in ({ArgLab}_{1}) ⊊ in ({ArgLab}_{2}) \cap in ({ArgLab}_{3})$ and that $in ({ArgLab}_{1}) ⊋ in ({ArgLab}_{4})$ , where ${ArgLab}_{4}$ is the grounded labelling of ${AF}_{1}$ .

Fig. 1.

Argumentation framework ${AF}_{1}$ .

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

Definition 16.

Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:

an arg-pre-ideal conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is a pre-ideal argument labelling of ${AF}_{P}$

the arg-ideal conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is the ideal argument labelling of ${AF}_{P}$

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.

Definition 17.

Let P be a logic program and $Mod = ⟨ T, F ⟩$ be a 3-valued interpretation of P w.r.t. ${HB}_{P}$ . We say that $Mod$ is:

a pre-ideal model iff $Mod$ is a 3-valued stable model where $T \subseteq T_{reg}$ for each regular model ${Mod}_{reg} = ⟨ T_{reg}, F_{reg} ⟩$ of P

the ideal model8 ⁸

In logic programming literature, this concept corresponds to Saccà and Zaniolo’s MD-stable (maximally-deterministic stable) model [38], which are defined in terms of their strongly-founded models. In their terminology, the unique MD-stable model of a logic program is the maximal strongly-founded model that is contained in every partial stable model (concerning only T). The correspondence of the MD-stable semantics for logic programs to the ideal semantics for abstract argumentation frameworks is straightforward because the strongly-founded models of [38] correspond to Przymusinski’s three-valued stable models and the partial stable models of [38] correspond to the regular models of a program [29].

iff

Mod

is a pre-ideal model where T is maximal (w.r.t. ⊆) among all pre-ideal models of P

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.

Definition 18.

Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:

a conc-pre-ideal conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab) \subseteq in ({ConcLab}_{cpref})$ for each conc-preferred conclusion labelling ${ConcLab}_{cpref}$ of P

the conc-ideal conclusion labelling iff $ConcLab$ is a conc-pre-ideal conclusion labelling of P where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-ideal conclusion labellings of P

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.

Theorem 4.

Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. It holds that:

if $Mod$ is a pre-ideal model of P then $Mod 2 ConcLab (Mod)$ is a conc-pre-ideal conclusion labelling of P

if $ConcLab$ is a conc-pre-ideal conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a pre-ideal model of P

if $Mod$ is the ideal model of P then $Mod 2 ConcLab (Mod)$ is the conc-ideal conclusion labelling of P

if $ConcLab$ is the conc-ideal conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is the ideal model of P

Proof.

Let $Mod$ be a pre-ideal model of P. Therefore, using point 1 of Definition 17, $Mod$ is a 3-valued stable model where $T \subseteq T_{reg}$ for each regular model of P. Let $ConcLab = Mod 2 ConcLab (Mod)$ . It has been proven in Theorem 2 that the regular models of P correspond to the conc-preferred conclusion labellings of P. This follows that $ConcLab$ is a complete conclusion labelling of P, where $in (ConcLab) \subseteq in ({ConcLab}_{cpref})$ for each conc-preferred conclusion labelling of P. Therefore, using point 1 of Definition 18, it follows that $ConcLab$ is the conc-pre-ideal conclusion labelling of P. That is, $Mod 2 ConcLab (Mod)$ is the conc-pre-ideal conclusion labelling of P.

Let $ConcLab$ be a conc-pre-ideal conclusion labelling of P. Therefore, using point 1 of Definition 18, $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab) \subseteq in ({ConcLab}_{cpref})$ for each conc-preferred conclusion labelling of P. Further, Let $Mod = ConcLab 2 Mod (ConcLab)$ . It has been proven in Theorem 2 that the regular models of P correspond to conc-preferred conclusion labellings of P. Therefore, $Mod$ is a 3-valued stable model where $T \subseteq T_{reg}$ for each regular model of P. Therefore, using point 1 of Definition 17, it follows that $Mod$ is the pre-ideal model of P. That is, $ConcLab 2 Mod (ConcLab)$ is the pre-ideal model of P.

Let $Mod$ be the ideal model of P. Therefore, using point 2 of Definition 17, $Mod$ is a pre-ideal model where T is maximal among all pre-ideal models of P. Let $ConcLab = Mod 2 ConcLab (Mod)$ . Using points 1 and 2 of this theorem, it has been proven that the pre-ideal models of P correspond to the conc-pre-ideal conclusion labellings of P. It follows that $ConcLab$ is a conc-pre-ideal conclusion labelling of P where $in (ConcLab)$ is maximal among all conc-pre-ideal conclusion labellings of P. Therefore, using point 2 of Definition 18, it follows that $ConcLab$ is the conc-ideal conclusion labelling of P. That is, $Mod 2 ConcLab (Mod)$ is the conc-ideal conclusion labelling of P.

Let $ConcLab$ be the conc-ideal conclusion labelling of P. Therefore, using point 2 of Definition 18, $ConcLab$ is a conc-pre-ideal conclusion labelling of P where $in (ConcLab)$ is maximal among all conc-pre-ideal conclusion labelling of P. Let $Mod = ConcLab 2 Mod (ConcLab)$ . Using points 1 and 2 of this Theorem, it has been proven that the pre-ideal model of P correspond to the conc-pre-ideal conclusion labelling of P. Therefore, $Mod$ is a pre-ideal model where T is maximal among all pre-ideal models of P. Therefore, using point 1 of Definition 17, it follows that $Mod$ is the ideal model of P. That is $ConcLab 2 Mod (ConcLab)$ is the ideal model of P.

□

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].

Lemma 5 ([16]).

Let P be a logic program and ${AF}_{P}$ be its associated argumentation framework. Let ${ArgLab}_{1}$ and ${ArgLab}_{2}$ be complete argument labellings of ${AF}_{P}$ . Let ${ConcLab}_{1} = ArgLab 2 ConcLab ({ArgLab}_{1})$ and ${ArgLab}_{2} = ArgLab 2 ConcLab ({ArgLab}_{2})$ . It holds that:

$in ({ArgLab}_{1}) \subseteq in ({ArgLab}_{2})$ iff $in ({ConcLab}_{1}) \subseteq in ({ConcLab}_{2})$

$in ({ArgLab}_{1}) = in ({ArgLab}_{2})$ iff $in ({ConcLab}_{1}) = in ({ConcLab}_{2})$

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

Theorem 6.
Let $ConcLab$ be a conclusion labelling of logic program P. It holds that:
$ConcLab$ is an arg-pre-ideal conclusion labelling of P iff $ConcLab$ is a conc-pre-ideal conclusion labelling of P

$ConcLab$ is the arg-ideal conclusion labelling of P iff $ConcLab$ is the conc-ideal conclusion labelling of P

Proof.

“⟹”:

Let $ConcLab$ be an arg-pre-ideal conclusion labelling of P. This means there exists a complete argument labelling $ArgLab$ , with $ConcLab = ArgLab 2 ConcLab (ArgLab)$ , such that $in (ArgLab) \subseteq in ({ArgLab}_{pref})$ for each preferred argument labelling ${ArgLab}_{pref}$ of ${AF}_{P}$ . From Lemma 5 (point 1) it follows that $in (ConcLab) \subseteq in ({ConcLab}_{argpref})$ for each arg-preferred conclusion labelling ${ConcLab}_{argpref}$ of P. As each arg-preferred conclusion labelling is also a conc-preferred conclusion labelling and vice versa (point 2 of Theorem 3) it then follows that $in (ConcLab) \subseteq in ({ConcLab}_{concpref})$ for each conc-preferred labelling ${ConcLab}_{concpref}$ of P. Hence, $ConcLab$ is a conc-pre-ideal conclusion labelling of P.

“⟸”:

Let $ConcLab$ be a conc-pre-ideal conclusion labelling of P. This means that $ConcLab$ is a complete conclusion labelling s.t. $in (ConcLab) \subseteq in ({ConcLab}_{concpref})$ for each conc-preferred conclusion labelling ${ConcLab}_{concpref}$ of P. As each conc-preferred conclusion labelling is also an arg-preferred conclusion labelling and vice versa (point 2 of Theorem 3), it follows that $in (ConcLab) \subseteq in ({ConcLab}_{argpref})$ for each arg-preferred conclusion labelling ${ConcLab}_{argpref}$ of P. Let $ArgLab$ be such that $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . From Lemma 5 (point 1), it follows that $in (ArgLab) \subseteq in ({ArgLab}_{pref})$ for each preferred argument labelling of ${AF}_{P}$ . This means that $ArgLab$ is a pre-ideal argument labelling of ${AF}_{P}$ . Hence, ConcLab is an arg-pre-ideal conclusion labelling of P.

“⟹”:

Let $ConcLab$ be the arg-ideal conclusion labelling of P. This means that there is an argument labelling $ArgLab$ with $ConcLab = ArgLab 2 ConcLab (ArgLab)$ such that $ArgLab$ is the ideal argument labelling of ${AF}_{P}$ . That is, $ArgLab$ is a pre-ideal argument labelling of ${AF}_{P}$ of which $in (ArgLab)$ is maximal among all pre-ideal argument labellings of ${AF}_{P}$ . So for each pre-ideal argument labelling ${ArgLab}_{preideal}$ of ${AF}_{P}$ , it holds that if $in ({ArgLab}_{preideal}) \supseteq in (ArgLab)$ then ${ArgLab}_{preideal} = ArgLab$ . From Lemma 5 it follows that for each arg-pre-ideal conclusion labelling ${ConcLab}_{argpreideal}$ of P it holds that if $in ({ConcLab}_{argpreideal}) \supseteq in (ConcLab)$ then ${ConcLab}_{argpreideal} = ConcLab$ . As each arg-pre-ideal conclusion labelling is also a conc-pre-ideal conclusion labelling and vice versa (point (1) of the current theorem) it follows that $ConcLab$ is a conc-pre-ideal conclusion labelling (as $ConcLab$ is an arg-pre-ideal labelling, since $ArgLab$ is a pre-ideal labelling) such that for each conc-pre-ideal labelling ${ConcLab}_{concpreideal}$ it holds that if $in ({ConcLab}_{concpreideal}) \supseteq in (ConcLab)$ then ${ConcLab}_{concpreideal} = ConcLab$ . That is, $ConcLab$ is a conc-pre-ideal conclusion labelling where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-ideal conclusion labellings. Hence, $ConcLab$ is the conc-ideal conclusion labelling of P.

“⟸”:

Let $ConcLab$ be the conc-ideal conclusion labelling of P. This means that $ConcLab$ is a conc-pre-ideal conclusion labelling where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-ideal conclusion labellings. That is, $ConcLab$ is a conc-pre-ideal conclusion labelling such that for each conc-pre-ideal conclusion labelling ${ConcLab}_{concpreideal}$ it holds that if $in ({ConcLab}_{concpreideal}) \supseteq in (ConcLab)$ then ${ConcLab}_{concpreideal} = ConcLab$ . From point (1) of the current theorem, it follows that $ConcLab$ is an arg-pre-ideal conclusion labelling such that for each arg-pre-ideal conclusion labelling ${ConcLab}_{argpreideal}$ it holds that if $in ({ConcLab}_{argpreideal}) \supseteq in (ConcLab)$ then ${ConcLab}_{argpreideal} = ConcLab$ . Let $ArgLab$ be such that $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . From Lemma 5 it follows that for each pre-ideal argument labelling ${ArgLab}_{preideal}$ it holds that if $in ({ArgLab}_{preideal}) \supseteq in (ArgLab)$ then ${ArgLab}_{preideal} = ArgLab$ . That is, $ArgLab$ is a pre-ideal argument labelling where $in (ArgLab)$ is maximal among all pre-ideal argument labellings. That is, $ArgLab$ is the ideal argument labelling. Hence, $ConcLab$ is the arg-ideal conclusion labelling of P.
□

We are now ready to formally state the correspondence between ideal semantics for formal argumentation and ideal semantics for logic programming. Theorem 7.
Let $Mod$ be the ideal model of logic program P and $ArgLab$ be the ideal argument labelling of ${AF}_{P}$ . It holds that
$Mod = ConcLab 2 Mod (ArgLab 2 ConcLab (ArgLab))$

$ArgLab = ConcLab 2 ArgLab (Mod 2 ConcLab (Mod))$

Proof.

Let $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . It then holds (Definition 16) that $ConcLab$ is the arg-ideal conclusion labelling. From point (2) of Theorem 6 it follows that $ConcLab$ is also the conc-ideal conclusion labelling. From point (4) of Theorem 4 it follows that $ConcLab 2 Mod (ConcLab)$ is the ideal model of P. As P has a unique ideal model, $Mod = ConcLab 2 Mod (ConcLab)$ . That is, $Mod = ConcLab 2 Mod (ArgLab 2 ConcLab (ArgLab))$ .

Let $ConcLab = Mod 2 ConcLab (Mod)$ . From point (3) of Theorem 4 it follows that $ConcLab$ is the conc-ideal conclusion labelling of P. Hence, by Definition 12 and point (2) of Definition 16, $ConcLab 2 ArgLab (ConcLab)$ is the ideal argument labelling of ${AF}_{P}$ . As the ideal argument labelling is unique, it follows that $ArgLab = ConcLab 2 ArgLab (ConcLab)$ . That is, $ArgLab = ConcLab 2 ArgLab (Mod 2 ConcLab (Mod))$ .
□

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.

Definition 19.
Let $ArgLab$ be an argument labelling of argumentation framework $AF = (Ar, att)$ . $ArgLab$ is called:
a pre-eager argument labelling iff $ArgLab$ is a complete argument labelling where $in (ArgLab) \subseteq in ({ArgLab}_{sem})$ for each semi-stable argument labelling ${ArgLab}_{sem}$ of $AF$

the eager argument labelling iff $ArgLab$ is a pre-eager argument labelling where $in (ArgLab)$ is maximal (w.r.t. ⊆) among all pre-eager argument labellings of $AF$

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 ${ArgLab}_{id}$ and its eager argument labelling ${ArgLab}_{ea}$ , it can be observed that $in ({ArgLab}_{id}) \subseteq in ({ArgLab}_{ea})$ (as well as $out ({ArgLab}_{id}) \subseteq out ({ArgLab}_{ea})$ ). 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.
Example 2.
The argumentation framework ${AF}_{2} = ({A, B, C, D, E}, {(A, B), (B, A), (B, C), (C, D), (D, E), (E, C)})$ (depicted in Fig. 2) has the following three complete labellings: $\begin{array}{l} {ArgLab}_{1} = (\emptyset, \emptyset, {A, B, C, D, E}) \\ {ArgLab}_{2} = ({A}, {B}, {C, D, E}) \\ {ArgLab}_{3} = ({B, D}, {A, C, E}, \emptyset) \end{array}$ Of these, ${ArgLab}_{1}$ is the grounded labelling, while ${ArgLab}_{2}$ and ${ArgLab}_{3}$ are both preferred, and only ${ArgLab}_{3}$ is semi-stable. It follows that only ${ArgLab}_{1}$ is pre-ideal, while both ${ArgLab}_{1}$ and ${ArgLab}_{3}$ are pre-eager. Therefore, ${ArgLab}_{1}$ is the ideal argument labelling of ${AF}_{2}$ and ${ArgLab}_{3}$ is the eager argument labelling of ${AF}_{2}$ .

Fig. 2.
Argumentation framework ${AF}_{2}$ .

Given the definition of the pre-eager and eager argument labellings, defining the associated arg-pre-eager and arg-eager conclusion labellings is straightforward.
Definition 20.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:
an arg-pre-eager conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is a pre-eager argument labelling of ${AF}_{P}$

the arg-eager conclusion labelling iff $ConcLab = ArgLab 2 ConcLab (ArgLab)$ where $ArgLab$ is the eager argument labelling of ${AF}_{P}$

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.
Definition 21.
Let P be a logic program and $Mod = ⟨ T, F ⟩$ be a 3-valued interpretation of P w.r.t. ${HB}_{P}$ . We say that $Mod$ is:
a pre-eager model iff $Mod$ is a 3-valued stable model where $T \subseteq T_{lstab}$ for each L-stable model ${Mod}_{lstab} = ⟨ T_{lstab}, F_{lstab} ⟩$ of P

the eager model iff $Mod$ is a pre-eager model where T is maximal (w.r.t. ⊆) among all pre-eager models of P

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 ${Mod}_{id} = ⟨ T_{id}, F_{id} ⟩$ and its eager model ${Mod}_{ea} = ⟨ T_{ea}, F_{ea} ⟩$ , it can be observed that $T_{id} \subseteq T_{ea}$ (as well as $F_{id} \subseteq F_{ea}$ ). 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.
Definition 22.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. Let $ConcLab$ be a conclusion labelling of P. $ConcLab$ is called:
a conc-pre-eager conclusion labelling iff $ConcLab$ is a complete conclusion labelling of P where $in (ConcLab) \subseteq in ({ConcLab}_{csem})$ for each conc-semi-stable conclusion labelling ${ConcLab}_{csem}$ of P

the conc-eager conclusion labelling iff $ConcLab$ is a conc-pre-eager conclusion labelling of P where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-eager conclusion labellings of P

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.
Theorem 8.
Let P be a logic program and let ${AF}_{P} = ({Ar}_{P}, {att}_{P})$ be its associated argumentation framework. It holds that:
if $Mod$ is a pre-eager model of P then $Mod 2 ConcLab (Mod)$ is a conc-pre-eager conclusion labelling of P

if $ConcLab$ is a conc-pre-eager conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is a pre-eager model of P

if $Mod$ is the eager model of P then $Mod 2 ConcLab (Mod)$ is the conc-eager conclusion labelling of P

if $ConcLab$ is the conc-eager conclusion labelling of P then $ConcLab 2 Mod (ConcLab)$ is the eager model of P

Proof.
The proof is analogous to that of Theorem 4. □

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.9 ⁹
This counter example is taken from [16] where it was used in the context of semi-stable and L-stable semantics. The example has been slightly adapted to increase readability.

Example 3.
Consider the following logic program P: $\begin{matrix} \begin{matrix} r_{1} : & a & \leftarrow & not b \\ r_{2} : & b & \leftarrow & not a \\ r_{3} : & c & \leftarrow & not c, not a \end{matrix} & \begin{matrix} r_{4} : & d & \leftarrow & not d, not b \\ r_{5} : & c & \leftarrow & not c, not e \\ r_{6} : & e & \leftarrow & not e \end{matrix} \end{matrix}$

Each of these rules corresponds to an argument ( $A_{1}$ to $A_{6}$ ). See Table 1 for details. The associated argumentation framework ${AF}_{P}$ is shown in Fig. 3.

Table 1
The arguments constructed from P

$A_{1}$ $A_{2}$ $A_{3}$ $A_{4}$ $A_{5}$ $A_{6}$

Conclusion a b c d c e

Vulnerabilities ${b}$ ${a}$ ${c, a}$ ${d, b}$ ${c, e}$ ${e}$

Fig. 3.
Argumentation framework ${AF}_{P}$ .

Given logic program P and argumentation framework ${AF}_{P}$ , 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 ${AF}_{P}$

Complete argument labellings Complete conclusion labellings 3-valued stable models

${ArgLab}_{1}$ : ${ConcLab}_{1}$ : ${Mod}_{1}$ :

$({A_{1}}, {A_{2}, A_{3}}, {A_{4}, A_{5}, A_{6}})$ $({a}, {b}, {c, d, e})$ $⟨ {a}, {b} ⟩$

${ArgLab}_{2}$ : ${ConcLab}_{2}$ : ${Mod}_{2}$ :

$({A_{2}}, {A_{1}, A_{4}}, {A_{3}, A_{5}, A_{6}})$ $({b}, {a, d}, {c, e})$ $⟨ {b}, {a, d} ⟩$

${ArgLab}_{3}$ : ${ConcLab}_{3}$ : ${Mod}_{3}$ :

$(\emptyset, \emptyset, {A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}})$ $(\emptyset, \emptyset, {a, b, c, d, e})$ $⟨ \emptyset, \emptyset ⟩$

From Table 2 it can be observed that only ${ArgLab}_{1}$ and ${ArgLab}_{2}$ are semi-stable argument labellings. This means that only ${ArgLab}_{3}$ is a pre-eager argument labelling, and therefore ${ArgLab}_{3}$ is the eager argument labelling. This means that ${ConcLab}_{3}$ is the arg-eager conclusion labelling.

From Table 2 it can also be observed that only ${ConcLab}_{2}$ is a conc-semi-stable conclusion labelling. Therefore, ${ConcLab}_{2}$ and ${ConcLab}_{3}$ are both conc-pre-eager conclusion labellings, which means that ${ConcLab}_{2}$ is the conc-eager conclusion labelling.

In a similar way, it can be observed that only ${Mod}_{2}$ is an L-stable model, ${Mod}_{2}$ and ${Mod}_{3}$ are pre-eager models, and (more importantly) that ${Mod}_{2}$ is the eager model.

As such, we have observed that the eager model coincides with the conc-eager conclusion labelling.10 ¹⁰
This should not come as a surprise, as it follows from Theorem 2.
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.
Definition 23 ([16]11 ¹¹
These programs are called semi-stable-L-stable compatible in [16]. We opted to slightly change the terminology in order for it to become more in line with the rest of the current paper.
).

	$A_{1}$	$A_{2}$	$A_{3}$	$A_{4}$	$A_{5}$	$A_{6}$
Conclusion	a	b	c	d	c	e
Vulnerabilities	${b}$	${a}$	${c, a}$	${d, b}$	${c, e}$	${e}$

Complete argument labellings	Complete conclusion labellings	3-valued stable models
${ArgLab}_{1}$ :	${ConcLab}_{1}$ :	${Mod}_{1}$ :
$({A_{1}}, {A_{2}, A_{3}}, {A_{4}, A_{5}, A_{6}})$	$({a}, {b}, {c, d, e})$	$⟨ {a}, {b} ⟩$
${ArgLab}_{2}$ :	${ConcLab}_{2}$ :	${Mod}_{2}$ :
$({A_{2}}, {A_{1}, A_{4}}, {A_{3}, A_{5}, A_{6}})$	$({b}, {a, d}, {c, e})$	$⟨ {b}, {a, d} ⟩$
${ArgLab}_{3}$ :	${ConcLab}_{3}$ :	${Mod}_{3}$ :
$(\emptyset, \emptyset, {A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6}})$	$(\emptyset, \emptyset, {a, b, c, d, e})$	$⟨ \emptyset, \emptyset ⟩$

A logic program is called semi-stable-compatible iff:

each arg-semi-stable conclusion labelling is a conc-semi-stable conclusion labelling

each conc-semi-stable conclusion labelling is an arg-semi-stable conclusion labelling

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.

Theorem 9.
Let $ConcLab$ be a conclusion labelling of a semi-stable-compatible logic program P. It holds that:
$ConcLab$ is an arg-pre-eager conclusion labelling iff $ConcLab$ is a conc-pre-eager conclusion labelling

$ConcLab$ is the arg-eager conclusion labelling iff $ConcLab$ is the conc-eager conclusion labelling

Proof.

“⟹”:

Let ConcLab be an arg-pre-eager conclusion labelling of P. This means there exists a complete argument labelling $ArgLab$ , with $ConcLab = ArgLab 2 ConcLab (ArgLab)$ , such that $in (ArgLab) \subseteq in ({ArgLab}_{sem})$ for each semi-stable argument labelling ${ArgLab}_{sem}$ of ${AF}_{P}$ . From Lemma 5 (point 1) it follows that $in (ConcLab) \subseteq in ({ConcLab}_{argsem})$ for each arg-semi-stable conclusion labelling ${ConcLab}_{argsem}$ of P. The fact that P is a semi-stable-compatible logic program means that each arg-semi-stable conclusion labelling is also a conc-semi-stable conclusion labelling and vice versa (Definition 23). We therefore obtain that $in (ConcLab) \subseteq in ({ConcLab}_{concsem})$ for each conc-semi-stable labelling ${ConcLab}_{concsem}$ of P. Hence, $ConcLab$ is a conc-pre-eager conclusion labelling of P.

“⟸”:

Let $ConcLab$ be a conc-pre-eager conclusion labelling of P. This means that $ConcLab$ is a complete conclusion labelling s.t. $in (ConcLab) \subseteq in ({ConcLab}_{concsem})$ for each conc-semi-stable conclusion labelling ${ConcLab}_{concsem}$ of P. The fact that P is a semi-stable-compatible logic program means that each conc-semi-stable conclusion labelling is also an arg-semi-stable conclusion labelling and vice versa (Definition 23). We therefore obtain that $in (ConcLab) \subseteq in ({ConcLab}_{argsem})$ for each arg-semi-stable conclusion labelling ${ConcLab}_{argsem}$ of P. Let $ArgLab$ be such that $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . From Lemma 5 (point 1) it follows that $in (ArgLab) \subseteq in ({ArgLab}_{sem})$ for each semi-stable argument labelling of ${AF}_{P}$ . This means that $ArgLab$ is a pre-eager argument labelling of ${AF}_{P}$ . Hence, ConcLab is an arg-pre-eager conclusion labelling of P.

“⟹”:

Let $ConcLab$ be the arg-eager conclusion labelling of P. This means that there is an argument labelling $ArgLab$ with $ConcLab = ArgLab 2 ConcLab (ArgLab)$ such that $ArgLab$ is the eager argument labelling of ${AF}_{P}$ . That is, $ArgLab$ is a pre-eager argument labelling of ${AF}_{P}$ of which $in (ArgLab)$ is maximal among all pre-eager argument labellings of ${AF}_{P}$ . So for each pre-eager argument labelling ${ArgLab}_{preeager}$ it holds that if $in ({ArgLab}_{preeager}) \supseteq in (ArgLab)$ then ${ArgLab}_{preeager} = ArgLab$ . From Lemma 5 it follows that for each arg-pre-eager conclusion labelling ${ConcLab}_{argpreeager}$ it holds that if $in ({ConcLab}_{argpreeager}) \supseteq in (ConcLab)$ then ${ConcLab}_{argpreeager} = ConcLab$ . As each arg-pre-eager conclusion labelling of P is also a conc-pre-eager conclusion labelling of P and vice versa (point (1) of the current theorem) it follows that $ConcLab$ is a conc-pre-eager conclusion labelling (as $ConcLab$ is an arg-pre-eager labelling, since $ArgLab$ is a pre-eager labelling) such that for each conc-pre-eager labelling ${ConcLab}_{concpreeager}$ it holds that if $in ({ConcLab}_{concpreeager}) \supseteq in (ConcLab)$ then ${ConcLab}_{concpreeager} = ConcLab$ . That is, $ConcLab$ is a conc-pre-eager conclusion labelling where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-eager conclusion labellings. Hence, $ConcLab$ is the conc-eager conclusion labelling.

“⟸”:

Let $ConcLab$ be the conc-eager conclusion labelling of P. This means that $ConcLab$ is a conc-pre-eager conclusion labelling where $in (ConcLab)$ is maximal (w.r.t. ⊆) among all conc-pre-eager conclusion labellings. That is, $ConcLab$ is a conc-pre-eager conclusion labelling such that for each conc-pre-eager conclusion labelling ${ConcLab}_{concpreeager}$ it holds that if $in ({ConcLab}_{concpreeager}) \supseteq in (ConcLab)$ then ${ConcLab}_{concpreeager} = ConcLab$ . From point (1) of the current theorem, it follows that $ConcLab$ is an arg-pre-eager conclusion labelling such that for each arg-pre-eager conclusion labelling ${ConcLab}_{argpreeager}$ it holds that if $in ({ConcLab}_{argpreeager}) \supseteq in (ConcLab)$ then ${ConcLab}_{argpreeager} = ConcLab$ . Let $ArgLab$ be such that $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . From Lemma 5 it follows that for each pre-eager argument labelling ${ArgLab}_{preeager}$ it holds that if $in ({ArgLab}_{preeager}) \supseteq in (ArgLab)$ then ${ArgLab}_{preeager} = ArgLab$ . That is, $ArgLab$ is a pre-eager argument labelling where $in (ArgLab)$ is maximal among all pre-eager argument labellings. That is, $ArgLab$ is the eager argument labelling. Hence, $ConcLab$ is the arg-eager conclusion labelling.
□
Theorem 10.
Let P be a semi-stable-compatible logic program, let $Mod$ be the eager model of P and let $ArgLab$ be the eager argument labelling of ${AF}_{P}$ . It holds that
$Mod = ConcLab 2 Mod (ArgLab 2 ConcLab (ArgLab))$

$ArgLab = ConcLab 2 ArgLab (Mod 2 ConcLab (Mod))$

Proof.

Let $ConcLab = ArgLab 2 ConcLab (ArgLab)$ . It then holds (Definition 20) that $ConcLab$ is the arg-eager conclusion labelling. From point (2) of Theorem 9 it follows that $ConcLab$ is also the conc-eager conclusion labelling. From point (4) of Theorem 8 it follows that $ConcLab 2 Mod (ConcLab)$ is the eager model of P. Since P has a unique eager model, $Mod = ConcLab 2 Mod (ConcLab)$ . That is, $Mod = ConcLab 2 Mod (ArgLab 2 ConcLab (ArgLab))$ .

Let $ConcLab = Mod 2 ConcLab (Mod)$ . From point (3) of Theorem 8 it follows that $ConcLab$ is the conc-eager conclusion labelling of P. Hence, by Definition 12 and point (2) of Definition 20, $ConcLab 2 ArgLab (ConcLab)$ is the eager argument labelling of ${AF}_{P}$ . As the eager argument labelling is unique, it follows that $ArgLab = ConcLab 2 ArgLab (ConcLab)$ . That is, $ArgLab = ConcLab 2 ArgLab (Mod 2 ConcLab (Mod))$ .
□
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).

Definition 24.
Let $AF = (Ar, att)$ be an argumentation framework. Then the logic program associated with $AF$ is $P_{AF} = {A \leftarrow not B_{1}, \dots, not B_{m} ∣ {B_{i} ∣ (B_{i}, A) \in att} = {B_{1}, \dots, B_{m}}}$ .

As an example, the argumentation framework of Fig. 3 (page 109) has the following associated logic program: $\begin{matrix} A_{1} \leftarrow not A_{2} & A_{4} \leftarrow not A_{2}, not A_{4} \\ A_{2} \leftarrow not A_{1} & A_{5} \leftarrow not A_{3}, not A_{5}, not A_{6} \\ A_{3} \leftarrow not A_{1}, not A_{3}, not A_{5} & A_{6} \leftarrow not A_{6} \end{matrix}$

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 $A_{i}$ will yield a corresponding rule $r_{i}$ with $A_{i}$ as its head and the attackers of $A_{i}$ as weakly negated statements in its body. When one uses the thus obtained logic program $P_{AF}$ to construct the associated argumentation framework ${AF}_{P_{AF}}$ (Definition 24) each rule $r_{i}$ will form an argument of its own.

As an example, consider again the argumentation framework ${AF}_{2}$ that was depicted in Fig. 2 (page 107) and was previously discussed in Example 2. This argumentation framework has the following associated logic program $P_{{AF}_{2}}$ : $\begin{matrix} \begin{matrix} A \leftarrow not B \\ B \leftarrow not A \\ C \leftarrow not B, not E \end{matrix} & \begin{matrix} D \leftarrow not C \\ E \leftarrow not D \end{matrix} \end{matrix}$

The logic program $P_{{AF}_{2}}$ has the associated argumentation framework ${AF}_{P_{{AF}_{2}}}$ shown in Fig. 4 with: $\begin{matrix} \begin{matrix} A^{'} & = & “ A \leftarrow not B^{″} \\ B^{'} & = & “ B \leftarrow not A^{″} \\ C^{'} & = & “ C \leftarrow not B, not E^{″} \end{matrix} & \begin{matrix} D^{'} & = & “ D \leftarrow not C^{″} \\ E^{'} & = & “ E \leftarrow not D^{″} \end{matrix} \end{matrix}$

Fig. 4.
Argumentation framework ${AF}_{P_{{AF}_{2}}}$ .

It is not difficult to see that ${AF}_{2}$ and ${AF}_{P_{{AF}_{2}}}$ are isomorphic. Moreover, we observe that the complete argument labellings of ${AF}_{2}$ (which are $(\emptyset, \emptyset, {A, B, C, D, E})$ , $({A}, {B}, {C, D, E})$ and $({B, D}, {A, C, E}, \emptyset)$ ) correspond also to the complete conclusion labellings of ${AF}_{P_{{AF}_{2}}}$ .

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.
Let $AF = (Ar, att)$ and ${AF}^{'} = ({Ar}^{'}, {att}^{'})$ be isomorphic argumentation frameworks and let I be the function that defines this isomorphism. That is, $I : Ar \to {Ar}^{'}$ is a function such that $(A, B) \in att$ iff $(I (A), I (B)) \in {att}^{'}$ . Let $ArgLab$ be an argument labelling of $AF$ . We define the associated argument labelling ${ArgLab}^{'}$ of ${AF}^{'}$ as $({I (A) ∣ ArgLab (A) = in}, ({I (A) ∣ ArgLab (A) = out}, ({I (A) ∣ ArgLab (A) = undec})$ .

Definition 25 allows us to prove the following lemma.
Lemma 11.
Let $AF = (Ar, att)$ be an argumentation framework and let $P_{AF}$ be its associated logic program (Definition 24 ). Let $ArgLab$ be the ideal argument labelling of $AF$ and let $ConcLab$ be the arg-ideal conclusion labelling of $P_{AF}$ . It holds that $ArgLab = ConcLab$ .
Proof.
Let ${AF}_{P_{AF}}$ be the argumentation framework associated with $P_{AF}$ . It holds that $AF$ and ${AF}_{P_{AF}}$ are isomorphic [16, Theorem 33]. Let ${ArgLab}^{'}$ be argument labelling of ${AF}_{P_{AF}}$ that is associated with $ArgLab$ under the isomorphism (Definition 25). As ideal semantics is language independent [4,5] it follows that ${ArgLab}^{'}$ is the ideal argument labelling of ${AF}_{P_{AF}}$ . It then follows that $ConcLab = ArgLab 2 ConcLab ({ArgLab}^{'})$ . In order to prove that $ArgLab = ConcLab$ we need to show the following:
$in (ArgLab) \subseteq in (ConcLab)$

Let $A \in in (ArgLab)$ . Then “ $A \leftarrow not B_{1}, \dots, not B_{m}$ ” $\in in ({ArgLab}^{'})$ .

Therefore, $A \in in (ConcLab)$ .

$out (ArgLab) \subseteq out (ConcLab)$

Let $A \in out (ArgLab)$ . Then “ $A \leftarrow not B_{1}, \dots, not B_{m}$ ” $\in out ({ArgLab}^{'})$ .

Therefore, $A \in out (ConcLab)$ .

$undec (ArgLab) \subseteq undec (ConcLab)$

Let $A \in undec (ArgLab)$ . Then “ $A \leftarrow not B_{1}, \dots, not B_{m}$ ” $\in undec ({ArgLab}^{'})$ .

Therefore, $A \in undec (ConcLab)$ .
□
Theorem 12.
Let $AF = (Ar, att)$ be an argumentation framework and let $P_{AF}$ be its associated logic program (in line with Definition 24 ). Let $ArgLab$ be the ideal argument labelling of $AF$ and let $Mod = ⟨ T, F ⟩$ be the ideal model of P. It holds that:
$Mod = ConcLab 2 Mod (ArgLab)$

$ArgLab = Mod 2 ConcLab (Mod)$

Proof.

As $ArgLab$ is the ideal argument labelling of $AF$ , it follows from Lemma 11 that $ArgLab$ is also the arg-ideal conclusion labelling of $P_{AF}$ . From point (2) of Theorem 6 it follows that $ArgLab$ is also a conc-ideal conclusion labelling of $P_{AF}$ . From Theorem 4 (point 4) it follows that $ConcLab 2 Mod (ArgLab)$ is the ideal model of $P_{AF}$ . That is, $ConcLab 2 Mod (ArgLab) = Mod$ .

As $Mod$ is the ideal model of $P_{AF}$ it follows that $Mod 2 ConcLab (Mod)$ is the conc-ideal conclusion labelling of $P_{AF}$ (Theorem 4, point 3). From Theorem 6 (point 2) it follows that $Mod 2 ConcLab (Mod)$ is also the arg-ideal conclusion labelling of $P_{AF}$ . From Lemma 11 it then follows that $Mod 2 ConcLab (Mod)$ is also the ideal argument labelling of $AF$ . That is, $Mod 2 ConcLab (Mod) = ArgLab$ .
□

The proof of Theorem 12 can be generalised for any argumentation semantics $σ_{arg}$ and associated logic programming semantics $σ_{lp}$ . As long as the $σ_{lp}$ models of a logic program P coincide with the $σ_{arg}$ argument labellings of ${AF}_{P}$ ,12 ¹²
which is the case when $σ_{lp} = ideal$ and $σ_{arg} = ideal$ , when $σ_{lp} = 3-valued stable$ and $σ_{arg} = complete$ , when $σ_{lp} = regular$ and $σ_{arg} = preferred$ and when $σ_{lp} = 2-valued stable$ and $σ_{arg} = stable$
it follows that the $σ_{arg}$ argument labellings of any argumentation framework $AF$ also coincide with the $σ_{lp}$ models of the associated logic program $P_{AF}$ [16].

We next focus our attention on eager semantics. As we have seen in Example 3, the eager model of a logic program does not necessarily coincide with the eager argument labelling of the associated argumentation framework.

At the same time, Example 3 cannot be seen as a counter example against the equivalence of eager semantics for formal argumentation and eager semantics for logic programming, when translating from formal argumentation to logic programming. That is, Example 3 does not show that there exists an argumentation framework $AF$ whose eager argument labelling does not coincide with the eager model of its associated logic program $P_{AF}$ . In fact, it turns out that for each argumentation framework $AF$ , its eager argument labelling does coincide with the eager model of the associated logic program $P_{AF}$ . In order to prove so, we first observe that an argumentation framework translates into a very specific class of logic programs, called AF-programs [16].
Definition 26 ([16]).

A logic program P is called an AF-program iff there is at most one rule r with $head (r) = c$ for each $c \in {HB}_{P}$ .

It turns out that each AF-program is semi-stable-compatible [16, Theorem 29].

Theorem 13 ([16]).

Let P be an AF-program. It holds that P is semi-stable-compatible.

Lemma 14.
Let $AF = (Ar, att)$ be an argumentation framework and let $P_{AF}$ be its associated logic program (Definition 24 ). Let $ArgLab$ be the eager argument labelling of $AF$ and let $ConcLab$ be the arg-eager conclusion labelling of $P_{AF}$ . It holds that $ArgLab = ConcLab$ .
Proof.
Similar to the proof of Lemma 11. □
Theorem 15.
Let $AF = (Ar, att)$ be an argumentation framework and let $P_{AF}$ be its associated logic program (in line with Definition 24 ). Let $ArgLab$ be the eager argument labelling of $AF$ and let $Mod = ⟨ T, F ⟩$ be the eager model of P. It holds that:
$Mod = ConcLab 2 Mod (ArgLab)$

$ArgLab = Mod 2 ConcLab (Mod)$

Proof.

As $ArgLab$ is the eager argument labelling of $AF$ , it follows from Lemma 14 that $ArgLab$ is also the arg-eager conclusion labelling of $P_{AF}$ . From point (2) of Theorem 9 it follows that $ArgLab$ is also a conc-eager conclusion labelling of $P_{AF}$ . From Theorem 8 (point 4) it follows that $ConcLab 2 Mod (ArgLab)$ is the eager model of $P_{AF}$ . That is, $ConcLab 2 Mod (ArgLab) = Mod$ .

As $Mod$ is the eager model of $P_{AF}$ it follows that $Mod 2 ConcLab (Mod)$ is the conc-eager conclusion labelling of $P_{AF}$ (Theorem 8, point 3). From Theorem 9 (point 2) it follows that $Mod 2 ConcLab (Mod)$ is also the arg-eager conclusion labelling of $P_{AF}$ . From Lemma 14 it then follows that $Mod 2 ConcLab (Mod)$ is also the eager argument labelling of $AF$ , That is, $Mod 2 ConcLab (Mod) = ArgLab$ .
□
6. Discussion

In the current paper, we extended the work of [16,47] by examining whether additional semantical correspondences hold between formal argumentation and logic programming, in particular in the context of ideal and eager semantics. For this, we made use of a recent reformulation of ideal semantics for logic programming (from [17]) that is roughly equivalent to the characterization of MD-stable models for logic programming [38], but offers a simpler presentation. This reformulation of ideal semantics for logic programming made it possible to define eager semantics for logic programming in a similar way.

Overall, we observe that when translating a logic program to an argumentation framework, the ideal model of the logic program coincides with the ideal argument labelling of the argumentation framework. However, the eager model of the logic program does not necessarily coincide with the eager argument labelling of the argumentation framework. These two findings, together with the findings of [16,47], are summarised in Table 3.

Table 3

Semantical correspondences and non-correspondences when translating from LP to argumentation

Logic programming model	Coincides	Argument labelling
3-valued stable	Yes [47]	Complete
Well-founded	Yes [16]	Grounded
Regular	Yes [16]	Preferred
L-stable	No [16]	Semi-stable
2-valued stable	Yes [16]	Stable
Ideal	Yes (Theorem 7)	Ideal
Eager	No (Example 3)	Eager

When translating an argumentation framework to a logic program, the situation is slightly different. Not only does the ideal argument labelling of the argumentation framework coincide with the ideal model of the logic program, the eager argument labelling of the argumentation framework also coincides with the eager model of the logic program. These two findings, together with the findings of [16,47], are summarised in Table 4.

Table 4

Semantical correspondences and non-correspondences when translating from argumentation to LP

Argument labelling	Coincides	Logic programming model
Complete	Yes [47]	3-valued-stable
Grounded	Yes [16]	Well-founded
Preferred	Yes [16]	Regular
Semi-stable	Yes [16]	L-stable
Stable	Yes [16]	2-valued stable
Ideal	Yes (Theorem 12)	Ideal
Eager	Yes (Theorem 15)	Eager

Table 3 and Table 4 round off our analysis of how mainstream admissibility-based semantics (at least those mentioned in [13]) relate to their logic programming counterparts. Notice that we did not analyse any correspondences in the context of non-admissibility-based semantics, such as naive, stage, CF2 and stage2. This is because as far as we are aware, comparable semantics have not been defined in the context of logic programming, and it is not immediately clear how such could be done.

The results of the current paper (and of [16,47]) go beyond the correspondences mentioned in Table 3 and Table 4, as we essentially compared two fundamental ways in which formal argumentation theory can be used to infer conclusions. Both are based on complete semantics (which in logic programming context is called 3-valued stable semantics). One of them (the instantiated argumentation way) works by making a selection on the argument level (such as selecting those argument labellings where a particular label is minimal or maximal) and then translating to the conclusion level. The other one (the logic programming way) works (at least conceptually) by translating all argument labellings to conclusion labellings and then doing the selection on the conclusion level (such as selecting those conclusion labellings where a particular label is minimal or maximal). What Table 3 and Table 4 in essence show is in which case doing a particular selection on the argument level yields the same result as doing a comparable selection on the conclusion level. Our findings should also benefit some similar investigations exploring semantic correspondences between logic programming semantics and other argumentation formalisms, such as [1,36,37,42].

It is worth noticing that Nieves and Osorio [34] found that the ideal semantics for argumentation frameworks could be captured by the WFS+ semantics13 ¹³

Given a program P, the WFS+ semantics provides a unique model which complements the well-founded model $WFS (P)$ of P with atoms that are classically entailed by P. Dix [23] writes that $P ⊧ a$ iff a is true in every 2-valued model of P. Here, models are expressed simply as sets of true atoms. The WFS+ model of a logic program P is then obtained as the least fix-point of the sequence $M_{k + 1} = SEM (P \cup M_{k})$ of subsets of ${HB}_{P}$ , where $SEM (P) = WFS (P) \cup {a \in {HB}_{P} ∣ P ⊧ a}$ and $M_{0} = \emptyset$ .

[23] for normal logic programs, but their result is based on a rather different translation from ours. Intuitively, their translation describes an argumentation framework in terms of conditions for each argument to be defeated (an argument is defeated if one or more of its attackers is not defeated; an argument is defeated if all of its potential defenders are defeated) and accepted (an argument is accepted if it is not defeated). As an example, consider the very simple argumentation framework

{AF}_{3} = ({A}, {(A, A)})

. Using the translation of Nieves and Osorio [34], we obtain the program

Π_{{AF}_{3}} = {r_{1} : def (A) \leftarrow not def (A), r_{2} : def (A) \leftarrow def (A), r_{3} : acc (A) \leftarrow not def (A)}

. This translation favours the use of more classical semantics obtained by replacing

not

with the classic negation. In our example,

Π_{{AF}_{3}}

has a single 2-valued model

{def (A)}

, which will also be its WFS+ model.14 ¹⁴

For short, let us make $Π_{{AF}_{3}} = Π_{3}^{0}$ . Starting from $M_{0} = \emptyset$ , we obtain $M_{1} = SEM (Π_{3}^{0} \cup M_{0}) = SEM (Π_{3}^{0}) = WFS (Π_{3}^{0}) \cup {a \in {HB}_{Π_{3}^{0}} ∣ Π_{3}^{0} ⊧ a}$ . Given that $WFS (Π_{3}^{0}) = \emptyset$ , this means $M_{1} = \emptyset \cup {def (A)} = {def (A)}$ . Next, we must compute $M_{2} = SEM (Π_{3}^{0} \cup M_{1}) = SEM (Π_{3}^{0} \cup {def (A)})$ . For short, let us make $Π_{3}^{0} \cup {def (A)} = Π_{3}^{1}$ . We obtain $M_{2} = SEM (Π_{3}^{0} \cup M_{1}) = SEM (Π_{3}^{1}) = WFS (Π_{3}^{1}) \cup {a \in {HB}_{Π_{3}^{1}} ∣ Π_{3}^{1} ⊧ a}$ . Now we have $WFS (Π_{3}^{1}) = {def (A)}$ , so $M_{2} = {def (A)} \cup {def (A)} = {def (A)} = M_{1}$ . This means $WFS+ (Π_{{AF}_{3}}) = {def (A)}$ .

From there, one can obtain the ideal extension of

{AF}_{3}

by taking the arguments that are accepted in the WFS+ model of

Π_{{AF}_{3}}

. In this case, there are no accepted arguments, so the ideal extension of

{AF}_{3}

is empty, which is correct. In contrast, the same result cannot be replicated using our translation; we would find

P_{{AF}_{3}} = {A \leftarrow not A}

, for which the WFS+ model is

{A}

. Notice that

{A}

is not even admissible for

{AF}_{3}

, so immediately the WFS+ semantics will differ from all admissible argumentation semantics using our translation. We believe the above advocates in favour of our approach being more straightforward, especially concerning translations. It should also be noticed that Nieves and Osorio do not consider translating logic programs into argumentation frameworks (they only translate one way, we do both) and that their approach does not properly differentiate between defeated and undecided arguments for some argumentation semantics in the resulting program. On that matter, it suffices to see that A is undecided in the ideal argument labelling of

{AF}_{3}

, but the WFS+ semantics for

Π_{{AF}_{3}}

concludes

def (A)

, which should intuitively mean that A is defeated. Instead, in their attempt to capture the ideal semantics of

{AF}_{3}

def (A)

means only that A is not accepted, therefore finding no conclusion to whether A is defeated or undecided. In contrast, our approach is natively 3-valued, allowing us to properly state the acceptance status of all arguments in an argumentation framework in each of the semantics we mentioned.

One particular topic that is still open is how formal argumentation relates to logic programming in the context of preferences. In formal argumentation, preferences are often accounted for by removing [21,33] or even adding [21] particular attacks from and to the argumentation framework. In logic programming, preferences are often accounted for by selecting among the various logic programming models those that are most in line with the preferences (see [22] for an overview). Hence, whereas preferences in formal argumentation are accounted for before computing semantics, possibly changing the argumentation framework itself, in logic programming the preferences are accounted for during semantics computation. To identify whether there are conditions under which the first approach corresponds to the second approach is a promising topic for further research.

So far, the existing approaches were compared almost exclusively within their native systems. One exception would be Wakaki’s approach to preference-based argumentation [45], which adapts the approach of Sakama and Inoue’s Prioritized Logic Programming (PLP) [40] to formal argumentation. Wakaki [45] proposes preference-based argumentation semantics and shows some correspondences to preferential semantics for logic programs hold, and we believe several more correspondences are also likely to hold. This idea is supported by recent findings of Silva et. al. [41], who complemented the set of semantics of Amgoud and Vesic [3] for preferential AFs to show they preserve the same hierarchy as their counterpart semantics in Dung’s AFs. It turns out that the logic programming semantics we studied (together with [16,47]) hold the same hierarchy as their counterpart AF semantics too.

Therefore, a particularly promising path of research enabled by our work is the potential adaptation of approaches using static preferences over literals from logic programming (such as [40], but see also [22]) to develop new approaches for preferences in abstract argumentation. This much is enabled by Definition 24 (taken from [16,47]), which ensures an AF can be written as a normal logic program that fully preserves its admissibility-based semantics, at least up from complete semantics. In short, the semantics of any approaches to logic programs with preferences over literals can be adapted for AFs using the mapping in Definition 24.

References

Alcântara,

Sá and

Acosta-Guadarrama, On the equivalence between abstract dialectical frameworks and logic programs, Theory and Practice of Logic Programming 19(5–6) (2019), 941–956. doi:10.1017/S1471068419000280.

J.J.

Alferes,

P.M.

Dung and

Pereira, Scenario semantics of extended logic programs, in: Proc. 2nd International Workshop on Logic Programming and Non-monotonic Reasoning,

Nerode and

Pereira, eds, MIT Press, 1993, pp. 334–348.

Amgoud and

Vesic, A new approach for preference-based argumentation frameworks, Annals of Mathematics and Artificial Intelligence 63(2) (2011), 149–183. doi:10.1007/s10472-011-9271-9.

Baroni,

M.W.A.

Caminada and

Giacomin, An introduction to argumentation semantics, Knowledge Engineering Review 26(4) (2011), 365–410. doi:10.1017/S0269888911000166.

Baroni and

Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171(10–15) (2007), 675–700. doi:10.1016/j.artint.2007.04.004.

Baumann, On the nature of argumentation semantics: Existence and uniqueness, expressibility, and replaceability, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018.

Baumann and

Spanring, Infinite argumentation frameworks – on the existence and uniqueness of extensions, in: Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation – Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday,

Eiter,

Strass,

Truszczyński and

Woltran, eds, Springer, 2015, pp. 281–295. doi:10.1007/978-3-319-14726-0_19.

Besnard and

Hunter, Constructing argument graphs with deductive arguments: A tutorial, Argument & Computation 5 (2014), 5–30, Special Issue: Tutorials on Structured Argumentation. doi:10.1080/19462166.2013.869765.

Bondarenko,

P.M.

Dung,

R.A.

Kowalski and

Toni, An abstract, argumentation-theoretic approach to default reasoning, Artificial Intelligence 93 (1997), 63–101. doi:10.1016/S0004-3702(97)00015-5.

10.

M.W.A.

Caminada, On the issue of reinstatement in argumentation, in: Logics in Artificial Intelligence; 10th European Conference, JELIA 2006,

Fischer,

van der Hoek,

Konev and

Lisitsa, eds, LNAI, Vol. 4160, Springer, 2006, pp. 111–123.

11.

M.W.A.

Caminada, Comparing two unique extension semantics for formal argumentation: Ideal and eager, in: Proceedings of the 19th Belgian-Dutch Conference on Artificial Intelligence (BNAIC 2007),

M.M.

Dastani and

de Jong, eds, 2007, pp. 81–87.

12.

M.W.A.

Caminada, Argumentation semantics as formal discussion, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018, pp. 487–518.

13.

M.W.A.

Caminada,

Baroni and

Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018.

14.

M.W.A.

Caminada and

D.M.

Gabbay, A logical account of formal argumentation, Studia Logica 93(2–3) (2009), 109–145, Special issue: new ideas in argumentation theory. doi:10.1007/s11225-009-9218-x.

15.

M.W.A.

Caminada and

Pigozzi, On judgment aggregation in abstract argumentation, Autonomous Agents and Multi-Agent Systems 22(1) (2011), 64–102. doi:10.1007/s10458-009-9116-7.

16.

M.W.A.

Caminada,

Sá,

Alcântara and

Dvořák, On the equivalence between logic programming semantics and argumentation semantics, International Journal of Approximate Reasoning 58 (2015), 87–111. doi:10.1016/j.ijar.2014.12.004.

17.

M.W.A.

Caminada and

Schulz, On the equivalence between assumption-based argumentation and logic programming, Journal of Artificial Intelligence Research 60 (2017), 779–825. doi:10.1613/jair.5581.

18.

M.W.A.

Caminada and

Uebis, An implementation of argument-based discussion using aspic, in: Computational Models of Argument. Proceedings of COMMA 2020,

Prakken,

Bistarelli,

Santini and

Taticchi, eds, IOS Press, 2020, pp. 455–456.

19.

M.W.A.

Caminada and

Verheij, On the existence of semi-stable extensions, in: Proceedings of the 22nd Benelux Conference on Artificial Intelligence,

Danoy,

Seredynski,

Booth,

Gateau,

Jars and

Khadraoui, eds, 2010.

20.

Čyras,

Fan,

Schulz and

Toni, Assumption-based argumentation: Disputes, explanations, preferences, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018.

21.

Čyras and

Toni, Aba+: Assumption-based argumentation with preferences, in: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2016), 2016, pp. 553–556.

22.

Delgrande,

Schaub,

Tompits and

Wang, A classification and survey of preference handling approaches in nonmonotonic reasoning, Computational Intelligence 20(2) (2004), 308–334. doi:10.1111/j.0824-7935.2004.00240.x.

23.

Dix, A classification theory of semantics of normal logic programs: I. strong properties, Fundamenta Informaticae 22(3) (1995), 227–255. doi:10.3233/FI-1995-2233.

24.

P.M.

Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77 (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.

25.

P.M.

Dung,

Mancarella and

Toni, Computing ideal sceptical argumentation, Artificial Intelligence 171(10–15) (2007), 642–674. doi:10.1016/j.artint.2007.05.003.

26.

Gorogiannis and

Hunter, Instantiating abstract argumentation with classical logic arguments: Postulates and properties, Artificial Intelligence 175(9–10) (2011), 1479–1497. doi:10.1016/j.artint.2010.12.003.

27.

Governatori,

M.J.

Maher,

Antoniou and

Billington, Argumentation semantics for defeasible logic, Journal of Logic and Computation 14(5) (2004), 675–702. doi:10.1093/logcom/14.5.675.

28.

Jakobovits and

Vermeir, Robust semantics for argumentation frameworks, Journal of logic and computation 9(2) (1999), 215–261. doi:10.1093/logcom/9.2.215.

29.

A.C.

Kakas and

Mancarella, Short note preferred extensions are partial stable models, The Journal of Logic Programming 14(3–4) (1992), 341–348. doi:10.1016/0743-1066(92)90015-U.

30.

Marshall,

Booth and

M.W.A.

Caminada, Disco: A web-based implementation of discussion games for grounded and preferred semantics, in: Computational Models of Argument. Proceedings of COMMA 2018,

Lawrence,

Modgil and

Budzynska, eds, 2018, pp. 453–454.

31.

Modgil and

Prakken, A general account of argumentation with preferences, Artificial Intellligence 195 (2013), 361–397. doi:10.1016/j.artint.2012.10.008.

32.

Modgil and

Prakken, The ASPIC+ framework for structured argumentation: A tutorial, Argument & Computation 5 (2014), 31–62, Special Issue: Tutorials on Structured Argumentation. doi:10.1080/19462166.2013.869766.

33.

Modgil and

Prakken, Abstract rule-based argumentation, in: Handbook of Formal Argumentation, Vol. 1, College Publications, 2018. doi:10.1007/978-3-319-75553-3.

34.

J.C.

Nieves and

Osorio, Ideal extensions as logical programming models, Journal of Logic and Computation 26(5) (2016), 1361–1393. doi:10.1093/logcom/exu014.

35.

T.C.

Przymusinski, The well-founded semantics coincides with the three-valued stable semantics, Fundamenta Informaticae 13(4) (1990), 445–463.

36.

Sá, On the expressive power of argumentation formalisms, in: Online Handbook of Argumentation for AI, 2020, p. 33.

37.

Sá and

Alcântara, Interpretations and models for assumption-based argumentation, in: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, SAC ’19, Association for Computing Machinery, New York, NY, USA, 2019, pp. 1139–1146.

38.

Saccà and

Zaniolo, Stable models and non-determinism in logic programs with negation, in: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, Tennessee, USA, April 2–4, 1990,

D.J.

Rosenkrantz and

Sagiv, eds, ACM Press, 1990, pp. 205–217.

39.

Saccà and

Zaniolo, Deterministic and non-deterministic stable models, Journal of Logic and Computation 7(5) (1997), 555–579. doi:10.1093/logcom/7.5.555.

40.

Sakama and

Inoue, Prioritized logic programming and its application to commonsense reasoning, Artificial Intelligence 123(1–2) (2000), 185–222. doi:10.1016/S0004-3702(00)00054-0.

41.

Silva,

Sá and

Alcântara, Semantics hierarchy in preference-based argumentation frameworks, in: Computational Models of Argument – Proceedings of COMMA 2020, Perugia, Italy, September 4–11, 2020,

Prakken,

Bistarelli,

Santini and

Taticchi, eds, Frontiers in Artificial Intelligence and Applications, Vol. 326, IOS Press, 2020, pp. 339–346.

42.

Strass, Approximating operators and semantics for abstract dialectical frameworks, Artificial Intelligence 205 (2013), 39–70. doi:10.1016/j.artint.2013.09.004.

43.

P.M.

Thang,

P.M.

Dung and

N.D.

Hung, Towards a common framework for dialectical proof procedures in abstract argumentation, Journal of Logic and Computation 19(6) (2009), 1071–1109. doi:10.1093/logcom/exp032.

44.

Toni, A tutorial on assumption-based argumentation, Argument & Computation 5 (2014), 89–117, Special Issue: Tutorials on Structured Argumentation. doi:10.1080/19462166.2013.869878.

45.

Wakaki, Preference-based argumentation built from prioritized logic programming, Journal of Logic and Computation 25(2) (2015), 251–301. doi:10.1093/logcom/exs066.

46.

Weydert, Semi-stable extensions for infinite frameworks, in: Proceedings of the 23rd Benelux Conference on Artificial Intelligence (BNAIC 2011),

de Causmaecker,

Maervoet,

Messelis,

Verbeeck and

Vermeulen, eds, 2011, pp. 336–343.

47.

Wu,

M.W.A.

Caminada and

D.M.

Gabbay, Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Studia Logica 93(1–2) (2009), 383–403, Special issue: new ideas in argumentation theory. doi:10.1007/s11225-009-9210-5.