An Abstract Argumentation and Logic Programming Comparison Based on 5-Valued Labellings

Abstract

Abstract argumentation and logic programming are two formalisms of non-monotonic reasoning that share many similarities. Previous studies contemplating connections between the two formalisms provided back and forth translations from one to the other and found they correspond in multiple different semantics, but not all. In this work, we propose a new set of five argument labels to revisit the semantic correspondences between abstract argumentation and logic programming. By doing so, we shed light on why the two formalisms are not absolutely equivalent. Our investigation lead to the specification of the novel least-stable semantics for abstract argumentation which corresponds to the L-stable semantics of logic programming.

1 Introduction

Logic Programming (LP) and Abstract Argumentation Frameworks are two different formalisms widely used for the representation of knowledge and reasoning. Abstract Argumentation (AA) was itself inspired by logic programming in its origins, which naturally led to several studies concerning connections between them [5, 6, 8, 11, 14, 16]. One of the main approaches to observe those connections is based on the comparison of the different semantics proposed for each formalism. To that end, the first questions were raised and answered in [6], the work that originally introduced abstract argumentation: a translation from a logic program into an abstract argumentation framework was proposed and used to prove that the stable models (resp. the well-founded model) of a logic program correspond to the stable extensions (resp. the grounded extension) of its corresponding abstract argumentation framework. Other advances were made when [16] observed the equivalence between the complete semantics for abstract argumentation and the p-stable semantics for logic programs. Those particular semantics generalise many others in their respective formalisms, wielding a plethora of results gathered in [5] and recently expanded in [4]. One particular equivalence formerly expected to hold, however, could not be achieved, namely the correspondence between the semi-stable semantics from abstract argumentation [3] and the L-stable semantics from logic programming [9]. The work we are about to present is largely motivated by that non-correspondence result.

In our efforts to understand why the semi-stable and L-stable semantics do not correspond to one another, we detected the fault is always related to some arguments whose attackees coincide; in their redundancy, one or more of those arguments would be irrelevant to the evaluation of those arguments they mutually attack. We were also able to identify that sink¹ arguments play a special role in pinpointing the culprits. To achieve our goals for this work, we follow the presentation of [5] while revising some key definitions: (i) the instantiation of abstract argumentation frameworks from logic programs is revised to include special arguments we call default arguments (which are always sinks) and (ii) we revise the definition of complete argument labellings [2] to use a different set of labels. Our revision of complete labellings follows [1, 10] to contemplate partial labellings and different categories of undecidedness. The resulting labellings, here on called 5-valued labellings, can isolate any arguments causing semi-stable and L-stable semantics to differ and are shown to preserve the main results in [5].

Based on those results, we introduce a novel semantics for abstract argumentation called the least-stable (or L-stable) semantics, which we show is equivalent to the L-stable LP semantics. The new AA semantics closes the previous gap preventing the claim that AA is actually equivalent to LP. Our results add further to the literature concerning semantics of non-monotonic reasoning formalisms, potentially allowing us to import proof procedures and implementations from formal argumentation to logic programming and vice-versa. Among other implications of our work, we set precedence to the proposal of new argumentation semantics based on partial labellings. We also establish that sink arguments have a role in the semantic evaluation of abstract argumentation frameworks, which may also help us identify new interesting AA semantics. Moreover, we show that if we restrict our attention to sink arguments, the standard 3-valued labellings are enough to capture the logic programming L-stable semantics.

2 Preliminaries

2.1 Abstract Argumentation

Abstract argumentation was introduced in [7] and most of the definitions in this section are based on that work. Concerning new definitions, we will compute the set of sink arguments of an abstract argumentation framework and use them to propose argumentation semantics in the form of 5-valued labellings, a core trait of our approach.

Definition 1

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

We may refer to AA frameworks simply as argumentation frameworks or AF’s.

Definition 2

Given an argumentation framework $\mathtt {AF}= ( Ar , att )$, the set of its sink arguments is given by $\mathtt {SINKS}_\mathtt {AF}= \left\{ A \in Ar \mid \forall B, (A,B) \notin att \right\}$.

The traditional approach of [7] to semantics involves the identification of sets of arguments (called extensions) based on the concept of admissibility (see [7]). An alternative formalization of AA semantics was introduced in [2] where argument labellings are used instead of extensions. The argument labellings of [2] are functions attributing to each argument a single label from $\left\{ \mathtt {in}, \mathtt {out}, \mathtt {undec}\right\}$. In this work, we specialise the labels $\mathtt {out},\mathtt {undec}$ into two different labels each based on the sink arguments they attack. Our labelling concept follows the lead of [1], where the authors explore alternative sets of labels and special cases of undecidedness in argumentation semantics. We borrow some of the labels discussed in their work, namely the “I don’t care” ($\mathtt {idc}$) label (originally proposed in [10]) and the “I don’t know” ($\mathtt {idk}$) label ([1]) and we introduce a new label of our own, here dubbed “It doesn’t matter if it’s out” ($\mathtt {ido}$). Hence, in our work, given an argumentation framework $\mathtt {AF}= ( Ar , att )$, an argument labelling $Al$ will be a function $Al : Ar \rightarrow \{ \mathtt {in}, \mathtt {out}, \mathtt {ido}, \mathtt {idk}, \mathtt {idc}\}$. We will start defining complete labellings, since the other relevant semantics are special cases of them.

Definition 3

An argument labelling is called a complete argument labelling iff for each $A \in Ar$ it holds that

• $Al (A) = \mathtt {in}$ iff all B that attacks A has $Al (B) \in \left\{ \mathtt {out},\mathtt {ido}\right\}$.

• $Al (A) = \mathtt {out}$ iff at least one B that attacks A has $Al (B) = \mathtt {in}$ and A attacks no sink C with $Al (C) = \mathtt {idk}$.

• $Al (A) = \mathtt {ido}$ iff at least one B that attacks A has $Al (B) = \mathtt {in}$ and A attacks at least one sink C with $Al (C) = \mathtt {idk}$

• $Al (A) = \mathtt {idk}$ iff at least one B that attacks A has $Al (B) \in \left\{ \mathtt {out},\mathtt {ido}\right\}$, no B that attacks A has $Al (B) = \mathtt {in}$, and every sink C attacked by A has $Al (C) = \mathtt {idk}$.

• $Al (A) = \mathtt {idc}$ iff at least one B that attacks A has $Al (B) \in \left\{ \mathtt {out},\mathtt {ido}\right\}$, no B that attacks A has $Al (B) = \mathtt {in}$, and at least one sink C attacked by A has $Al (C) \ne \mathtt {idk}$.

As one can observe, the sink arguments influence the evaluation of arguments in our definition. For instance, the only difference between labelling an argument as $\mathtt {out}$ or $\mathtt {ido}$ is whether that argument attacks any $\mathtt {idk}$-labelled sinks. As such, $\mathtt {out}$ and $\mathtt {ido}$ are merely specialisations of the $\mathtt {out}$ label from the standard 3-valued labellings of [2]. The same holds for $\mathtt {idk}$ and $\mathtt {idc}$, as specialisations of $\mathtt {undec}$ from [2]. Intuitively, $\mathtt {idk}$ replaces $\mathtt {undec}$ in most cases; $\mathtt {idc}$ (resp. $\mathtt {ido}$) is used when the status of a classically $\mathtt {undec}$ (resp. $\mathtt {out}$) argument is irrelevant to the status of its attackee. In a way, the labels $\mathtt {ido},\mathtt {idc}$ allow us to sometimes evaluate one extra argument (using $\mathtt {ido}$) or one less argument (using $\mathtt {idc}$) as undecided. This is enough to ensure that our 5-valued complete labellings from Definition 3 are one to one related to the 3-valued complete labellings of [2] and preserve the complete semantics for abstract argumentation frameworks. The same holds for the grounded, preferred, stable and semi-stable semantics, as they are all particular cases of the complete semantics. Another straightforward result is

Proposition 1

Let $( Ar , att )$ be an AF and $Al$ be one of its complete argument labellings. For every sink argument $C \in \mathtt {SINKS}_\mathtt {AF}$, it holds $Al (C) \in \{ \mathtt {in}, \mathtt {out}, \mathtt {idk}\}$.

Given an argument labelling $Al$, we write $\mathtt {v}( Al ) = \{ A \mid Al (A) = \mathtt {v}\}$ for $\mathtt {v}\in \{\mathtt {in}, \mathtt {out},$ $\mathtt {ido},$ $\mathtt {idk},\mathtt {idc}\}$. An argument labelling provides a partition of $Ar$, so we might as well present $Al$ as a tuple $(\mathtt {in}( Al ), \mathtt {out}( Al ), \mathtt {ido}( Al ), \mathtt {idk}( Al ), \mathtt {idc}( Al ))$.

The next definition adapts from well-known results concerning the 3-valued argument labellings of [2, 5]. Our adaptation maps the 3-valued label $\mathtt {undec}$ to $\mathtt {idk}\cup \mathtt {idc}$, the specialised labels we created from the standard $\mathtt {undec}$.

Definition 4

Let $\mathcal {AL}$ be the set of all complete argument labellings of $\mathtt {AF}$. Then

• $Al \in \mathcal {AL}$ is grounded if $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {in}( Al ') \subsetneq \mathtt {in}( Al )$.

• $Al \in \mathcal {AL}$ is preferred if $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {in}( Al ') \supsetneq \mathtt {in}( Al )$.

• $Al \in \mathcal {AL}$ is stable if $\mathtt {idk}( Al ) \cup \mathtt {idc}( Al ) = \emptyset$.

• $Al \in \mathcal {AL}$ is semi-stable if $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {idk}( Al ') \cup \mathtt {idc}( Al ') \subsetneq \mathtt {idk}( Al ) \cup \mathtt {idc}( Al )$.

The following example should help the reader to further understand these concepts.

Example 1

The argumentation framework $\mathtt {AF}$ below has complete labellings $Al _1 = (\left\{ \ \right\} , \left\{ \ \right\} , \left\{ \ \right\} , Ar , \left\{ \ \right\} )$, $Al _2 = (\left\{ A_2, A_8 \right\} , \left\{ A_3, A_7 \right\} , \left\{ A_4 \right\} , \left\{ A_1, A_5, A_6, A_9 \right\} , \left\{ \ \right\} )$, $Al _3 = (\left\{ A_3, A_7, A_9 \right\} , \left\{ A_2, A_5, A_8 \right\} , \left\{ \ \right\} , \left\{ A_1, A_4, A_6 \right\} , \left\{ \ \right\} )$. The grounded labelling of $\mathtt {AF}$ is $Al _1$ and its preferred labellings are $Al _2, Al _3$. $\mathtt {AF}$ has no stable labellings, but has two semi-stable labellings, namely $Al _2, Al _3$. For contrast, the corresponding argument labellings in Caminada’s 3-valued approach are $Al '_1 = (\left\{ \ \right\} , \left\{ \ \right\} , Ar )$, $Al '_2 = (\left\{ A_2, A_8 \right\} , \left\{ A_3, A_7, A_4 \right\} , \left\{ A_1, A_5, A_6, A_9 \right\} )$, $Al '_3 = (\left\{ A_3, A_7, A_9 \right\} , \left\{ A_2, A_5, A_8\right\} ,$ $\left\{ A_1, A_4, A_6 \right\} )$. We highlight the difference between $Al _2$ and $Al '_2$ due to $\mathtt {ido}( Al _2) \ne \emptyset$.

It should be noticed that sink arguments were only attributed labels $\mathtt {in}, \mathtt {out}, \mathtt {idk}$, as previously stated in Proposition 1.

2.2 Logic Programs and Semantics

In the current paper, we account for propositional normal logic programs², which we call logic programs or simply programs from now on. We will follow the presentation of logic programs and their semantics as done in [5], which, in turn, is based on [13].

Definition 5

A rule r is an expression

$$r: c \leftarrow a_1, \ldots , a_n, \mathtt {not}\; b_1, \ldots , \mathtt {not}\; b_m$$

($m,n \ge 0$) where c, each $a_i$ ($1 \le i \le n$) and each $b_j$ ($1 \le j \le m$) are atoms and $\mathtt {not}$ represents negation as failure. A literal is either an atom a (positive literal) or a negated atom $\mathtt {not\ }a$ (negative literal). Given a rule r as above, c is called the head of r, which we denote head(r), and $a_1, \ldots , a_n, \mathtt {not}\; b_1, \ldots , \mathtt {not}\; b_m$ is called the body of r, denoted body(r). Further, we divide body(r) in two sets $body^{+}(r) = \{a_1, \ldots , a_n\}$ and $body^{-}(r) = \{ \mathtt {not}\; b_1, \ldots , \mathtt {not}\; b_m \}$. A logic program (or simply a program or LP) P is then defined as a finite set of rules. If every $r \in P$ has $body^{-}(r) = \emptyset$, then P is positive. The Herbrand Base of P is the set $HB _{P}$ of all atoms appearing in the program.

Definition 6

A 3-valued Herbrand Interpretation I of a logic program P is a pair $\langle T,F \rangle$ with $T,F \subseteq HB _P$ and $T \cap F = \emptyset$. The atoms in T are said to be true, the atoms in F are said to be false and the atoms in $HB _P \setminus (T \cup F)$ are said to be undefined.

Definition 7

A 3-valued Herbrand interpretation I of a logic program P is called a model if $I(head(r)) \ge \mathtt {min}(\left\{ I(l) \mid l \in body(r)\right\} )$ for each $r \in P$, according to the order true > undefined > false.

Let I be a 3-valued Herbrand Interpretation of P, the reduct of P with respect to I (written P/I) can be obtained replacing each occurrence of a naf-literal $\mathtt {not\ }c$ in P “$\mathtt {true}$” if $c \in F$, by “$\mathtt {false}$” if $c \in T$, or by “$\mathtt {undefined}$” otherwise. In this context, “$\mathtt {true}$”, “$\mathtt {false}$” and “$\mathtt {undefined}$” are special atoms not occurring in P which are necessarily evaluated according to their naming conventions. This procedure ensures P/I has no instances of negative literals. As consequence, P/I has a unique least 3-valued model [13] hereby denoted $\Psi _P(I) = \langle T_{\Psi }, F_{\Psi } \rangle$³ with minimal $T_{\Psi }$ and maximal $F_{\Psi }$ (w.r.t. set inclusion) such that, for every $a \in HB _{P}$:

• $a \in T_{\Psi }$ if there is a rule $r^{\prime } \in P/I$ with $head(r^{\prime }) = a$ and $body^{+}(r^{\prime }) \subseteq T_{\Psi }$;

• $a \in F_{\Psi }$ if every rule $r^{\prime } \in P/I$ with $head(r^{\prime }) = a$ has $body^{+}(r^{\prime }) \cap F_{\Psi } \ne \emptyset$;

Definition 8

Let $I = \langle T,F \rangle$ be a 3-valued Herbrand Interpretation of program P.

• I is a partial stable (or P-stable) model of P iff $\Psi _P(I) = I$.

• T is a well-founded model of P iff I is a P-stable model of P where T is minimal (w.r.t. set inclusion) among all P-stable models of P.

• T is a regular model of P iff I is a P-stable model of P where T is maximal (w.r.t. set inclusion) among all P-stable models of P.

• T is a stable model of P iff I is a P-stable model of P where $T \cup F = HB _P$.

• T is an L-stable model of P iff I is a P-stable model of P where $T \cup F$ is maximal (w.r.t. set inclusion) among all P-stable models of P.

While some of the above definitions are not standard in logic programming literature, their equivalence is proved in [5]. This approach is favored in our work due to the structural similarities to Definition 4, simplifying the proof of some results.

The following example should help the reader to understand the above concepts.

Example 2

Consider the following logic program P:

$$ \begin{array}{llcll} r_{1}: &{} c \leftarrow \mathtt {not}\; c &{} \ &{} r_{4}: &{} c \leftarrow \mathtt {not}\; c, \mathtt {not}\; a \\ r_{2}: &{} a \leftarrow \mathtt {not}\; b &{} \ &{} r_{5}: &{} g \leftarrow \mathtt {not}\; g, \mathtt {not}\; b \\ r_{3}: &{} b \leftarrow \mathtt {not}\; a &{} \ &{} \ &{} \ \end{array} $$

This program has three P-stable models: $I_1 = \langle \{ \ \}, \{ \ \} \rangle$, $I_2 = \langle \{ a \}, \{ b \} \rangle$, $I_3 = \langle \{ b \}, \{ a, g \} \rangle$. P has $\{ \ \}$ for its well-founded model (always unique), $\{ a \}$, $\{ b \}$ for its regular models, no stable models and only $\{ b \}$ as an L-stable model.

3 From Logic Programs to Argumentation Frameworks

In this section, we review the procedure used to instantiate argumentation frameworks based on logic programs from [5] with slight updates to each step. Our updates are required to include special arguments we call default arguments, which are necessarily sinks, in the result. By design, they will be the only sinks in the output of our procedure.

3.1 Step 1: AF Instantiation

Given a normal logic program P, we recursively instantiate the following arguments:

Definition 9

Let P be a logic program.

• If $r: c \leftarrow \mathtt {not\ }b_1, \ldots , \mathtt {not\ }b_m$ is a rule in P then r is also an argument (say A) with $\mathtt {Conc}(A) = c$, $\mathtt {Rules}(A) = \{ r \}$, $\mathtt {Vul}(A) = \{ b_1, \ldots , b_m\}$ and $\mathtt {Sub}(A) = \{A\}$.

• If $r: c \leftarrow a_1,\ldots ,a_n, \mathtt {not}\; b_1,\ldots , \mathtt {not}\; b_m$ is a rule in P and for each $a_i \in body^+(r)$ there is an argument $A_i$ with $\mathtt {Conc}(A_i) = a_i$ and $r \notin \mathtt {Rules}(A_i)$ then

  $$c \leftarrow (A_1),\ldots ,(A_n),\mathtt {not}\;b_1,\ldots , \mathtt {not}\; b_m$$

  is an argument (say A) with $\mathtt {Conc}(A) = c$, $\mathtt {Rules}(A) = \bigcup \mathtt {Rules}(A_i) \cup \{ r \}$, $\mathtt {Vul}(A) = \bigcup \mathtt {Vul}(A_i)\ \cup$ $\{ b_1, \ldots ,$ $b_m \}$ and $\mathtt {Sub}(A) = \bigcup \mathtt {Sub}(A_i)\ \cup \{A\}$.

• For each different head(r) where $r \in P$, there is a default argument (say $\mathtt {not\ }A$) such that $\mathtt {Conc}(\mathtt {not\ }A) = \mathtt {not\ }head(r)$, $\mathtt {Rules}(\mathtt {not\ }A) = \emptyset$, $\mathtt {Vul}(\mathtt {not\ }A) = \{ head(r) \}$ and $\mathtt {Sub}(\mathtt {not\ }A) = \{\mathtt {not\ }A\}$.

Above, $\mathtt {Conc}(A)$, $\mathtt {Rules}(A)$, $\mathtt {Vul}(A)$ and $\mathtt {Sub}(A)$ respectively refer to what we call the conclusion, rules, vulnerabilities and subarguments of A. Our definition is very similar to the one in [5], which consists of only the first two bullet points above. The difference is the third bullet point, which is required to instantiate the default arguments.

Example 3

Based on the logic program P from Example 2 we can instantiate: $A_i = r_i$, $1 \le i \le 5$, based on the first bullet point of Definition 9; $A_6 = \mathtt {not\ }c$, $A_7 = \mathtt {not\ }a$, $A_8 = \mathtt {not\ }b$, $A_9 = \mathtt {not\ }g$, based on the third bullet point of Definition 9. No arguments are instantiated following the second bullet point because all $r \in P$ have $body^+(r) = \emptyset$. To exemplify the components of some of those arguments, $A_1$ has $\mathtt {Conc}(A_1) = c$, $\mathtt {Rules}(A_1) = \left\{ r_1\right\}$, $\mathtt {Vul}(A_1) = \left\{ c\right\}$ and $\mathtt {Sub}(A_1) = \left\{ A_1\right\}$. $A_6$ has $\mathtt {Conc}(A_6) = \mathtt {not\ }c$, $\mathtt {Rules}(A_6) = \emptyset$, $\mathtt {Vul}(A_6) = \{ c \}$ and $\mathtt {Sub}(A_6) = \{ A_6 \}$.

The next step is to determine the attack relation of the argumentation framework: an argument attacks another iff its conclusion is a vulnerability of the latter.

Definition 10

Let A and B be arguments⁴. We say A attacks B iff $\mathtt {Conc}(A) \in \mathtt {Vul}(B)$.

Example 4

The argument $A_1$ from Example 3 consists of $r: c \leftarrow \mathtt {not\ }c$ and has $\mathtt {Conc}(A_1) = c$ and $\mathtt {Vul}(A_1) = \left\{ c\right\}$; since $\mathtt {Conc}(A_1) \in \mathtt {Vul}(A_1)$, $A_1$ attacks itself. $A_6$, in comparison, attacks no arguments, but is also attacked by $A_1$.

Definition 11

The argumentation framework $\mathtt {AF}_P$ associated with a program P is $\mathtt {AF}_P = ( Ar _P, att _P)$, where $Ar _P$ is the set of all arguments from P (Definition 9) and $att _P = \left\{ (A,B) \in Ar \times Ar \ |\ \mathtt {Conc}(A) \in \mathtt {Vul}(B)\right\}$ (Definition 10).

Given $\mathtt {AF}_P$, the computation of $\mathtt {SINKS}_{\mathtt {AF}_{P}}$ retrieves its set of default arguments.

Example 5

Following the names of arguments used in Example 3, the $\mathtt {AF}_P$ corresponding to P from Example 2 is precisely the framework depicted in Example 1.

3.2 Step 2: Applying Argumentation Semantics

Once we have $\mathtt {AF}_P$, we will be interested in its semantics from the standpoint of abstract argumentation, which are given by Definition 3.

3.3 Step 3: Computing Conclusion Labellings

The goal of this step is to translate the 5-valued argument labellings obtained in the previous step to sets of conclusions comparable to the models of the original program, which are in turn 3-valued. For this reason, conclusions will be labeled exclusively within the elements of $\left\{ \mathtt {in}, \mathtt {out}, \mathtt {undec}\right\}$. In what follows, we will refer to the necessary sets of labels as $V_5 = \left\{ \mathtt {in}, \mathtt {out}, \mathtt {ido}, \mathtt {idk}, \mathtt {idc}\right\}$ and $V_3 = \left\{ \mathtt {in}, \mathtt {out}, \mathtt {undec}\right\}$.

Definition 12

Let P be a program. A conclusion labelling is a map $Cl : HB _P \rightarrow V_3$.

As in [5], we follow the approach of [15]: for each conclusion, we map the labels of arguments that yield it (taken from $V_5$) to a label in $V_3$. The label attributed to each $a \in HB _P$ is then the best one⁵ according to the total order $\mathtt {in}> \mathtt {undec}> \mathtt {out}$.

Definition 13

The mapping $\sigma : V_5 \rightarrow V_3$ is such that $\sigma (\mathtt {in}) = \mathtt {in}$, $\sigma (\mathtt {out}) = \sigma (\mathtt {ido}) = \mathtt {out}$, $\sigma (\mathtt {idk}) = \sigma (\mathtt {idc}) = \mathtt {undec}$.

Definition 14

Let $\mathtt {AF}_P = ( Ar _P, att _P)$ be the AF associated with a program P and $Al$ be an argument labelling of $\mathtt {AF}_P$. We say that $Cl$ is the associated conclusion labelling of $Al$ iff $Cl$ is a conclusion labelling such that for each $c \in HB _P$ it holds that $Cl (c) = max(\{ \sigma ( Al (A)) \mid \mathtt {Conc}(A) = c \} \cup \{ \mathtt {out}\})$ where $\mathtt {in}> \mathtt {undec}> \mathtt {out}$.

Given a conclusion labelling $Cl$, we write $\mathtt {in}( Cl )$ to denote $\{ c \mid Cl (c) = \mathtt {in}\}$, $\mathtt {out}( Cl )$ for $\{ c \mid Cl (c) = \mathtt {out}\}$ and $\mathtt {undec}( Cl )$ for $\{ c \mid Cl (c) = \mathtt {undec}\}$. Because a conclusion labelling defines a partition of $HB _P$ into sets of $\mathtt {in}/\mathtt {out}/\mathtt {undec}$-labelled conclusions, we may sometimes write $Cl$ as the triple $(\mathtt {in}( Cl ), \mathtt {out}( Cl ), \mathtt {undec}( Cl ))$.

Example 6

Recall the complete argument labellings of $\mathtt {AF}$ in Example 1 are: $Al _1 = (\left\{ \ \right\} , \left\{ \ \right\} , \left\{ \ \right\} , Ar , \left\{ \ \right\} )$, $Al _2 = (\left\{ A_2, A_8 \right\} , \left\{ A_3, A_7 \right\} , \left\{ A_4 \right\} , \left\{ A_1, A_5, A_6, A_9 \right\} , \left\{ \ \right\} )$, $Al _3 = (\left\{ A_3, A_7, A_9 \right\} , \left\{ A_2, A_5, A_8 \right\} , \left\{ \ \right\} , \left\{ A_1, A_4, A_6 \right\} , \left\{ \ \right\} )$. Furthermore, remember $\mathtt {Conc}(A_1) = \mathtt {Conc}(A_4) = c$ (Example 3). Observe that $Al _2(A_4) = \mathtt {ido}$ and $Al _2(A_1) = \mathtt {idk}$. Given that $\sigma (\mathtt {ido}) = \mathtt {out}$ and $\sigma (\mathtt {idk}) = \mathtt {undec}$, we will find $Cl _2(c) = \mathtt {undec}$ in the corresponding conclusion labelling $Cl _2$. Following Definition 14, we produce the conclusion labellings $Cl _1 = (\left\{ \right\} , \left\{ \right\} , \left\{ a,b,c,g\right\} )$, $Cl _2 = (\left\{ a\right\} , \left\{ b\right\} , \left\{ c,g\right\} )$, and $Cl _3 = (\left\{ b\right\} , \left\{ a,g\right\} , \left\{ c\right\} )$ respectively associated to $Al _1, Al _2, Al _3$. Please observe that $\langle \mathtt {in}( Cl _i), \mathtt {out}( Cl _i) \rangle$ ($1 \le i \le 3$) are precisely the p-stable models of P (Example 2).

4 Semantic Correspondences

In this section, we overview results concerning semantic relations between abstract argumentation and logic programming. We show that our approach based on 5-valued labellings preserves the original results and provides us a new correspondence.

First, we must formally define functions to map argument labellings to conclusion labellings and vice-versa. Our intention is to later prove they are each other’s inverse. The function $\mathtt {AL2CL}$ below simply follows Definition 14, while $\mathtt {CL2AL}$ is introduced anew. In the latter, we will find that an argument is $\mathtt {out}$ or $\mathtt {ido}$ in the resulting argument labelling if some of its vulnerabilities are $\mathtt {in}$ in the original conclusion labelling. Deciding if that argument is $\mathtt {out}$ or $\mathtt {ido}$ will depend solely on whether it attacks an $\mathtt {undec}$-labelled sink. The case for $\mathtt {idk}$ and $\mathtt {idc}$ arguments is similarly based on $\mathtt {undec}$ and the status of the sink arguments they attack.

Definition 15

Let P be a program and $\mathtt {AF}_P$ be its associated argumentation framework. Let $\mathcal {AL}$ be the set of all argument labellings of $\mathtt {AF}_P$ and let $\mathcal {CL}$ be the set of all conclusion labellings of $\mathtt {AF}_P$.

• We define a function $\mathtt {AL2CL}\!\!: \mathcal {AL}\rightarrow \mathcal {CL}$ such that for each $Al \in \mathcal {AL}$, $\mathtt {AL2CL}( Al )$ is the associated conclusion labelling of $Al$ (Definition 14).

• We define a function $\mathtt {CL2AL}: \mathcal {CL}\rightarrow \mathcal {AL}$ such that for each $Cl \in \mathcal {CL}$ and each $A \in Ar _P$ it holds that:

  • $\mathtt {CL2AL}( Cl )(A) = \mathtt {in}$ iff $\mathtt {Vul}(A) \subseteq \mathtt {out}( Cl )$

  • $\mathtt {CL2AL}( Cl )(A) = \mathtt {out}$ iff $\mathtt {Vul}(A) \cap \mathtt {in}( Cl ) \ne \emptyset$ and $\left\{ \mathtt {Conc}(B) \mid B \in \mathtt {SINKS}_{\mathtt {AF}_{P}}\ and\ (A,B) \in att \right\} \cap \mathtt {undec}( Cl ) = \emptyset$

  • $\mathtt {CL2AL}( Cl )(A) = \mathtt {ido}$ iff $\mathtt {Vul}(A) \cap \mathtt {in}( Cl ) \ne \emptyset$ and $\left\{ \mathtt {Conc}(B) \mid B \in \mathtt {SINKS}_{\mathtt {AF}_{P}}\ and\ (A,B) \in att \right\} \cap \mathtt {undec}( Cl ) \ne \emptyset$

  • $\mathtt {CL2AL}( Cl )(A) = \mathtt {idk}$ iff $\mathtt {Vul}(A) \cap \mathtt {in}( Cl ) = \emptyset$, while $\mathtt {Vul}(A) \setminus \mathtt {out}( Cl ) \ne \emptyset$ and ${ \mathtt {Conc}(B) \mid B \in \mathtt {SINKS}_{\mathtt {AF}_{P}}\ and\ (A,B) \in att } \subseteq \mathtt {undec}( Cl )$

  • $\mathtt {CL2AL}( Cl )(A) = \mathtt {idc}$ iff $\mathtt {Vul}(A) \cap \mathtt {in}( Cl ) = \emptyset$, while $\mathtt {Vul}(A) \setminus \mathtt {out}( Cl ) \ne \emptyset$ and $\left\{ \mathtt {Conc}(B) \mid B \in \mathtt {SINKS}_{\mathtt {AF}_{P}}\ and\ (A,B) \in att \right\} \setminus \mathtt {undec}( Cl ) \ne \emptyset$

Theorem 1

When restricted to complete argument labellings and complete conclusion labellings, the functions $\mathtt {AL2CL}$ and $\mathtt {CL2AL}$ are bijections and each other’s inverse.

We are now ready to present some key results of our work. In what follows, let P be a logic program and $\mathtt {AF}_P$ be its associated argumentation framework. Further, assume $Cl = (\mathtt {in}( Cl ), \mathtt {out}( Cl ), \mathtt {undec}( Cl ))$ is an arbitrary conclusion labelling of $\mathtt {AF}_P$. The results below are based on our $\sigma$-mapping from 5-valued labellings to the standard $\mathtt {in}/\mathtt {out}/\mathtt {undec}$-labellings from [2] and theorems from [5] connecting the standard labellings to logic programming models. In summary, the following theorems assure our 5-valued labellings preserve all the results from [5].

Theorem 2

Let $Al$ be a complete argument labelling of $\mathtt {AF}_P$. Then $\mathtt {AL2CL}( Al ) = Cl$ iff $\langle \mathtt {in}( Cl ), \mathtt {out}( Cl ) \rangle$ is a p-stable model of P.

As our definition of complete argument labelling corresponds to the definition of [2] and the characterization of $\mathtt {in}$ is equivalent in both settings, we can borrow the following result from [5]:

Lemma 1

Let P be a program and $\mathtt {AF}_P = ( Ar , att )$ be its associated argumentation framework. Let $Al _1$ and $Al _2$ be complete argument labellings of $\mathtt {AF}_P$, and $Cl _1 = \mathtt {AL2CL}( Al _1)$ and $Cl _2 = \mathtt {AL2CL}( Al _2)$. It holds that

• 1. $\mathtt {in}( Al _1) \subseteq \mathtt {in}( Al _2)$ iff $\mathtt {in}( Cl _1) \subseteq \mathtt {in}( Cl _2)$,

• 2. $\mathtt {in}( Al _1) = \mathtt {in}( Al _2)$ iff $\mathtt {in}( Cl _1) = \mathtt {in}( Cl _2)$, and

• 3. $\mathtt {in}( Al _1) \subsetneq \mathtt {in}( Al _2)$ iff $\mathtt {in}( Cl _1) \subsetneq \mathtt {in}( Cl _2)$.

From Theorem 2 and Lemma 1, we obtain:

Theorem 3

Let $Al$ be the grounded argument labelling of $\mathtt {AF}_P$. Then $\mathtt {AL2CL}( Al ) = Cl$ iff $\mathtt {in}( Cl )$ is the well-founded model of P.

Theorem 4

Let $Al$ be a preferred argument labelling of $\mathtt {AF}_P$. Then $\mathtt {AL2CL}( Al ) = Cl$ iff $\mathtt {in}( Cl )$ is a regular model of P.

In addition, we know $\mathtt {idk},\mathtt {idc}= \emptyset$ in a complete argument labelling $Al$ iff $\mathtt {undec}= \emptyset$ in $\mathtt {AL2CL}( Al ) = Cl$ (Definition 14). Thus,

Theorem 5

Let $Al$ be a stable argument labelling of $\mathtt {AF}_P$. Then $\mathtt {AL2CL}( Al ) = Cl$ iff $\mathtt {in}( Cl )$ is a stable model of P.

Following the queue of the theorems above, we can as well consider the conclusion labellings where $\mathtt {in}( Cl )$ is an L-stable model of P. The natural candidate argument labellings to correspond to those conclusion labellings would be the semi-stable argument labellings, since both semi-stable and L-stable semantics respectively minimize undecided arguments and undecided atoms. Unfortunately, in the same way as in [5], we find there are cases where the semi-stable semantics does not exactly correspond to the L-stable semantics. Our running example is enough to show that: as one can observe from the computed labellings in Example 6, the framework from Example 1 has two semi-stable argument labellings (hence two semi-stable conclusion labellings), namely $Al _2, Al _3$, but $Cl _3$ is the sole complete conclusion labelling for which $\mathtt {in}( Cl )$ is an L-stable model of P. In other words, P has a single L-stable model, but $\mathtt {AF}_P$ has two semi-stable argument labellings. Differently from previous works, however, our labellings isolated a possible culprit to that difference in Example 6, for we have $Al _2(A_4) = \mathtt {ido}$. But why may it be a culprit? Because if $A_4$ was instead labelled $\mathtt {idk}$ in $Al _2$, only $Al _3$ would be semi-stable, fixing the expected correspondence.

5 The L-Stable Semantics for Abstract Argumentation Frameworks

The discussion about the semi-stable and L-stable semantics by the end of Sect. 4 led us to the suggestion that changing the labels of some particular arguments could lead those semantics to coincide. Unfortunately, such changes are far from trivial, as changing the label of an argument is likely to affect the labels of others. Fortunatelly, there are other parts of the three-step procedure from Sect. 3 that can be easily adapted to achieve a similar result: the conception of a new abstract argumentation semantics that corresponds perfectly to the L-stable semantics from logic programming.

Definition 16

Let $\mathcal {AL}$ be the set of all complete argument labellings of $\mathtt {AF}$. Then $Al$ is a least-stable (or L-stable) argument labelling of $\mathtt {AF}$ if $Al \in \mathcal {AL}$ and $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {idk}( Al ') \cup \mathtt {ido}( Al ') \subsetneq \mathtt {idk}( Al ) \cup \mathtt {ido}( Al )$.

Lemma 2

Let $Al$ be a complete labelling of an argumentation framework and $Cl = \mathtt {AL2CL}( Al )$. Then $\exists A \in \mathtt {idk}( Al ) \cup \mathtt {ido}( Al )$ with $\mathtt {Conc}(A) = c$ iff $Cl (c) = \mathtt {undec}$.

Theorem 6

Let $Al$ be a least-stable argument labelling of $\mathtt {AF}_P$. Then $\mathtt {AL2CL}( Al ) = Cl$ iff $\mathtt {in}( Cl )$ is an L-stable model of P.

This correspondence ensures the L-stable semantic for argumentation frameworks has similar properties to the semi-stable semantics.

Corollary 1

Every AF has at least one L-stable labelling.

Corollary 2

If $Al$ is a stable labelling of $\mathtt {AF}_P$, then $Al$ is an L-stable labelling of $\mathtt {AF}_P$.

Corollary 3

If $\mathtt {AF}_P$ has at least one stable labelling, then $Al$ is an L-stable labelling of $\mathtt {AF}_P$ iff $Al$ is a semi-stable labelling of $\mathtt {AF}_P$ iff $Al$ is a stable labelling of $\mathtt {AF}_P$.

However, differently than semi-stable, the L-stable AA semantic captures the L-stable semantics for LP.

6 On the Role of Sink Arguments

We have affirmed sink arguments together with 5-valued labellings are able to isolate the possible culprits for the difference between the semi-stable and L-stable semantics. Now we resume this discussion to provide a more detailed account on the role played by sink arguments in argumentation semantics. In particular, we will emphasize the following two points:

• When considering only the sink arguments obtained in our translation (Definition 9), 3-valued labellings suffice to capture the equivalence between logic programming semantics and abstract argumentation semantics (including L-stable).

• The sink arguments together with the 5-valued labellings offer a more fine-grained view of the notion of undecidedness when compared with 3-valued labellings.

The sink arguments can be employed to obtain the conclusion labellings associated with complete argument labellings:

Theorem 7

Let P be a logic program, $\mathtt {AF}_P = ( Ar _P, att _P)$ be its associated argumentation framework and $Al$ be a complete 5-valued argument labelling of $\mathtt {AF}_P$. We define $Cl : HB _P \rightarrow V_3$:

$$ Cl (c) = \left\{ \begin{array}{ll} \overline{\sigma ( Al (A))} &{} \textit{if } \exists A \in Ar _P \textit{ such that } \mathtt {Conc}(A) = \mathtt {not\ }c \\ \mathtt {out}&{} \textit{ otherwise } \end{array} \right. $$

in which $\overline{\mathtt {in}} = \mathtt {out}$, $\overline{\mathtt {out}} = \mathtt {in}$ and $\overline{\mathtt {undec}} = \mathtt {undec}$. Then $\mathtt {AL2CL}( Al ) = Cl$ and $\langle \mathtt {in}( Cl ), \mathtt {out}( Cl ) \rangle$ is a p-stable model of P.

From Definition 9, there is at most one argument A in $\mathtt {AF}_P$ such that $\mathtt {Conc}(A) = \mathtt {not\ }c$ for each $c \in HB _P$. Therefore, the function $Cl$ above is well-defined.

Theorem 8

Let P be a program, $\mathtt {AF}_P = ( Ar _P, att _P)$ be its associated argumentation framework, $Al$ be a 5-valued argument labelling of $\mathtt {AF}_P$ and $\mathtt {AL3}( Al ) : \mathtt {SINKS}_{\mathtt {AF}_{P}} \rightarrow \left\{ \mathtt {in}, \mathtt {out}, \mathtt {undec}\right\}$, in which for every $A \in \mathtt {SINKS}_{\mathtt {AF}_{P}}$, we have $\mathtt {AL3}( Al )(A) = \sigma ( Al (A))$. Let also $\mathcal {AL}$ be the set of all complete argument labellings of $\mathtt {AF}_P$. Then

• $Al$ is the grounded argument labelling of $\mathtt {AF}_P$ iff $Al \in \mathcal {AL}$ and $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {out}(\mathtt {AL3}( Al ')) \subsetneq \mathtt {out}(\mathtt {AL3}( Al ))$.

• $Al$ is a preferred argument labelling of $\mathtt {AF}_P$ iff $Al \in \mathcal {AL}$ and $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {out}(\mathtt {AL3}( Al ')) \supsetneq \mathtt {out}(\mathtt {AL3}( Al ))$.

• $Al$ is a stable argument labelling of $\mathtt {AF}_P$ iff $Al \in \mathcal {AL}$ and $\mathtt {undec}(\mathtt {AL3}( Al )) = \emptyset$.

• $Al$ is an L-stable argument labelling of $\mathtt {AF}_P$ iff $Al \in \mathcal {AL}$ and $\not \exists Al ' \in \mathcal {AL}$ such that $\mathtt {undec}(\mathtt {AL3}( Al ')) \subsetneq \mathtt {undec}(\mathtt {AL3}( Al ))$.

Theorem 8 highlights a distinction between the semi-stable and L-stable semantics over an argumentation framework $\mathtt {AF}_P$ obtained from a logic program P: the semi-stable argument labellings of $\mathtt {AF}_P$ are those complete argument labellings with minimal set of $\mathtt {undec}$-labelled arguments, whereas the L-stable argument labellings of $\mathtt {AF}_P$ are those complete argument labellings with minimal set of $\mathtt {undec}$-labelled sinks. Therefore, the labels assigned to the sink arguments of $\mathtt {AF}_P$ suffice to know if a labelling is grounded, preferred, stable and L-stable, but they may not suffice to know if it is semi-stable. Revisiting Example 6, we have both $Al _2$ and $Al _3$ are complete labellings with minimal $\mathtt {undec}$ arguments (semi-stable, see Example 1); in contrast, $Al _3$ is the only complete labelling with minimal $\mathtt {undec}$ sinks (L-stable, see Example 2).

One may then wonder it the 5-valued labelling semantics we introduced in this paper are of some interest on their own. First, observe that the 5 labels are a necessary condition to define the L-stable argumentation semantics (complete labellings with minimal ($\mathtt {ido}\cup \mathtt {idk}$)-valued arguments). Further, although one can mimic the L-stable logic programming semantics with 3-valued labellings, it will work as expected just for argumentation frameworks obtained from logic programs through Definition 11; in an arbitrary argumentation framework (one that does not account for default arguments), unlike our definition of L-stable semantics based on 5 labels, this adaptation of the 3-valued approach to capture L-stable will not produce meaningful results.

Besides, we emphasize the role played by sink arguments in our 5-valued labellings: in an argumentation framework $\mathtt {AF}$ without sink arguments, its complete 3-valued labellings coincide precisely with its 5-valued counterpart by simply replacing $\mathtt {undec}$ for $\mathtt {idk}$ in the respective labellings. This means that the semi-stable and L-stable argumentation semantics collapse into each other for those frameworks! What is more, owing to the 5-valued labellings, we can define new semantics with interesting properties: for instance, consider a new argumentation semantics (let us call it “I-stable”) defined by the complete labellings with minimal $\mathtt {idk}$ arguments. In an argumentation framework without sink arguments, it will coincide with both semi-stable and L-stable argumentation semantics and yet it will possibly produce distinct results for some argumentation frameworks. As such, these semantics offer three different views of undecidedness in which the difference between them is positively determined by the sink arguments.

7 Conclusion

This work was largely motivated by the curious result of [5] stating the semi-stable semantics from abstract argumentation is not equivalent to the L-stable semantics from logic programming. Both semantics are based on the minimization of undecided arguments and atoms in their respective domains, share very similar properties, and yet are different. Our efforts to understand the differences between the semantics led us to consider the instantiation of special arguments in logic programming we called default arguments and the specialization of the standard 3-valued argument labellings from [2] into more expressive 5-valued partial labellings (as previously considered in [1]). To accomplish our goals, we considered the labels $\mathtt {in}, \mathtt {out}, \mathtt {ido}, \mathtt {idk}, \mathtt {idc}$ and introduced a corresponding definition of complete labellings revising the meanings of $\mathtt {out},\mathtt {idk},\mathtt {idc}$ and introducing the new label $\mathtt {ido}$, here dubbed “It doesn’t matter if it’s out”. Following the revised concepts, we showed our approach preserves well-known results in the semantic comparison of abstract argumentation and logic programming. While we did not try to resolve the semi-stable-L-stable equivalence problem, we shed light into it, as our 5-valued labellings can isolate the possible culprit arguments causing the differences based on the labels $\mathtt {ido},\mathtt {idc}$. Instead, we introduced a new semantics for abstract argumentation frameworks: the least-stable (or L-stable) semantics. What is more, we proved our newly established semantics to be equivalent to the logic programming L-stable semantics for normal programs and their corresponding instantiated argumentation frameworks. The non-equivalence result proved in [5] was based on a particular procedure for the instantiation of argumentation frameworks from logic programs. The 5-valued labellings, the sink arguments and our revision of their procedure are the key changes to obtain an argumentation-based semantics corresponding to L-stable. Indeed, we show that if we restrict our attention to sink arguments, the standard 3-valued labelling is enough to characterize the logic programming semantics, including L-stable.

It is worth noticing that partial labellings were also employed by [12] in an algorithm for enumerating preferred extensions of an argumentation framework. As we do, they also consider five labels, namely $\mathtt {in}, \mathtt {out}, \mathtt {undec}, \mathtt {blank},$ and $\mathtt {must}$-$\mathtt {out}$ labels. In their algorithm, all arguments of the framework are initially $\mathtt {blank}$ and $\mathtt {must}$-$\mathtt {out}$ is used at run time to flag arguments that are candidate to be labelled $\mathtt {out}$.

Natural ramifications of this work include an in-depth investigation of properties of the least-stable argumentation semantics. Our newly defined 5-valued complete labellings may also lead to the proposal of other interesting semantics as we try to maximize or minimize different combinations of the labels at our disposal. We also intend to investigate whether sink arguments play other relevant roles in the characterization or computation of argumentation semantics.