2 Preliminaries

2.1 SETAF

Nielsen and Parsons (Reference Nielsen and Parsons2006) proposed an extension of Dung’s (Reference Dung1995b) Abstract Argumentation Frameworks ( $\mathit{AAF}$ s) to allow joint attacks on arguments. The resulting framework, called $\textit{SETAF}$ , is defined next:

Definition 1 (SETAF (Nielsen and Parsons Reference Nielsen and Parsons2006)). A framework with sets of attacking arguments ( $\mathit{SETAF}$ for short) is a pair $\mathfrak{A} = (\mathcal{A}, \mathit{Att})$ , in which $\mathcal{A}$ is a finite set of arguments and $\mathit{Att} \subseteq ( 2^{\mathcal{A}} \setminus \left \{\emptyset \right \}) \times \mathcal{A}$ is an attack relation such that if $(\mathcal{B}, a) \in \mathit{Att}$ , there is no $\mathcal{B}' \subset \mathcal{B}$ such that $(\mathcal{B}', a) \in \mathit{Att}$ ; that is, $\mathcal{B}$ is a minimal set (w.r.t. $\subseteq$ ) attacking $a$ Footnote ¹. By $\mathit{Att}(a) = \left \{\mathcal{B} \subseteq \mathcal{A} \mid (\mathcal{B}, a) \in \mathit{Att}\right \}$ , we mean the set of attackers of $a$ .

In $\mathit{AAF}$ s, only individual arguments can attack arguments. In $\textit{SETAF}$ s, the novelty is that sets of two or more arguments can also attack arguments. This means that $\textit{SETAF}$ s $(\mathcal{A}, \mathit{Att})$ with $|\mathcal{B}| = 1$ for each $(\mathcal{B}, a) \in \mathit{Att}$ amount to (standard Dung) $\mathit{AAF}$ s.

The semantics for $\textit{SETAF}$ s are generalizations of the corresponding semantics for $\mathit{AAF}$ s (Nielsen and Parsons Reference Nielsen and Parsons2006) and can be defined equivalently in terms of extensions or labelings (Flouris and Bikakis Reference Flouris and Bikakis2019). Our focus here will be on their labeling-based semantics.

Definition 2 (Labelings (Flouris and Bikakis Reference Flouris and Bikakis2019)). Let $\mathfrak{A} = (\mathcal{A}, \mathit{Att})$ be a $\mathit{SETAF}$ . A labeling is a function $\mathcal{L} : \mathcal{A} \to \left \{\mathtt{in}, \mathtt{out}, \mathtt{undec}\right \}$ . It is admissible iff for each $a \in \mathcal{A}$ ,

• • If $\mathcal{L}(a) = \mathtt{in}$ , then for each $\mathcal{B} \in \mathit{Att}(a)$ , it holds $\mathcal{L}(b) = \mathtt{out}$ for some $b \in \mathcal{B}$ .

• • If $\mathcal{L}(a) = \mathtt{out}$ , then there exists $\mathcal{B} \in \mathit{Att}(a)$ such that $\mathcal{L}(b) = \mathtt{in}$ for each $b \in \mathcal{B}$ .

A labeling $\mathcal{L}$ is called complete iff it is admissible and for each $a \in \mathcal{A}$ ,

• • If $\mathcal{L}(a) = \mathtt{undec}$ , then there exists $\mathcal{B} \in \mathit{Att}(a)$ such that $\mathcal{L}(b) \neq \mathtt{out}$ for each $b \in \mathcal{B}$ , and for each $\mathcal{B} \in \mathit{Att}(a)$ , it holds $\mathcal{L}(b) \neq \mathtt{in}$ for some $b \in \mathcal{B}$ .

We write $\mathtt{in}(\mathcal{L})$ for $\left \{a \in \mathcal{A} \mid \mathcal{L}(a) = \mathtt{in}\right \}$ , $\mathtt{out}(\mathcal{L})$ for $\{a \in \mathcal{A} \mid$ $\mathcal{L}(a) = \mathtt{out} \}$ , and $\mathtt{undec}(\mathcal{L})$ for $\left \{a \in \mathcal{A} \mid \mathcal{L}(a) = \mathtt{undec}\right \}$ . As a labeling essentially defines a partition among the arguments, we sometimes write $\mathcal{L}$ as a triple $(\mathtt{in}(\mathcal{L}), \mathtt{out}(\mathcal{L}), \mathtt{undec}(\mathcal{L}))$ . Intuitively, an argument labeled $\mathtt{in}$ represents explicit acceptance; an argument labeled $\mathtt{out}$ indicates rejection; and one labeled $\mathtt{undec}$ is undecided; that is, it is neither accepted nor rejected. We can now describe the $\textit{SETAF}$ semantics studied in this paper:

Definition 3 (Semantics (Flouris and Bikakis Reference Flouris and Bikakis2019)). Let $\mathfrak{A} = (\mathcal{A}, \mathit{Att})$ be a $\mathit{SETAF}$ . A complete labeling $\mathcal{L}$ is called

• • grounded iff $\mathtt{in}(\mathcal{L})$ is minimal (w.r.t. $\subseteq$ ) among all complete labelings of $\mathfrak{A}$ .

• • preferred iff $\mathtt{in}(\mathcal{L})$ is maximal (w.r.t. $\subseteq$ ) among all complete labelings of $\mathfrak{A}$ .

• • stable iff $\mathtt{undec}(\mathcal{L}) = \emptyset$ .

• • semi-stable iff $\mathtt{undec}(\mathcal{L})$ is minimal (w.r.t. $\subseteq$ ) among all complete labelings of $\mathfrak{A}$ .

Let us consider the following example:

Example 1. Consider the $\textit{SETAF}\ \mathfrak{A} = (\mathcal{A},\mathit{Att})$ below:

Fig. 1. A $\textit{SETAF}$ $\mathfrak{A}$ .

Concerning the semantics of $\mathfrak{A}$ , we have

• • Complete labelings: $\mathcal{L}_1 = (\emptyset, \emptyset, \left \{a,b,c,d,e\right \})$ , $\mathcal{L}_2 =$ $(\left \{a\right \}, \left \{b\right \}, \left \{c,d,e\right \})$ and $\mathcal{L}_3 = (\left \{b\right \}, \left \{a,e\right \}, \left \{c,d\right \})$ ;

• • Grounded labelings: $\mathcal{L}_1 = (\emptyset, \emptyset, \left \{a,b,c,d,e\right \})$ ;

• • Preferred labelings: $\mathcal{L}_2 =$ $(\left \{a\right \}, \left \{b\right \}, \left \{c,d,e\right \})$ and $\mathcal{L}_3 = (\left \{b\right \}, \left \{a,e\right \}, \left \{c,d\right \})$ ;

• • Stable labelings: none;

• • Semi-stable labelings: $\mathcal{L}_3 = (\left \{b\right \}, \left \{a,e\right \}, \left \{c,d\right \})$ .

2.2 Logic programs and semantics

Now, we take a look at propositional Normal Logic Programs. To delve into their definition and semantics, we will follow the presentation outlined by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b), which draws from the foundation laid out by Przymusinski (Reference Przymusinski1990).

Definition 4 (Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b).) A rule $r$ is an expression

(1) \begin{align} r: c \leftarrow a_1, \ldots, a_m, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \end{align}

where ( $m, n \geq 0$ ); $c$ , each $a_i$ ( $1 \leq i \leq m$ ) and each $b_j$ ( $1 \leq j \leq n$ ) 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 as ${\mathit{head}}(r)$ , and $\mathit{body}(r) = \left \{a_1, \ldots, a_m, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n\right \}$ is called the body of $r$ . Further, we divide $\mathit{body}(r)$ into two sets $\mathit{body}^+(r) = \left \{a_1, \ldots, a_m\right \}$ and $\mathit{body}^-(r) = \left \{\mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n\right \}$ . A fact is a rule where $m = n = 0$ . A Normal Logic Program ( $\mathit{NLP}$ ) or simply a program $P$ is a finite set of rules. If every $r \in P$ has $body^{-}(r) = \emptyset$ , $P$ is a positive program. The Herbrand Base of $P$ is the set ${\mathit{HB}}_{P}$ of all atoms appearing in $P$ .

A wide range of $\textit{NLP}$ semantics are based on the three-valued interpretations of programs (Przymusinski Reference Przymusinski1990):

Definition 5 (Three-Valued Herbrand Interpretation (Przymusinski Reference Przymusinski1990)). A three-valued Herbrand Interpretation $\mathcal{I}$ (or simply interpretation) of an NLP $P$ is a pair $\left\langle T, F \right \rangle$ with $T, F \subseteq{\mathit{HB}}_P$ and $T \cap F = \emptyset$ . The atoms in $T$ are true in $\mathcal{I}$ , the atoms in $F$ are false in $\mathcal{I}$ , and the atoms in ${\mathit{HB}}_P \setminus (T \cup F)$ are undefined in $\mathcal{I}$ . For convenience, when the NLP $P$ is clear from the context, we will refer to the set of undefined atoms in ${\mathit{HB}}_P \setminus (T \cup F)$ simply as $\overline{T \cup F}$ .

Now we will consider the main semantics for $\textit{NLP}$ s. Let $\mathcal{I} = \left\langle T, F \right \rangle$ be a three-valued Herbrand interpretation of an $\textit{NLP}$ $P$ ; the reduct of $P$ with respect to $\mathcal{I}$ (written as $P/\mathcal{I}$ ) is the $\textit{NLP}$ constructed using the following steps:

1. 1. Remove any $a \leftarrow a_1, \ldots, a_m,$ $\mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \in P$ such that $b_j \in T$ for some $j$ ( $1 \leq j \leq n$ );

2. 2. Afterward, remove any occurrence of $\mathtt{not\ } b_j$ from $P$ such that $b_j \in F$ ;

3. 3. Then, replace any occurrence of $\mathtt{not\ } b_j$ left by a special atom $\mathbf{u}$ ( $\mathbf{u} \not \in{\mathit{HB}}_P$ ).

In the above procedure, $\mathbf{u}$ is assumed to be an atom not in ${\mathit{HB}}_{P}$ which is undefined in all interpretations of $P$ (a constant). Note that $P/\mathcal{I}$ is a positive program since all negative literals have been removed. As a consequence, $P/\mathcal{I}$ has a unique least three-valued model (Przymusinski Reference Przymusinski1990), obtained by the $\Psi$ operator:

Definition 6 ( $\Psi$ Operator (Przymusinski Reference Przymusinski1990)). Let $P$ be a positive program and $\mathcal{J} = \left\langle T, F \right \rangle$ be an interpretation. Define $\Psi _P(\mathcal{J}) = \left\langle T', F' \right \rangle$ , where

• • $c \in T'$ iff $c \in HB_P$ and there exists $c \leftarrow a_1, \ldots, a_m \in P$ such that for all $i$ , $1 \leq i \leq m$ , $a_i \in T$ ;

• • $c \in F'$ iff $c \in HB_P$ and for every $c \leftarrow a_1, \ldots, a_m \in P$ , there exists $i$ , $1 \leq i \leq m$ , such that $a_i \in F$ .

The least three-valued model of $P$ is given by $ \Psi ^{\uparrow \ \omega }_P$ (Przymusinski Reference Przymusinski1990), the least fixed point of $\Psi _P$ iteratively obtained as follows:

\begin{align*} \Psi ^{\uparrow \ 0}_P = & \left\langle \emptyset, {\mathit{HB}}_P \right \rangle \\[5pt] \Psi ^{\uparrow \ i + 1}_P = & \Psi _P(\Psi ^{\uparrow \ i}_P)\\[5pt] \Psi ^{\uparrow \ \omega }_P = & \left\langle \bigcup _{i \lt \omega } \left \{T_i \mid \Psi ^{\uparrow \ i}_P = \left\langle T_i, F_i \right \rangle \right \}, \bigcap _{i \lt \omega } \left \{F_i \mid \Psi ^{\uparrow \ i}_P = \left\langle T_i, F_i \right \rangle \right \} \right \rangle \end{align*}

where $\omega$ denotes the first infinite ordinal.

We can now describe the logic programming semantics studied in this paper:

Definition 7. Let $P$ be an $NLP$ and $\mathcal{I} = \left\langle T, F \right \rangle$ be an interpretation; by $\Omega _P(\mathcal{I}) = \Psi ^{\uparrow \ \omega }_{\frac{P}{\mathcal{I}}}$ , we mean the least three-valued model of $\frac{P}{\mathcal{I}}$ . We say that

• • $\mathcal{I}$ is a partial stable model of $P$ iff $\Omega _P(\mathcal{I}) = \mathcal{I}$ (Przymusinski Reference Przymusinski1990).

• • $\mathcal{I}$ is a well-founded model of $P$ iff $\mathcal{I}$ is a partial stable model of $P$ where there is no partial stable model $\mathcal{I} ' = \left\langle T', F' \right \rangle$ of $P$ such that $T' \subset T$ ; that is, $T$ is minimal (w.r.t. set inclusion) among all partial stable models of $P$ (Przymusinski Reference Przymusinski1990).

• • $\mathcal{I}$ is a regular model of $P$ iff $\mathcal{I}$ is a partial stable model of $P$ where there is no partial stable model $\mathcal{I} ' = \left\langle T', F' \right \rangle$ of $P$ such that $T \subset T'$ ; that is, $T$ is maximal (w.r.t. set inclusion) among all partial stable models of $P$ (Eiter et al. Reference Eiter, Leone and Saccá1997).

• • $\mathcal{I}$ is a (two-valued) stable model of $P$ iff $\mathcal{I}$ is a partial stable model of $P$ where $T \cup F ={\mathit{HB}}_P$ (Przymusinski Reference Przymusinski1990).

• • $\mathcal{I}$ is an $L$ -stable model of $P$ iff $\mathcal{I}$ is a partial stable model of $P$ where there is no partial stable model $\mathcal{I} ' = \left\langle T', F' \right \rangle$ of $P$ such that $T \cup F \subset T' \cup F'$ ; that is, $T \cup F$ is maximal (w.r.t. set inclusion) among all partial stable models of $P$ (Eiter et al. Reference Eiter, Leone and Saccá1997).

Although some of these definitions are not standard in logic programming literature, their equivalence was proved by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b). This format helps us to relate $\textit{NLP}$ and $\textit{SETAF}$ semantics due to the structural similarities between Definition7 and Definitions2 and 3. We illustrate these semantics in the following example:

Example 2. Consider the following logic program $P$ :

\begin{equation*} \begin {array}{llcllcll} r_1: & a \leftarrow \mathtt {not}\; b & & r_2: & b \leftarrow \mathtt {not}\; a & & r_3: & c \leftarrow \mathtt {not}\; a, \mathtt {not}\; c\\[5pt] r_4: & c \leftarrow \mathtt {not}\; c, \mathtt {not}\; d & & r_5: & d \leftarrow \mathtt {not}\; d & & r_6: & e \leftarrow \mathtt {not}\; b, \mathtt {not}\; e \end {array} \end{equation*}

This program has

• • Partial Stable Models: $\mathcal{M}_1 = \langle \emptyset, \emptyset \rangle$ , $\mathcal{M}_2 = \langle \left \{ a \right \}, \left \{ b \right \} \rangle$ and $\mathcal{M}_3 = \langle \left \{ b \right \}, \left \{ a, e \right \} \rangle$ ;

• • Well-founded model: $\mathcal{M}_1 = \langle \emptyset, \emptyset \rangle$ ;

• • Regular models: $\mathcal{M}_2 = \langle \left \{ a \right \}, \left \{ b \right \} \rangle$ and $\mathcal{M}_3 = \langle \left \{ b \right \}, \left \{ a, e \right \} \rangle$ ;

• • Stable models: none;

• • $L$ -stable model: $\mathcal{M}_3 = \langle \left \{ b \right \}, \left \{ a, e \right \} \rangle$ .

3. From $\textit{NLP}$ to $\textit{SETAF}$

In this section, we revisit the three-step process of argumentation framework instantiation as employed by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b) for translating an $\textit{NLP}$ into an $\mathit{AAF}$ . This method is based on the approach introduced by Wu et al. (Reference Wu, Caminada and Gabbay2009) and shares similarities with the procedures used in ASPIC (Caminada and Amgoud Reference Caminada and Amgoud2005, Reference Caminada and Amgoud2007) and logic-based argumentation (Gorogiannis and Hunter Reference Gorogiannis and Hunter2011). Its first step involves taking an $\textit{NLP}$ and constructing its associated $\mathit{AAF}$ . Then, we apply $\mathit{AAF}$ semantics in the second step, followed by an analysis of the implications of these semantics at the level of conclusions (step 3). In our case, starting with an $\textit{NLP}$ $P$ , we derive the associated $\textit{SETAF}$ $(\mathcal{A}_P, \mathit{Att}_P)$ . Unlike the construction described by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b), rules with identical conclusions in $P$ will result in a single argument in $\mathcal{A}_P$ . This distinction is capital for establishing the equivalence results between $\textit{NLP}$ s and $\textit{SETAF}$ s. Additionally, it simplifies steps 2 and 3, making them more straightforward to follow. We now detail this process.

3.1 $\textit{SETAF}$ construction

We will devise one translation from $\textit{NLP}$ to $\textit{SETAF}$ that is sufficiently robust to guarantee the equivalence between various kinds of $\textit{NLP}$ s models and $\textit{SETAF}$ s labelings. Specifically, our approach will establish the correspondence between partial stable models and complete labelings, well-founded models and grounded labelings, regular models and preferred labelings, stable models and stable labelings, $L$ -stable models and semi-stable labelings. Our method is built upon a translation from $\textit{NLP}$ to $\mathit{AAF}$ proposed by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b), where $\textit{NLP}$ rules are directly translated into arguments. We will adapt this approach for $\textit{SETAF}$ by employing the translation method outlined by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b) to construct statements, and then statements corresponding to rules with the same head will be grouped to form a single argument. Taking an $\textit{NLP}$ $P$ , we can start to construct statements recursively as follows:

Definition 8 (Statements and Arguments). Let $P$ be an $NLP$ .

• • If $c \leftarrow \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n$ is a rule in $P$ , then it is also a statement (say $s$ ) with

1. — $\mathtt{Conc}(s) = c$ ,

2. — $\mathtt{Rules}(s) = \{ c \leftarrow \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \}$ ,

3. — $\mathtt{Vul}(s) = \{ b_1, \ldots, b_n \}$ , and

4. — ${\mathtt{Sub}}(s) = \{ s \}$ .

• • If $c \leftarrow a_1,\ldots, a_m, \mathtt{not\ } b_1,\ldots, \mathtt{not\ } b_n$ is a rule in $P$ and for each $a_i$ ( $1 \leq i \leq m$ ) there exists a statement $s_i$ with $\mathtt{Conc}(s_i) = a_i$ and $c \leftarrow a_1,\ldots, a_m, \mathtt{not\ } b_1,\ldots, \mathtt{not\ } b_n$ is not contained in $\mathtt{Rules}(s_i)$ , then $c \leftarrow (s_1),\ldots, (s_m),$ $\mathtt{not\ } b_1,\ldots, \mathtt{not\ } b_n$ is a statement (say $s$ ) with

1. — $\mathtt{Conc}(s) = c$ ,

2. — $\mathtt{Rules}(s) = \mathtt{Rules}(s_1) \cup \ldots \cup \mathtt{Rules}(s_m)\cup$ $ \{ c \leftarrow a_1,\ldots, a_m, \mathtt{not\ } b_1,\ldots, \mathtt{not\ } b_n \}$

3. — $\mathtt{Vul}(s) = \mathtt{Vul}(s_1)$ $\cup \ldots \cup$ $\mathtt{Vul}(s_m)$ $\cup$ $\{b_1, \ldots, b_n \}$ , and

4. — ${\mathtt{Sub}}(s) = \{ s \} \cup{\mathtt{Sub}}(s_1) \cup \ldots \cup{\mathtt{Sub}}(s_m)$ .

By $\mathfrak S_P$ , we mean the set of all statements we can construct from $P$ as above. Then we define $\mathcal{A}_P = \left \{\mathtt{Conc}(s) \mid s \in \mathfrak S_P\right \}$ as the set of all arguments we can construct from $P$ . For an argument $c$ from $P$ ( $c \in \mathcal{A}_P$ ), we have that

• • $\mathtt{Conc}(c) = c$ , and

• • $\mathtt{Vul}_P(c) = \left \{\mathtt{Vul}(s) \mid s \in \mathfrak S_P \textit{ and } \mathtt{Conc}(s) = c\right \}$ .

If $c$ is an argument, then $\mathtt{Conc}(c)$ is referred to as the conclusion of $c$ , and $\mathtt{Vul}_P(c)$ is referred to as the vulnerabilities of $c$ in $P$ . When the context is clear, we will write simply $\mathtt{Vul}(c)$ instead of $\mathtt{Vul}_P(c)$ .

Now we will clarify the connection between the existence of statements and the existence of a derivation in a reduct.

Lemma 1. Let $P$ be an $\textit{NLP}$ , $\mathcal{I} = \left\langle T, F \right \rangle$ an interpretation and $\Omega _P(\mathcal{I}) = \left\langle T', F' \right \rangle$ the least three-valued model of $\frac{P}{\mathcal{I}}$ . It holds

1. (i) $c \in T'$ iff there exists a statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ and $\mathtt{Vul}(s) \subseteq F$ .

2. (ii) $c \in F'$ iff for every statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ , we have $\mathtt{Vul}(s) \cap T \neq \emptyset$

We can prove both results in Lemma1 by induction. Assuming that $\Psi ^{\uparrow \ i}_{\frac{P}{\mathcal{I}}} = \left\langle T_i, F_i \right \rangle$ for each $i \in \mathbb{N}$ , we can prove the right-hand side of item 1 and the left-hand side of item 2 by induction on the value of $i$ after guaranteeing the following results:

• • If $c \in T_i$ , then there exists a statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ and $\mathtt{Vul}(s) \subseteq F$ .

• • If $c \not \in F_i$ , then there exists a statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ and $\mathtt{Vul}(s) \cap T = \emptyset$ .

The remaining cases of Lemma1 can be proved by structural induction on the construction of a statement $s$ (see a detailed account of the proof of Lemma 1 in Supplementary Material).

Lemma1 ensures that statements are closely related to derivations in a reduct. An atom $c$ is true in the least three-valued model of $\frac{P}{\mathcal{I}}$ iff we can construct a statement with conclusion $c$ and whose vulnerabilities are false according to $\mathcal{I}$ ; otherwise, $c$ is false in the least three-valued model of $\frac{P}{\mathcal{I}}$ iff for every statement whose conclusion is $c$ , at least one of its vulnerabilities is true in $\mathcal{I}$ . The next result is a direct consequence of Lemma1:

Corollary 2. Let $P$ be an $\textit{NLP}$ .

• • Assume $\mathcal{I} = \left\langle \emptyset, {\mathit{HB}}_P \right \rangle$ and $\Omega _P(\mathcal{I}) = \left\langle T', F' \right \rangle$ . It holds that $c \in T'$ iff there exists a statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ .

• • There is no statement $s$ constructed from $P$ such that $\mathtt{Conc}(s) = c$ iff $c \in F'$ for every interpretation $\mathcal{I}$ with $\Omega _P(\mathcal{I}) = \left\langle T', F' \right \rangle$ .

The reduct of $P$ with respect to $\left\langle \emptyset, {\mathit{HB}}_P \right \rangle$ gives us all the possible derivations of $P$ , and from these derivations, we can construct all the statements associated with $P$ . On the other hand, the atoms that are lost in the translation, that is, the atoms not associated with statements, are simply those that are false in the least three-valued model of every possible reduct of $P$ . Besides establishing connections between statements and derivations in a reduct, Lemma1 also plays a central role in the proof of Theorems4 and 5.

Apart from that, intuitively, we can see a statement as a tree-like structure representing a possible derivation of an atom from the rules of a program. In contrast, an argument for $c$ in $P$ is associated with the (derivable) atom $c$ itself and can be obtained by collecting all the statements with the same conclusion $c$ (i.e., all the possible ways of deriving $c$ in $P$ ).

Example 3. Consider the $\textit{NLP}$ $P$ below with rules $\left \{r_1, \ldots, r_8\right \}$ :

\begin{equation*} \begin {array}{llcllcll} r_1: & a & & r_2: & b \leftarrow a & & r_3: & c \leftarrow \mathtt {not}\; c \\[5pt] r_4: & d \leftarrow b, \mathtt {not}\; a, \mathtt {not}\; d & & r_5: & d \leftarrow \mathtt {not}\; c, \mathtt {not}\; d & & r_6: & e \leftarrow b, c, \mathtt {not}\; e \\[5pt] r_7: & c \leftarrow f, \mathtt {not}\; g & & r_8: & f \leftarrow c, g & & \ & \ \end {array} \end{equation*}

According to Definition 8, we can construct the following statements from $P$ :

\begin{equation*} \begin {array}{llcllcll} s_1: & a & & s_2: & b \leftarrow (s_1) & & s_3: & c \leftarrow \mathtt {not}\; c\\[5pt] s_4: & d \leftarrow (s_2), \mathtt {not}\; a, \mathtt {not}\; d & & s_5: & d \leftarrow \mathtt {not}\; c, \mathtt {not}\; d & & s_6: & e \leftarrow (s_2), (s_3),\mathtt {not}\; e \end {array} \end{equation*}

In the next table, we give the conclusions and vulnerabilities of each statement:

Alternatively, we can depict statements as possible derivations as in Figure 2:

Fig. 2. Statements constructed from $P$ .

The vulnerabilities of a statement $s$ are associated with the negative literals found in the derivation of $s$ . If $\mathtt{not}\; a$ is one of them, we know that $a$ is one of its vulnerabilities. This means that if $a$ is derived, then $\mathtt{Conc}(s)$ cannot be obtained via this derivation represented by $s$ . However, it can still be obtained via other derivations/statements. For instance, in the program $P$ of Example 3, the derivation of $a$ suffices to prevent the derivation of $d$ via statement $s_4$ (for that reason, $a \in \mathtt{Vul}(s_4)$ ), but we still can derive $d$ via $s_5$ . Notice also that there are no statements with conclusions $f$ and $g$ . From Corollary 2, we know that it is not possible to derive them in $P$ as they are false in the least three-valued model of each reduct of $P$ . In addition, to determine the vulnerabilities of an atom (and not only of a specific derivation leading to this atom), we collect these data about the statements with the same conclusions to give the conclusions and vulnerabilities of each argument. In our example, we obtain the following results:

As the vulnerabilities of an atom/argument $a$ are a collection of the vulnerabilities of the statements whose conclusion is $a$ , any set containing at least one atom in each of these statements suffices to prevent the derivation of $a$ in $P$ . In our example, there are two statements with the same conclusion $d$ and $\mathtt{Vul}(d) = \left \{\left \{a, d\right \}, \left \{c, d\right \}\right \}$ . Thus any set of atoms containing $\left \{d\right \}$ or $\left \{a, c\right \}$ prevents the conclusion of $d$ in $P$ . We will resort to these minimal sets to determine the attack relation:

Definition 9. Let $P$ be an $NLP$ and let $\mathcal{B}$ and $a$ be, respectively, a set of arguments and an argument in the sense of Definition 8. We say that $(\mathcal{B}, a) \in \mathit{Att}_P$ iff $\mathcal{B}$ is a minimal set (w.r.t. set inclusion) such that for each $V \in \mathtt{Vul}_P(a)$ , there exists $b \in \mathcal{B} \cap V$ .

For the arguments of Example3, it holds that both $a$ and $b$ are not attacked, $c$ attacks itself, $c$ attacks $e$ , $e$ attacks itself, $d$ attacks itself, $a$ and $c$ (collectively) attack $d$ . This strategy of extracting statements from $\textit{NLP}$ s rules and then gathering those with identical conclusions into arguments is not novel; Alcântara et al. (Reference Alcântara, Sá and Acosta-Guadarrama2019) proposed a translation from $\textit{NLP}$ s into Abstract Dialectical Frameworks (Brewka and Woltran Reference Brewka and Woltran2010; Brewka et al. Reference Brewka, Ellmauthaler, Strass, Wallner and Woltran2013) by following a similar path. Using the thus-defined notions of arguments and attacks, we define the $\textit{SETAF}$ associated with an $\textit{NLP}$ .

Definition 10. Let $P$ be an $NLP$ . We define its associated $SETAF$ as $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ , where $\mathcal{A}_P$ is the set of arguments in the sense of Definition 8 and $\mathit{Att}_P$ is the attack relation in the sense of Definition 9.

As an example, the $\textit{SETAF}$ $\mathfrak{A}_P = (\mathcal{A}_P,\mathit{Att}_P)$ associated with the $\textit{NLP}$ of Example3 is depicted in Figure 3 .

Fig. 3. A $\textit{SETAF}$ $\mathfrak{A}_P = (\mathcal{A}_P,\mathit{Att}_P)$ .

3.2 Equivalence results

Once the $\textit{SETAF}$ has been constructed, we show the equivalence between the semantics for an $\textit{NLP}$ $P$ and their counterpart for the associated $\textit{SETAF}$ $\mathfrak{A}_P$ . One distinguishing characteristic of our approach in comparison with König et al.’s (Reference König, Rapberger and Ulbricht2022) proposal is that it is more organic. We prove the equivalence results by identifying connections between fundamental notions used in the definition of the semantics for $\textit{NLP}$ s and $\textit{SETAF}$ s. With this purpose, we introduce two functions: $\mathcal{L}2\mathcal{I}_P$ associates an interpretation to each labeling while $\mathcal{I}2\mathcal{L}_P$ associates a labeling to each interpretation. We then investigate the conditions under which they are each other’s inverse and employ these results to prove the equivalence between the semantics. These functions essentially permit us to treat interpretations and labelings interchangeably.

Definition 11 ( $\mathcal{L}2\mathcal{I}_P$ and $\mathcal{I}2\mathcal{L}_P$ Functions). Let $P$ be an $NLP$ , $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be its associated $SETAF$ , $\mathcal{I}\mathit{nt}$ be the set of all the three-valued interpretations of $P$ and $\mathcal{L}\mathit{ab}$ be the set of all labelings of $\mathfrak{A}_p$ . We introduce a function $\mathcal{L}2\mathcal{I}_P : \mathcal{L}\mathit{ab} \to \mathcal{I}\mathit{nt}$ such that $\mathcal{L}2\mathcal{I}_P(\mathcal{L}) = \left\langle T, F \right \rangle$ , in which

• • $T = \left \{c \in{\mathit{HB}}_P \mid c \in \mathcal{A}_P \textit{ and } \mathcal{L}(c) = \mathtt{in}\right \}$ ;

• • $F = \{c \in{\mathit{HB}}_P \mid c \not \in \mathcal{A}_P \textit{ or } c \in \mathcal{A}_P \textit{ and } \mathcal{L}(c) = \mathtt{out} \}$ ;

• • $\overline{T \cup F} = \left \{c \in{\mathit{HB}}_P \mid c \in \mathcal{A}_P \textit{ and } \mathcal{L}(c) = \mathtt{undec}\right \}$ .

We introduce a function $\mathcal{I}2\mathcal{L}_P : \mathcal{I}\mathit{nt} \to \mathcal{L}\mathit{ab}$ such that for any $\mathcal{I} = \left\langle T, F \right \rangle \in \mathcal{I}\mathit{nt}$ and any $c \in \mathcal{A}_P$ ,

• • $\mathcal{I}2\mathcal{L}_P(\mathcal{I})(c) = \mathtt{in}$ if $c\in T$ ;

• • $\mathcal{I}2\mathcal{L}_P(\mathcal{I})(c) = \mathtt{out}$ if $c \in F$ ;

• • $\mathcal{I}2\mathcal{L}_P(\mathcal{I})(c) = \mathtt{undec}$ if $c \not \in T \cup F$ .

$\mathcal{I}2\mathcal{L}_P(\mathcal{I})(c)$ is not defined if $c \not \in \mathcal{A}_P$ .

The correspondence between labelings and interpretations is clear for those atoms $c \in{\mathit{HB}}_P$ in which $c \in \mathcal{A}_P$ . In this case, we have that $c$ is interpreted as true iff $c$ is labeled as $\mathtt{in}$ ; $c$ is interpreted as false iff $c$ is labeled as $\mathtt{out}$ . In contradistinction, those atoms $c \in{\mathit{HB}}_P$ not associated with arguments ( $c \not \in \mathcal{A}_P$ ) are simply interpreted as false. This will suffice to guarantee our results; next theorem assures us that $\mathcal{I}2\mathcal{L}_P(\mathcal{L}2\mathcal{I}_P(\mathcal{L})) = \mathcal{L}$ :

Theorem 3. Let $P$ be an $\textit{NLP}$ and $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be the associated $\textit{SETAF}$ . For any labeling $\mathcal{L}$ of $\mathfrak{A}_P$ , it holds $\mathcal{I}2\mathcal{L}_P(\mathcal{L}2\mathcal{I}_P(\mathcal{L})) = \mathcal{L}$ .

In general, $\mathcal{L}2\mathcal{I}_P(\mathcal{I}2\mathcal{L}_P(\mathcal{I}))$ is not equal to $\mathcal{I}$ , because of those atoms $c$ occurring in an $\textit{NLP}$ $P$ , but not in $\mathcal{A}_P$ . However, when $\mathcal{M}$ is a partial stable model, $\mathcal{L}2\mathcal{I}_P(\mathcal{I}2\mathcal{L}_P(\mathcal{M})) = \mathcal{M}$ :

Theorem 4. Let $P$ be an $\textit{NLP}$ , $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be the associated $\textit{SETAF}$ and $\mathcal{M} = \left\langle T, F \right \rangle$ be a partial stable model of $P$ . It holds that $\mathcal{L}2\mathcal{I}_P(\mathcal{I}2\mathcal{L}_P(\mathcal{M})) = \mathcal{M}$ .

This means that when restricted to partial stable models and complete labelings, $\mathcal{L}2\mathcal{I}_P$ and $\mathcal{I}2\mathcal{L}_P$ are each other’s inverse. From Lemma1, and Theorems3 and 4, we can obtain the following result:

Theorem 5. Let $P$ be an $\textit{NLP}$ and $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be the associated $\textit{SETAF}$ . It holds

• • $\mathcal{L}$ is a complete labeling of $\mathfrak{A}_P$ iff $\mathcal{L}2\mathcal{I}_P(\mathcal{L})$ is a partial stable model of $P$ .

• • $\mathcal{M}$ is a partial stable model of $P$ iff $\mathcal{I}2\mathcal{L}_P(\mathcal{M})$ is a complete labeling of $\mathfrak{A}_P$ .

Theorem5 is one of the main results of this paper. It plays a central role in ensuring the equivalence between the semantics for $\textit{NLP}$ and their counterpart for $\textit{SETAF}$ :

Theorem 6. Let $P$ be an $\textit{NLP}$ and $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be the associated $\textit{SETAF}$ . It holds

1. 1. $\mathcal{L}$ is a grounded labeling of $\mathfrak{A}_P$ iff $\mathcal{L}2\mathcal{I}_P(\mathcal{L})$ is a well-founded model of $P$ .

2. 2. $\mathcal{L}$ is a preferred labeling of $\mathfrak{A}_P$ iff $\mathcal{L}2\mathcal{I}_P(\mathcal{L})$ is a regular model of $P$ .

3. 3. $\mathcal{L}$ is a stable labeling of $\mathfrak{A}_P$ iff $\mathcal{L}2\mathcal{I}_P(\mathcal{L})$ is a stable model of $P$ .

4. 4. $\mathcal{L}$ is a semi-stable labeling of $\mathfrak{A}_P$ iff $\mathcal{L}2\mathcal{I}_P(\mathcal{L})$ is an $L$ -stable model of $P$ .

The following result is a direct consequence of Theorems4 and 6:

Corollary 7. Let $P$ be an $\textit{NLP}$ and $\mathfrak{A}_P = (\mathcal{A}_P, \mathit{Att}_P)$ be the associated $\textit{SETAF}$ . It holds

1. 1. $\mathcal{M}$ is a well-founded model of $P$ iff $\mathcal{I}2\mathcal{L}_P(\mathcal{M})$ is a grounded labeling of $\mathfrak{A}_P$ .

2. 2. $\mathcal{M}$ is a regular model of $P$ iff $\mathcal{I}2\mathcal{L}_P(\mathcal{M})$ is a preferred labeling of $\mathfrak{A}_P$ .

3. 3. $\mathcal{M}$ is a stable model of $P$ iff $\mathcal{I}2\mathcal{L}_P(\mathcal{M})$ is a stable labeling of $\mathfrak{A}_P$ .

4. 4. $\mathcal{M}$ is an $L$ -stable model of $P$ iff $\mathcal{I}2\mathcal{L}_P(\mathcal{M})$ is a semi-stable labeling of $\mathfrak{A}_P$ .

Next, we consider the $\textit{NLP}$ exploited by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b) as a counterexample to show that in general, $L$ -stable models and semi-stable labelings do not coincide with each other in their translation from $\textit{NLP}$ s to $\mathit{AAF}$ s:

Example 4. Let $P$ be the $\textit{NLP}$ and $\mathfrak{A}_P$ be the associated $\textit{SETAF}$ depicted in Figure 4:

Fig. 4. $\textit{NLP}$ $P$ and its associated $\textit{SETAF}$ $\mathfrak{A}_P$ .

As expected from Theorems5 and 6, we obtain in Table 1 the equivalence between partial stable models and complete labelings, well-founded models and grounded labelings, regular models and preferred labelings, stable models and stable labelings, $L$ -stable models and semi-stable labelings. We emphasize the coincidence between $L$ -stable models and semi-stable labelings in Table 1 as it does not occur in the approach of Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b). In their work, the associated $\mathit{AAF}$ possesses two semi-stable labelings in contrast with the unique $L$ -stable model $\mathcal{M}_3$ of $P$ . In the next two sections, we will show that this relation between $\textit{NLP}$ s and $\textit{SETAF}$ s has even deeper implications.

4 From $\textit{SETAF}$ to $\textit{NLP}$

Now we will provide a translation in the other direction, that is, from $\textit{SETAF}$ s to $\textit{NLP}$ s. As in the previous section, this translation guarantees the equivalence between the semantics for $\textit{NLP}$ s and their counterpart for $\textit{SETAF}$ s.

Definition 12. Let $\mathfrak{A} = (\mathcal{A}, \mathit{Att})$ be a $\textit{SETAF}$ . For any argument $a \in \mathcal{A}$ , we will assume $\mathcal{V}_a = \{ V \mid V \textit{ is a minimal set (w.r.t. set inclusion) such that for each } \mathcal{B} \in \mathit{Att}(a), \textit{ there exists } b \in \mathcal{B} \cap V \}$ . We define the associated $\textit{NLP}$ $P_{\mathfrak{A}}$ as follows:

\begin{equation*}P_{\mathfrak {A}} = \left \{a \leftarrow \mathtt {not\ } b_1, \ldots \mathtt {not\ } b_n \mid a \in \mathcal {A}, V \in \mathcal {V}_a \textit { and } V = \left \{b_1, \ldots, b_n\right \}\right \}. \end{equation*}

Example 5. Recall the $\textit{SETAF}$ $\mathfrak{A}$ of Example 1 (it is the same as that in Figure 4 b). The associated $\textit{NLP}$ $P_{\mathfrak{A}}$ is

\begin{equation*} \begin {array}{lcl} d \leftarrow \mathtt {not\ } d & & c \leftarrow \mathtt {not\ } c, \mathtt {not\ } d\\[5pt] a \leftarrow \mathtt {not\ } b & & b \leftarrow \mathtt {not\ } a\\[5pt] c \leftarrow \mathtt {not\ } c, \mathtt {not\ } a & & e \leftarrow \mathtt {not\ } e, \mathtt {not\ } b \end {array} \end{equation*}

Notice that $P_{\mathfrak{A}}$ and the $\textit{NLP}$ $P$ of Example4 are the same. As it will be clear in the next section, this is not merely a coincidence. Besides, from Definition12, it is clear that ${\mathit{HB}}_{P_{\mathfrak{A}}} = \mathcal{A}$ . Consequently, when considering a $\textit{SETAF}$ $\mathfrak{A}$ and its associated $\textit{NLP}$ $P_{\mathfrak{A}}$ , the definition of the function $\mathcal{L}2\mathcal{I}_{\mathfrak{A}}$ (resp., $\mathcal{I}2\mathcal{L}_{\mathfrak{A}}$ ), which associates labelings with interpretations (resp., interpretations with labelings), will be simpler than the definition of $\mathcal{L}2\mathcal{I}_P$ (resp., $\mathcal{I}2\mathcal{L}_P$ ) presented in the previous section.

In contrast with $\mathcal{L}2\mathcal{I}_P$ and $\mathcal{I}2\mathcal{L}_P$ , the functions $\mathcal{L}2\mathcal{I}_{\mathfrak{A}}$ and $\mathcal{I}2\mathcal{L}_{\mathfrak{A}}$ are each other’s inverse in the general case:

Table 1. Semantics for $P$ and $\mathfrak{A}_P$

A similar result to Theorem5 also holds here:

From Theorem9, we can ensure the equivalence between the semantics for $\textit{NLP}$ and their counterpart for $\textit{SETAF}$ :

The following result is a direct consequence of Theorems8 and 10:

Recalling the $\textit{SETAF}$ $\mathfrak{A}$ and its associated $P_{\mathfrak{A}}$ of Example5, we obtain the expected equivalence results related to their semantics (see Table 1). In the next section, we will identify a class of $\textit{NLP}$ s in which the translation from a $\textit{SETAF}$ to an $\textit{NLP}$ (Definition12) behaves as the inverse of the translation from an $\textit{NLP}$ to a $\textit{SETAF}$ (Definition10).

5 On the relation between $\textit{RFALP}$ s and $\textit{SETAF}$ s

We will recall a particular kind of $\textit{NLP}$ s, called Redundancy-Free Atomic Logic Programs $(\textit{RFALP} s)$ . From an $\textit{RFALP}$ $P$ , we obtain its associated $\textit{SETAF}$ $\mathfrak{A}_P$ via Definition10; from $\mathfrak{A}_P$ , we obtain its associated $\textit{NLP}$ $P_{\mathfrak{A}_P}$ via Definition12. By following the other direction, from a $\textit{SETAF}$ $\mathfrak{A}$ , we obtain its associated $\textit{NLP}$ $P_{\mathfrak{A}}$ , and from $P_{\mathfrak{A}}$ , its associated $\textit{SETAF}$ $\mathfrak{A}_{P_{\mathfrak{A}}}$ . An important result mentioned in this section is that $P = P_{\mathfrak{A}_P}$ and $\mathfrak{A} = \mathfrak{A}_{P_{\mathfrak{A}}}$ ; that is, the translation from an $\textit{NLP}$ to a $\textit{SETAF}$ and the translation from a $\textit{SETAF}$ to an $\textit{NLP}$ are each other’s inverse. Next, we define $\textit{RFALP}$ s:

First, Proposition12 sustains that for any $\textit{SETAF}$ $\mathfrak{A}$ , its associated $\textit{NLP}$ $P_{\mathfrak{A}}$ will always be an $\textit{RFALP}$ :

The following results guarantee that $\mathfrak{A} = \mathfrak{A}_{P_{\mathfrak{A}}}$ (Theorem13) and $P = P_{\mathfrak{A}_P}$ (Theorem14):

Remark 1. Minimality is crucial to ensure that the translation from an $\textit{NLP}$ to a $\textit{SETAF}$ and the translation from a $\textit{SETAF}$ to an $\textit{NLP}$ are each other’s inverse. If the minimality requirement in Definition 1 (and consequently in Definition 9) were dropped, any $\textit{SETAF}$ (among other combinations) in Figure 5 could be a possible candidate to be the associated $\textit{SETAF}$ $\mathfrak{A}_P$ of the $\textit{RFALP}$ $P$

\begin{equation*} \begin {array}{lcl} c \leftarrow \mathtt {not\ } a, \mathtt {not\ } c & & c \leftarrow \mathtt {not\ } b, \mathtt {not\ } c\\[5pt] a & & b \end {array} \end{equation*}

Fig. 5. Possible $\textit{SETAF}$ s associated with $P$ .

As a result, Theorem 13 would no longer hold, and these translations would not be each other’s inverse. Notice also that the $\textit{SETAF}$ s in Figure 5 have the same complete labelings as non-minimal attacks are irrelevant and can be ignored when determining semantics based on complete labelings.

Theorems13 and 14 reveal that $\textit{SETAF}$ s and $\textit{RFALP}$ s are essentially the same formalism. The equivalence between them involves their semantics and is also structural: two distinct $\textit{SETAF}$ s will always be translated into two distinct $\textit{RFALP}$ s and vice versa. In contradistinction, Theorem14 would not hold if we had replaced our translation from $\textit{NLP}$ to $\textit{SETAF}$ (Definition10) with that from $\textit{NLP}$ to $\mathit{AAF}$ presented by Caminada et al. (Reference Caminada, Sá, Alcântara and Dvořák2015b). Thus, the connection between $\textit{NLP}$ s and $\textit{SETAF}$ s is more robust than that between $\textit{NLP}$ s and $\mathit{AAF}$ s. In the forthcoming section, we will explore how expressive $\textit{RFALP}$ s can be; we will ensure they are as expressive as $\textit{NLP}$ s.

6 On the expressiveness of $\textit{RFALP}$ s

Dvořák et al. (Reference Dvořák, Fandinno and Woltran2019) comprehensively characterized the expressiveness of $\textit{SETAF}$ s. Now we compare the expressiveness of $\textit{NLP}$ s with that of $\textit{RFALP}$ s. In the previous section, we established that $\textit{SETAF}$ s and $\textit{RFALP}$ s are essentially the same formalism. We demonstrated that from the $\textit{SETAF}$ $\mathfrak{A}_P$ associated with an $\textit{NLP}$ $P$ , we can obtain $P$ ; and conversely, from the $\textit{NLP}$ $P_{\mathfrak{A}}$ associated with a $\textit{SETAF}$ $\mathfrak{A}$ , we can obtain $\mathfrak{A}$ . Here, we reveal that this connection between $\textit{SETAF}$ s and $\textit{RFALP}$ s is even more substantial: $\textit{RFALP}$ s are as expressive as $\textit{NLP}$ s when considering the semantics for $\textit{NLP}$ s we have exploited in this paper. With this aim in mind, we transform any $\textit{NLP}$ $P$ into an $\textit{RFALP}$ $P^*$ by resorting to a specific combination (denoted by $\mapsto _{\textit{UTPM}}$ ) of some program transformations proposed by Brass and Dix (Reference Brass and Dix1994, Reference Brass and Dix1997, Reference Brass and Dix1999). Although each program transformation in $\mapsto _{\textit{UTPM}}$ was proposed by Brass and Dix (Reference Brass and Dix1994, Reference Brass and Dix1997, Reference Brass and Dix1999), the combination of these program transformations (as far as we know) has not been investigated yet. Then, we show that $P$ and $P^*$ share the same partial stable models. Since well-founded models, regular models, stable models, and $L$ -stable models are all settled on partial stable models, it follows that both $P$ and $P^*$ also coincide under these semantics. Based on Dunne et al.’s (Reference Dunne, Dvořák, Linsbichler and Woltran2015) work, where they define the notion of expressiveness of the semantics for $\mathit{AAF}$ s, we define formally expressiveness in terms of the signatures of the semantics for $\textit{NLP}$ s:

Definition 15 (Expressiveness). Let $\mathcal{P}$ be a class of $\textit{NLP}$ s. The signature $\Sigma ^{\mathcal{P}}_{\mathit{PSM}}$ of the partial stable models associated with $\mathcal{P}$ is defined as

\begin{equation*} \Sigma ^{\mathcal {P}}_{\mathit {PSM}} = \left \{ \sigma (P) \mid P \in \mathcal {P}\right \}, \end{equation*}

where $\sigma (P) = \left \{\mathcal{I} \mid \mathcal{I} \textit{ is a partial stable model of } P\right \}$ is the set of all partial stable models of $P$ .

Given two classes $\mathcal{P}_1$ and $\mathcal{P}_2$ of $\textit{NLP}$ s, we say that $\mathcal{P}_1$ and $\mathcal{P}_2$ have the same expressiveness for the partial stable models semantics if $\Sigma ^{\mathcal{P}_1}_{\mathit{PSM}} = \Sigma ^{\mathcal{P}_2}_{\mathit{PSM}}$

In other words, $\mathcal{P}_1$ and $\mathcal{P}_2$ have the same expressiveness if

• • For every $P_1 \in \mathcal{P}_1$ , there exists $P_2 \in \mathcal{P}_2$ such that $P_1$ and $P_2$ have the same set of partial stable models.

• • For every $P_2 \in \mathcal{P}_2$ , there exists $P_1 \in \mathcal{P}_1$ such that $P_1$ and $P_2$ have the same set of partial stable models.

Similarly, we can define when $\mathcal{P}_1$ and $\mathcal{P}_2$ have the same expressiveness for the well-founded, regular, stable, and $L$ -stable semantics.

As the class of $\textit{RFALP}$ s is contained in the class of all $\textit{NLP}$ s, to show that these classes have the same expressiveness for these semantics, it suffices to prove that for every $\textit{NLP}$ , there exists an $\textit{RFALP}$ with the same set of partial stable models. We will obtain this result by resorting to a combination of program transformations:

Thus, $P \mapsto ^* P'$ means that there is a finite sequence $P = P_1 \mapsto \cdots \mapsto P_n = P'$ . We are particularly interested in program transformations preserving partial stable models:

From Definitions18 to 21, we focus on the following program transformations introduced by Brass and Dix (Reference Brass and Dix1994, Reference Brass and Dix1997, Reference Brass and Dix1999): Unfolding (it is also known as Generalized Principle of Partial Evaluation (GPPE)), elimination of tautologies, positive reduction, and elimination of non-minimal Rules. They are sufficient for our purposes.

Definition 18 (Unfolding (Brass and Dix, Reference Brass and Dix1994, Reference Brass and Dix1997, Reference Brass and Dix1999)). An $\textit{NLP}$ $P_2$ results from an $\textit{NLP}$ $P_1$ by unfolding ( $P_1 \mapsto _U P_2$ ) iff there exists a rule $c \leftarrow a, a_1, \ldots, a_m, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \in P_1$ such that

\begin{align*} P_2 = &\ (P_1 - \left \{c \leftarrow a, a_1, \ldots, a_m, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n\right \})\\[5pt] & \hspace{5em} \cup \{c \leftarrow a_1', \ldots, a_p', a_1, \ldots, a_m, \mathtt{not\ } b_1', \ldots, \mathtt{not\ } b_q', \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \mid \\[5pt] & \hspace{6.675em} a \leftarrow a_1', \ldots, a_p', \mathtt{not\ } b_1', \ldots, \mathtt{not\ } b_q' \in P_1 \}. \end{align*}

Definition 20 (Positive Reduction (Brass and Dix, Reference Brass and Dix1994, Reference Brass and Dix1999)). An $\textit{NLP}$ $P_2$ results from an $\textit{NLP}$ $P_1$ by positive reduction ( $P_1 \mapsto _P P_2$ ) iff there exists a rule $c \leftarrow a_1, \ldots, a_m, \mathtt{not\ } b, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n \in P_1$ such that $b \not \in \left \{{\mathit{head}}(r) \mid r \in P_1\right \}$ and

\begin{align*} P_2 = &\ (P_1 - \left \{c \leftarrow a_1, \ldots, a_m, \mathtt{not\ } b, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n\right \})\\[5pt] & \hspace{4.475em} \cup \left \{c \leftarrow a_1, \ldots, a_m, \mathtt{not\ } b_1, \ldots, \mathtt{not\ } b_n\right \}. \end{align*}

Now we combine these program transformations and define $\mapsto _{\textit{UTPM}}$ as follows:

We call an $\textit{NLP}$ $P$ irreducible concerning $\mapsto$ if there is no $\textit{NLP}$ $P' \neq P$ with $P \mapsto ^* P'$ . Besides, we say $\mapsto$ is strongly terminating iff every sequence of successive applications of $\mapsto$ eventually leads to an irreducible $\textit{NLP}$ . As displayed by Brass and Dix (Reference Brass and Dix1998), not every program transformation is strongly terminating. For instance, in the $\textit{NLP}$

\begin{equation*} \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \end{equation*}

if we apply unfolding $(\mapsto _U)$ to the third rule, this rule is replaced by $c \leftarrow b, \mathtt{not\ } c$ . We can now apply unfolding again to this rule and get the original program; such an oscillation can repeat indefinitely. Thus we have a sequence of program transformations that do not terminate. However, if we restrict ourselves to fair sequences of program transformations, the termination is guaranteed:

The sequence above of program transformations is not fair, because it does not remove the positive body atoms occurring in the program. In contrast, the sequence of program transformations given by

\begin{equation*} \small { \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} a & \leftarrow & a\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _T \begin {array}{rcl} b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} b & \leftarrow & a\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} c \end {array} } \end{equation*}

is not only fair but also terminates. The next result guarantees that it is not simply a coincidence:

Theorem15 is crucial to obtain the following result:

This means that from an $\textit{NLP}$ $P$ , it is always possible to obtain an irreducible $\textit{NLP}$ $P^*$ after successive applications of $\mapsto _{\textit{UTPM}}$ . Indeed, $P^*$ is an $\textit{RFALP}$ :

From Theorems15 and 17, we can infer that for fair sequences, after applying repeatedly $\mapsto _{\textit{UTPM}}$ , we will eventually produce an $\textit{RFALP}$ . In fact, every $\textit{RFALP}$ is irreducible:

Theorems16 and 17 guarantee that every $\textit{NLP}$ $P$ can be transformed into an $\textit{RFALP}$ $P^*$ by applying $\mapsto _{\textit{UTPM}}$ a finite number of times. It remains to show that $P$ and $P^*$ share the same partial stable models (and consequently, the same well-founded, regular, stable, and $L$ -stable models). Before, however, note that $\mapsto _{\textit{UTPM}}$ does not introduce new atoms; instead, it can eliminate the occurrence of existing atoms in an $\textit{NLP}$ . For simplicity in notation, we assume throughout the rest of this section that ${\mathit{HB}}_P ={\mathit{HB}}_{P'}$ whenever $P \mapsto _{\textit{UTPM}}^* P'$ . Next, we recall that these program transformations preserve the least models of positive programs:

In the sequel, we aim to extend Lemma19 to $\textit{NLP}$ s. Notice, however, that we already have the result for the program transformation $\mapsto _U$ :

It remains to guarantee the result for the program transformation $\mapsto _T$ , $\mapsto _P$ and $\mapsto _M$ :

Consequently, if $P_1 \mapsto _{\textit{UTPM}} P_2$ , then $P_1$ and $P_2$ share the same partial stable models. By repeatedly resorting to this result, we can even show that for any $\textit{NLP}$ , there exists an irreducible $\textit{NLP}$ with the same set of partial stable models, well-founded models, regular models, stable models, and $L$ -stable models:

As any irreducible $\textit{NLP}$ is an $\textit{RFALP}$ (Theorem17), the following result is immediate:

Given that each $\textit{NLP}$ can be associated with an $\textit{RFALP}$ preserving the semantics above, it follows that $\textit{NLP}$ and $\textit{RFALP}$ s have the same expressiveness for those semantics:

Another important result is that the $\textit{SETAF}$ corresponding to an $\textit{NLP}$ is invariant with respect to $\mapsto _{\textit{UTPM}}$ :

This means that any $\textit{NLP}$ in a sequence of program transformations from $\mapsto _{\textit{UTPM}}$ has the same corresponding $\textit{SETAF}$ . For instance, every $\textit{NLP}$ in this sequence

\begin{equation*} \small { \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} a & \leftarrow & a\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _T \begin {array}{rcl} b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} b & \leftarrow & a\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} c \end {array} } \end{equation*}

leads to the same corresponding $\textit{SETAF}$ , constituted by a unique (unattacked) argument:

Theorem28 also suggests an alternative way to find the $\textit{SETAF}$ corresponding to an $\textit{NLP}$ $P$ : instead of resorting directly to Definition8 to construct the arguments, we can apply (starting from $P$ ) $\mapsto _{\textit{UTPM}}$ successively by following a fair sequence of program transformations. By Theorems15 and 17, we know that eventually, we will reach an $\textit{RFALP}$ whose corresponding $\textit{SETAF}$ is identical to that of the original program $P$ (Theorem28). Then, we apply Definition8 to this $\textit{RFALP}$ to obtain the arguments and Definition9 for the attack relation. Notably, when $P$ is an $\textit{RFALP}$ , Definition8 becomes considerably simpler, requiring only its first item to characterize the statements.

In addition, from the same $\textit{NLP}$ , various fair sequences of program transformations can be conceived. Recalling the $\textit{NLP}$

\begin{equation*} \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \end{equation*}

exploited above, we can design the following alternative fair sequence

\begin{equation*} \small { \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & a\\[5pt] c & \leftarrow & a, \mathtt {not\ } c\\[5pt] c \end {array} \mapsto _M \begin {array}{rcl} a & \leftarrow & a\\[5pt] b & \leftarrow & a\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} a & \leftarrow & b\\[5pt] b & \leftarrow & b\\[5pt] c \end {array} \mapsto _T \begin {array}{rcl} a & \leftarrow & b\\[5pt] c \end {array} \mapsto _U \begin {array}{rcl} c \end {array} } \end{equation*}

This sequence produced the same $\textit{RFALP}$ as before; it is not a coincidence. Apart from being strongly terminating for fair sequences of program transformations, the relation $\mapsto _{\textit{UTPM}}$ has an appealing property; it is also confluent:

By confluent $\mapsto _{\textit{UTPM}}$ , we mean that it does not matter the path we take by repeatedly applying $\mapsto _{\textit{UTPM}}$ , if it ends, it will always lead to the same irreducible $\textit{NLP}$ . In addition, as any irreducible $\textit{NLP}$ is an $\textit{RFALP}$ (Theorem17), and the translations from $\textit{SETAF}$ to $\textit{RFALP}$ s and conversely, from $\textit{RFALP}$ s to $\textit{SETAF}$ are each other’s inverse (Theorems13 and 14), we obtain that two distinct $\textit{SETAF}$ s will always be associated with two distinct $\textit{NLP}$ s. The confluence of $\mapsto _{\textit{UTPM}}$ is of particular significance from the logic programming perspective as it guarantees that the ordering of the transformations in $\textit{UTPM}$ does not matter: we are free to choose always the “best” transformation, which maximally reduces the program. Consequently, Theorem29 also sheds light on the search for efficient implementations in $\textit{NLP}$ s.

From the previous section, we know that the equivalence between $\textit{SETAF}$ s and $\textit{RFALP}$ s is not only of a semantic nature but also structural: two distinct $\textit{SETAF}$ s will always be translated into two distinct $\textit{RFALP}$ s and vice versa. Now we enhance our understanding of this result still more by establishing that