<figure><img src="image_1.png" /></figure>

HAL
open science

# On the Trap Space Semantics of Normal Logic Programs

Van-Giang Trinh, Sylvain Soliman, François Fages, Belaid Benhamou

► To cite this version:

Van-Giang Trinh, Sylvain Soliman, François Fages, Belaid Benhamou. On the Trap Space Semantics of Normal Logic Programs. ICLP 2025 - 41st International Conference on Logic Programming, Sep 2025, Rende, Italy. pp.294-319, 10.4204/EPTCS.439.21 . hal-05299701

HAL Id: hal-05299701

https://amu.hal.science/hal-05299701v1

Submitted on 6 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Trap Space Semantics of Normal Logic Programs

Van-Giang Trinh

Sylvain Soliman

François Fages

Inria Saclay, EP Lifeware, Palaiseau, France

van-giang.trinh@inria.fr

Sylvain.Soliman@inria.fr

francois.fages@inria.fr

## Belaid Benhamou

LIRICA team, LIS, Aix-Marseille University, Marseille, France

belaid.benhamou@lis-lab.fr

The logical semantics of normal logic programs has traditionally been based on the notions of Clark's completion and two-valued or three-valued canonical models, including supported, stable, regular, and well-founded models. Two-valued interpretations can also be seen as states evolving under a program's update operator, producing a transition graph whose fixed points and cycles capture stable and oscillatory behaviors, respectively. We refer to this view as *dynamical semantics* since it characterizes the program's meaning in terms of state-space trajectories, as first introduced in the stable (supported) class semantics. Recently, we have established a formal connection between Datalog programs (i.e., normal logic programs without function symbols) and Boolean networks, leading to the introduction of the *trap space* concept for Datalog programs. In this paper, we generalize the trap space concept to arbitrary normal logic programs, introducing *trap space semantics* as a new approach to their interpretation. This new semantics admits both model-theoretic and dynamical characterizations, providing a comprehensive approach to understanding program behaviors. We establish the foundational properties of the trap space semantics and systematically relate it to the established model-theoretic semantics, including the stable (supported), stable (supported) partial, regular, and L-stable model semantics, as well as to the dynamical stable (supported) class semantics. Our results demonstrate that the trap space semantics offers a unified and precise framework for proving the existence of supported classes, strict stable (supported) classes, and regular models, in addition to uncovering and formalizing deeper relationships among the existing semantics of normal logic programs.

**Keywords:** logic programming, normal logic program, Clark's completion, model-theoretic semantics, dynamical semantics, trap space, Boolean network, infinite structure

## 1 Introduction

The meaning of a Normal Logic Program (NLP)—its declarative semantics—is typically defined by a class of models of a logical formula associated with the program, such as the Herbrand models of the *Clark's completion* of the program [13]. This was later shown to be equivalent to the *supported model semantics* [2]. For NLPs with negation, the Clark's completion may have no model, or several minimal models; therefore, there is generally no unique least Herbrand model. In this setting, the *stable model semantics* was introduced by [24] to provide a canonical notion of two-valued models, defined by an elegant fixed-point definition based on the least model of a *reduct* transformation. Stable models were later characterized as *well-supported models* [21], i.e., models with circuit-free finite justifications—which led to graphical conditions for the existence of stable models [20, 1], and equivalence results with other forms of non-monotonic logics [43, 31, 32, 7].

A three-valued logic approach was introduced, where the third value denotes ignorance [23, 33, 35]. Subsequent research expanded the semantic landscape of NLPs through additional three-valued logic
transformations [3]. The *stable (supported) partial model semantics*—also known as the three-valued stable (supported) model semantics—extends the two-valued stable (supported) model semantics [34, 19, 33]. Under this framework, all models are minimal, and every NLP possesses at least one stable (supported) partial model. Notably, two specific types of stable partial semantics are distinguished by their informational content: the *well-founded partial model semantics* [22, 33], representing the unique model with minimal information, and the *regular model semantics* [42], encompassing models with maximal information. It is worth noting that these three-valued semantics (e.g., stable partial models, regular models) in normal logic programs have been shown to correspond to several extension-based semantics (e.g., complete extensions, preferred extensions, respectively) in Dung's frameworks [17, 41] and assumption-based argumentation [10], which are two prominent formalisms in symbolic AI.

Alternatively, an NLP can be viewed as a state-transition system in which each rule in the program represents how a component (here an atom) is affected by other components [4, 8]. The dynamical behaviors of the program, including its oscillating behavior [27], are characterized by a directed graph called the (stable or supported) *transition graph* whose vertices are two-valued interpretations and whose arcs are transitions between interpretations. This led to the *stable class semantics* [4] and *supported class semantics* [27]. If a stable (resp. supported) class is of size one, it coincides with a stable (resp. supported) model and exhibits a stable behavior. Otherwise, it exhibits an oscillating behavior.

The aforementioned semantics capture various aspects of program behavior. Despite their success, they often diverge in interpretive principles, and many lack a unifying framework that integrates both model-theoretic and dynamical behaviors coherently. Recently, we have established a formal connection between *Datalog*~ programs (i.e., NLPs without function symbols~—thus the Herbrand base is finite) and Boolean networks, leading to the introduction of the concept of *trap space* for *Datalog*~ programs, inspired by the notion of trap space in Boolean networks [28, 39]. This concept offers a bridge between model-theoretic and dynamical aspects, but applies only to finite structures [40].

In this paper, we generalize the trap space concept to arbitrary NLPs, introducing *trap space semantics* as a new approach to their interpretation. This new semantics admits both model-theoretic and dynamical characterizations, providing a comprehensive approach to understanding program behavior. We establish foundational properties of the trap space semantics and systematically relate it to established model-theoretic and dynamical semantics—including the stable (supported), stable (supported) partial, regular, and L-stable model semantics—as well as to dynamical semantics such as the stable (supported) class semantics. Our results demonstrate that the trap space semantics offers a unified framework (along with a proper use of set-theoretic axioms) for proving the existence of supported classes, strict supported classes, strict stable classes, or regular models—proofs that have been unfortunately either missing or imprecise in prior literature [4, 42, 27]. Furthermore, by leveraging the concept of stable or supported trap set underlying the trap space semantics, we correct a flaw in the existing alternative characterization of strict stable or supported classes established in [27]. Finally, the trap space semantics emerges as a powerful tool for uncovering and formalizing deeper relationships among various existing semantics of NLPs, for instance, the stable (resp. supported) class semantics vs. the stable (resp. supported) partial model semantics, and the regular model semantics vs. the stable class semantics and the L-stable model semantics.

The rest of the paper is organized as follows: in Section 2, we review the necessary background on NLPs and set theory. Section 3 presents the formal definitions of the trap space semantics, as well as its fundamental properties. Section 4 shows the relationships between the trap space semantics and other semantics. In Section 5, we present the existence results. Section 6 offers concluding remarks and future research directions.
# 2 Preliminaries

## 2.1 Normal Logic Programs

We assume that the reader is familiar with the logic programming theory and stable model semantics. Unless specifically stated, NLP means normal logic program. In addition, we consider the Boolean domain $\mathbb{B} = \{0, 1\}$, the three-valued domain $\mathbb{B}_* = \{0, 1, \star\}$. The logical connectives used in this paper are $\land$ (conjunction), $\lor$ (disjunction), $\neg$ (negation), and $\leftrightarrow$ (equivalence).

We consider a first-order language built over an infinite alphabet of variables, and finite alphabets of constant, function, and predicate symbols. The set of first-order terms is the least set containing variables and constants, and closed by application of function symbols. An atom is a formula of the form $p(t_1, ..., t_k)$ where $p$ is a predicate symbol and each $t_i$ is a term. A normal logic program $P$ is a finite set of rules of the form $p \leftarrow p_1, ..., p_m, \sim p_{m+1}, ..., \sim p_k$ where $p$ and $p_i$ are atoms, $k \ge m \ge 0$, and $\sim$ denotes default negation. A fact is a rule with $k = 0$. For any rule $r$ of the above form, $h(r) = p$ is called the head of $r$, $b^+(r) = \{p_1, ..., p_m\}$ is called the positive body of $r$, $b^-(r) = \{p_{m+1}, ..., p_k\}$ is called the negative body of $r$, and $b(r) = b^+(r) \cup b^-(r)$ is called the body of $r$. For convenience, we denote $bf(r) = \bigwedge_{v \in b^+(r)} v \wedge \bigwedge_{v \in b^-(r)} \neg v$ as the body formula of $r$; if $k = 0$, then $bf(r) = 1$. If $b^-(r) = \emptyset$ for all $r \in P$, then $P$ is called a positive NLP. If $b^+(r) = \emptyset$ for all $r \in P$, then $P$ is called a negative NLP. The program $P$ is called internal-variable-free if for any rule in $P$, the variables in the body also appear in the head [36].

A term, an atom, or an NLP is ground if it contains no variables. The Herbrand base of an NLP $P$ (denoted by $HB_P$) is the set of ground atoms formed over the alphabet of $P$. It is finite in the absence of function symbols, which is the case of Datalog programs [12]. The ground instantiation of an NLP $P$ (denoted by $gr(P)$) is the set of the ground instances of all rules in $P$. An NLP $P$ is called uni-rule if every atom in $HB_P$ appears in the head of at most one rule in $gr(P)$ [37].

We shall use the least fixpoint transformation of NLPs [18] to prove many new results in the next sections. To be self-contained, we briefly recall the definition of the least fixpoint of an NLP $P$ as follows. The reader can refer [18] for more details. Let $r$ be the rule $p \leftarrow \sim p_1, ..., \sim p_k, q_1, ..., q_j$ in $gr(P)$ and let $r_i$ be the rules $q_i \leftarrow \sim q_i^1, ..., \sim q_i^{l_i}$ in $gr(P)$ where $1 \le i \le j$ and $l_i \ge 0$. Then $\Pi_r(\{r_1, ..., r_j\})$ is the following rule

$$p \leftarrow \sim p_1, ..., \sim p_k, \sim q_1^1, ..., \sim q_1^{l_1}, ..., \sim q_j^1, ..., \sim q_j^{l_j},$$

which means that each atom $q_j$ in the positive body of $r$ is substituted with the body of the rule $r_j$. Then $\Pi_P$ is the transformation on negative normal logic programs:

$$\Pi_P(Q) = \{\Pi_r(\{r_1, ..., r_j\}) \mid r \in gr(P), r_i \in Q, 1 \le i \le j\}.$$

Let $\text{lfp}(P)_i = (\Pi_P(\emptyset))^i = \Pi_P(\Pi_P(...\Pi_P(\emptyset)))$, then $\text{lfp}(P) = \bigcup_{i \ge 1} \text{lfp}(P)_i$ is the least fixpoint of the NLP $P$.

### 2.1.1 Stable and Supported Partial Models

A three-valued interpretation $I$ of an NLP $P$ is a mapping $I: HB_P \to \mathbb{B}_*$. If $I(a) \ne \star$ for all $a \in HB_P$, then $I$ is a two-valued interpretation of $P$. Usually, a two-valued interpretation is written as the set of atoms that are true. A three-valued interpretation $I$ characterizes the set of two-valued interpretations denoted by $\mathcal{S}(I)$ as $\mathcal{S}(I) = \{J \mid J \in 2^{HB_P}, \forall a \in HB_P, I(a) \ne \star \Rightarrow J(a) = I(a)\}$. For example, if $I = \{p = 1, q = 0, r = \star\}$, then $\mathcal{S}(I) = \{\{p\}, \{p, r\}\}$. We consider three orders on three-valued interpretations. The truth
order $\le_t$ is given by $0 <_t * <_t 1$. Then, $I_1 \le_t I_2$ iff $I_1(a) \le_t I_2(a)$ for all $a \in \text{HB}_P$. The order $\le_s$ is given by $0 <_s *$, $1 <_s *$; no other relations hold. Then, $I_1 \le_s I_2$ iff $I_1(a) \le_s I_2(a)$ for all $a \in \text{HB}_P$. In addition, $I_1 \le_s I_2$ iff $\mathcal{S}(I_1) \subseteq \mathcal{S}(I_2)$, i.e., $\le_s$ is identical to the subset partial order. The information order $\le_i$ is given by $* <_i 0$, $* <_i 1$; no other relations hold. Then, $I_1 \le_i I_2$ iff $I_1(a) \le_i I_2(a)$ for all $a \in \text{HB}_P$. It is easy to see that $\le_i$ is the complement of $\le_s$, i.e., $I_1 \le_s I_2$ iff $I_2 \le_i I_1$.

Let $e$ be a propositional formula on $\text{HB}_P$, using only the $\neg$, $\wedge$, and $\vee$ connectives. Then the valuation of $e$ under a three-valued interpretation $I$ (denoted by $I(e)$) following the three-valued logic is defined recursively as follows: $I(e) = e$ if $e \in \mathbb{B}_*$; $I(e) = I(a)$ if $e = a, a \in \text{HB}_P$; $I(e) = \neg I(e_1)$ if $e = \neg e_1$; $I(e) = \min_{\le_t} (I(e_1), I(e_2))$ if $e = e_1 \wedge e_2$; and $I(e) = \max_{\le_t} (I(e_1), I(e_2))$ if $e = e_1 \vee e_2$ where $\neg 1 = 0, \neg 0 = 1, \neg * = *,$ and $\min_{\le_t}$ (resp. $\max_{\le_t}$) is the function to get the minimum (resp. maximum) value of two values w.r.t. the order $\le_t$. We say three-valued interpretation $I$ is a *three-valued model* of an NLP *P* if for each rule $r \in \text{gr}(P)$, $I(\text{bf}(r)) \le_t I(\text{h}(r))$.

Given a three-valued interpretation $I$ of an NLP $P$, the *reduct* of $P$ w.r.t. $I$ (denoted by $P^I$) is defined as: remove any rule $a \leftarrow a_1, \dots, a_m, \sim b_1, \dots, \sim b_k \in \text{gr}(P)$ if $I(b_i) = 1$ for some $1 \le i \le k$; afterwards, remove any occurrence of $\sim b_i$ from $\text{gr}(P)$ such that $I(b_i) = 0$; then, replace any occurrence of $\sim b_i$ left by a special atom $u$ such that $u \notin \text{HB}_P$ and it always receives the value $*$. The NLP $P^I$ is positive and has a unique $\le_t$-least three-valued model. See [33] for the method for computing this $\le_t$-least model. Then $I$ is a *stable partial model* of $P$ if $I$ is equal to the $\le_t$-least three-valued model of $P^I$. A stable partial model $I$ is an *M-stable model* if it is $\le_s$-minimal [35]. In this paper, we define a *regular model* as an M-stable model as they are equivalent [19]. In the two-valued setting, $P^I$ is identical to the reduct defined by [24]; $I$ is a *stable model* of $P$ if $I$ is equal to the $\le_t$-least two-valued model of $P^I$. It is easy to derive that a stable model is a two-valued regular model, as well as a two-valued stable partial model [3]. We define $I^u$ as the set of ground atoms that are assigned to $* \in I$, i.e., $I^u = \{v \mid v \in \text{HB}_P, I(v) = *\}$. Then $I$ is a *L-stable model* of $P$ if $I$ is a stable partial model of $P$ and there is no stable partial model $J$ such that $J^u \subset I^u$ [35].

The (propositional) *Clark's completion* of an NLP *P* (denoted by *comp(P)*) consists of the following equivalences: $p \leftrightarrow \bigvee_{r \in \text{gr}(P), h(r)=p} \text{bf}(r)$, for each $p \in \text{HB}_P$; if there is no rule whose head is $p$, then the equivalence is $p \leftrightarrow 0$. Let $\text{rhs}_P(a)$ denote the right-hand side of the equivalence of a ground atom $a \in \text{HB}_P$ in $\text{comp}(P)$. A three-valued interpretation $I$ is a three-valued model of $\text{comp}(P)$ iff for every $a \in \text{HB}_P$, $I(a) = I(\text{rhs}_P(a))$. In this work, we define a *supported partial model* of $P$ as a three-valued model of $\text{comp}(P)$, and a *supported model* of $P$ as a two-valued model of $\text{comp}(P)$. Clearly, a supported model is a (two-valued) partial supported model. It has been pointed out that a stable partial model (resp. stable model) is a supported partial model (resp. supported model), but the reverse may be not true [14].

### 2.1.2 Stable and Supported Classes

Let $P$ be an NLP and let $I$ be any two-valued interpretation of $P$. We have that $P^I$ is positive, and has a unique $\le_t$-least two-valued model (say $J$). We define the operator $F_P$ as $F_P(I) = J$. In contrast, we define the operator $T_P$ as $T_P(I) = J$ where $J$ is a two-valued interpretation such that for every $a \in \text{HB}_P$, $J(a) = I(\text{rhs}_P(a))$.

**Definition 2.1.** A non-empty set $S$ of two-valued interpretations is a stable class of an NLP $P$ iff it holds that $S = \{F_P(I) \mid I \in S\}$ [4]. Similarly, $S$ is a supported class of an NLP $P$ iff it holds that $S = \{T_P(I) \mid I \in S\}$ [27]. A stable (resp. supported) class $S$ of $P$ is strict iff no proper subset of $S$ is a stable (resp. supported) class of $P$.

**Example 2.1.** Consider the NLP $P = \{a \leftarrow b; b \leftarrow a\}$ where the symbol “;” is used to separate program rules. Since $P$ is positive, for any two-valued interpretation $I$, $P^I = P$. It follows that $F_P(I) = \emptyset$ for all $I$.
It is easy to derive that P has only a unique stable class {$\emptyset$}. On the other hand, we have that $T_P(\emptyset) = \emptyset$, $T_P(\{a\}) = \{b\}$, $T_P(\{b\}) = \{a\}$, and $T_P(\{a,b\}) = \{a,b\}$. It is easy to derive that P has three supported classes: {$\emptyset$}, {$\{a\}$}, {$b$}, and {$\{a,b\}$}.

### 2.1.3 Transition Graphs

The stable (resp. supported) transition graph of P is a (possibly infinite) directed graph (denoted by $\text{tg}_{st}(P)$ (resp. $\text{tg}_{sp}(P)$)) on the set of all possible two-valued interpretations of P such that $(I, J)$ is an arc of $\text{tg}_{st}(P)$ (resp. $\text{tg}_{sp}(P)$) iff $J = F_P(I)$ (resp. $J = T_P(I)$). Given a directed graph $G$, we use $V(G)$ (resp. $E(G)$) to denote the set of vertices (resp. arcs) of $G$. For more details about theory of finite and infinite graphs, we refer the reader to [29].

**Example 2.2.** Consider the NLP $P = \{p(X) \leftarrow p(s(X))\}$. The ground instanciation of the Clark's completion of P includes $p(0) \leftrightarrow p(s(0))$, $p(s(0)) \leftrightarrow p(s(s(0)))$, ... It is easy to verify that P has only three supported partial models: $I_1$ where $I_1(a) = 0$ for every $a \in \text{HB}_P$, $I_2$ where $I_2(a) = 1$ for every $a \in \text{HB}_P$, and $I_3$ where $I_3(a) = \star$ for every $a \in \text{HB}_P$. We have $P^{I_1} = P^{I_2} = P^{I_3} = P$. It is easy to derive that $I_1$ is the unique stable partial model of P. It is also the unique regular model, stable model, and L-stable model of P. The stable and supported transition graphs of P are shown in Figure 1 (a) and Figure 1 (b), respectively. The NLP P has only one stable class $\{I_1\}$, but three supported classes $\{I_1\}$, $\{I_2\}$, and $\{I_1, I_2\}$. Then $\{I_1\}$ is the unique strict stable class of P, whereas $\{I_1\}$ and $\{I_2\}$ are strict supported classes of P.

<figure><img src="image_3.png" /><figcaption>Figure 1: Stable transition graph (a) and supported transition graph (b) of the NLP P of Example 2.2. Herein, $a_i$ denotes $p(s^i(0))$, $I_1(a) = 0, \forall a \in \text{HB}_P (I_1 = \emptyset)$, $I_2(a) = 1, \forall a \in \text{HB}_P (I_2 = \text{HB}_P)$.</figcaption></figure>

## 2.2 Set Theory

Our proofs in the following sections rely on existing results in set theory. To keep the paper self-contained, we recall them below. For more details, we refer the reader to [25].

**Lemma 2.1 (Zorn's lemma [44].)** Given a partially ordered set $(P, \leq)$. If any $\leq$-chain possesses an upper bound, then $(P, \leq)$ has a maximal element.

Zorn's lemma can also be formulated as follows:
**Lemma 2.2 ([6]).** Given a partially ordered set $(P, \le)$, if any $\le$-chain has an upper bound, then for any $p \in P$, $P$ has a maximal element $m$ such that $p \le m$.

**Lemma 2.3 (Hartogs' lemma).** For any set $X$, there is a least ordinal $\alpha$ such that there is no injection from $\alpha$ into $X$.

# 3 Trap Space Semantics

The concept of stable (resp. supported) trap set is obtained by relaxing the equality in Definition 2.1 of stable (resp. supported) class, as follows:

**Definition 3.1.** A non-empty set $S$ of two-valued interpretations of an NLP $P$ is called a stable trap set (resp. supported trap set) of $P$ iff $\{F_P(I) \mid I \in S\} \subseteq S$ (resp. $\{T_P(I) \mid I \in S\} \subseteq S$).

Note that a stable (resp. supported) class is clearly a stable (resp. supported) trap set, but the reverse may not be true. Indeed, given the NLP $P$ of Example 2.2, $\{\emptyset\}$ is a stable class and also a stable trap set, whereas $\{\emptyset, a_0\}$ is a stable trap set but not a stable class. Similarly, $\{\emptyset, HB_P\}$ is a supported class and also a supported trap set, whereas $\{\emptyset, a_0, a_1\}$ is a supported trap set but not a supported class. By adding the condition on three-valued interpretations, we obtain the concept of stable or supported trap space:

**Definition 3.2.** A three-valued interpretation $I$ of an NLP $P$ is called a stable trap space (resp. supported trap space) of $P$ iff $\mathcal{S}(I)$ is a stable (resp. supported) trap set of $P$. We call $I$ a trap space of $P$ iff it is a stable or supported trap space of $P$.

More broadly, it is easy to adapt the concept of stable or supported trap set of an NLP to a (possibly infinite) directed graph in general:

**Definition 3.3.** Consider a directed graph $G$. A non-empty subset $S$ of $V(G)$ is called a trap set of $G$ iff there are no two vertices $A$ and $B$ such that $A \in S$, $B \notin S$, and $(A, B) \in E(G)$.

By definition, this immediately follows that $S$ is a stable (resp. supported) trap set of $P$ iff $S$ is a trap set of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$). Hence, we can deduce from Definition 3.2 that a three-valued interpretation $I$ is a stable (resp. supported) trap space of $P$ iff $\mathcal{S}(I)$ is a trap set of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$). Since stable and supported transition graphs represent the dynamical aspect of an NLP [4, 27], this indicates that the trap space semantics for NLPs admits a dynamical characterization.

**Example 3.1.** Consider the NLP $P$ of Example 2.2. The stable and supported transition graphs of $P$ are shown in Figure 1 (a) and Figure 1 (b), respectively. We have that the three-valued interpretation $I_1$ is a stable (resp. supported) trap space of $P$ since $\mathcal{S}(I_1) = \{\emptyset\}$ is a stable (resp. supported) trap set of $P$. It is easy to verify that $\mathcal{S}(I_1)$ is also a trap set of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$). Note that $\{\emptyset, a_0, a_1\}$ is a stable (resp. supported) trap set, but it does not correspond to a stable (resp. supported) trap space of $P$. We see that $I_2$ is a supported trap space but not a stable trap space of $P$, since $\mathcal{S}(I_2) = \{HB_P\}$ is a supported trap set but not a stable trap set of $P$.

We define the *trap space semantics* of an NLP as the set of its trap spaces. When applicable we shall restrict ourselves to stable or supported trap spaces to relate those subsets to other semantics. For convenience, let $\text{StTS}(P)$ (resp. $\text{SuTS}(P)$) denote the set of stable (resp. supported) trap spaces of an NLP $P$. We first establish the simplest property, which is, however, vital for proving subsequent results, especially in infinite structures. Note that, due to space limitations, all proofs are given in Appendix A.

**Proposition 3.1.** An NLP $P$ always has a stable or supported trap space.
Next, we investigate the consistency among stable or supported trap spaces, which shall be used to
investigate the model or class disjointness (see Section 4).

**Definition 3.4.** Consider an NLP *P*. Two three-valued interpretations *I*₁ and *I*₂ of *P* are called consistent iff for all *a* ∈ HB<sub>P</sub>, *I*₁(*a*) ≤<sub>s</sub> *I*₂(*a*) or *I*₂(*a*) ≤<sub>s</sub> *I*₁(*a*). Equivalently, *I*₁ and *I*₂ are called consistent iff S(*I*₁)∩S(*I*₂) ≠ Φ.

Note that using $I_1 \leq_s I_2$ or $I_2 \leq_s I_1$ in Definition 3.4 is insufficient here, since two three-valued interpretations that are not comparable w.r.t. $\leq_s$ can still be consistent. We then generalize the above definition to a non-empty set of mutually consistent trap spaces:

**Definition 3.5.** Given an NLP *P*, let *E* be a non-empty set of mutually consistent three-valued interpretations (i.e., *E*<sub>*i*</sub> and *E*<sub>*j*</sub> are consistent for all *E*<sub>*i*</sub>, *E*<sub>*j*</sub> ∈ *E*). Then the intersection of all elements in *E* (denoted by ∩<sub>*E*</sub>) is a three-valued interpretation defined as: ∩<sub>*E*</sub>(*a*) = min<sub>≤*s*</sub> {*E*<sub>*i*</sub>(*a*) | *E*<sub>*i*</sub> ∈ *E*} for all atom *a* ∈ HB<sub>*P*</sub>. This is well-defined because {*E*<sub>*i*</sub>(*a*) | *E*<sub>*i*</sub> ∈ *E*} is a totally ordered finite set w.r.t. ≤<sub>*s*</sub> (thus its minimum element exists), since all elements in *E* are mutually consistent.

By pointing out that the intersection of mutually consistent stable (resp. supported) trap spaces is a
stable (resp. supported) trap space, along with applying Definition 3.4 and Lemma 2.2, we obtain the
following two lemmas:

**Lemma 3.1.** Consider an NLP *P* and a three-valued interpretation *J* of *P*. If *J* is a stable trap space of *P*, then there exists a *≤*<sub>s</sub>-minimal stable trap space *J'* of *P* such that *J'* *≤*<sub>s</sub> *J*.

**Lemma 3.2.** Consider an NLP *P* and a three-valued interpretation *J* of *P*. If *J* is a supported trap space of *P*, then there exists a *≤*<sub>s</sub>-minimal supported trap space *J'* of *P* such that *J'* *≤*<sub>s</sub> *J*.

In addition to Proposition 3.1, we obtain the following main result:

**Theorem 3.1 (main result).** Any NLP *P* has *a* ≤*s*-minimal stable (resp. supported) trap space.

We then establish the relationship between a non-empty set of two-valued interpretations and stable or supported trap spaces, which is useful for bridging the relationships between stable (resp. supported) classes and stable (resp. supported) trap spaces later.

**Proposition 3.2.** Consider an NLP *P*. Let *S* be a non-empty set of two-valued interpretations of *P*. Then there is a unique *≤*<sub>s</sub>-minimal stable (resp. supported) trap space, denoted by ⟨*S*⟩<sub>*P*</sub><sup>*st*</sup> (resp. ⟨*S*⟩<sub>*P*</sub><sup>*sp*</sup>), covering *S*, i.e., *S* ⊆ *S* (⟨*S*⟩<sub>*P*</sub><sup>*st*</sup>) (resp. *S* ⊆ *S* (⟨*S*⟩<sub>*P*</sub><sup>*sp*</sup>)).

Finally, we show the separation of trap spaces w.r.t. the $\leq_s$-minimality:

**Proposition 3.3.** Consider an NLP *P*. Let *I*₁ and *I*₂ be two distinct *≤*<sub>s</sub>-minimal stable (resp. supported) trap spaces of *P*. Then *I*₁ and *I*₂ are not consistent.

4 Relationships with Other Semantics

Naturally, if a stable (resp. supported) trap space of an NLP *P* is two-valued, then it is also a stable
LTEP
(resp. supported) model of *P*. We now present additional relationships between stable or supported trap
spaces and other types of models. These results show that the trap space semantics can provide a unified
semantic framework for NLPs. Note that there are historically different model-theoretic or dynamical
semantics for NLPs, and they are often defined in different ways [43, 35]. For convenience, let StPM(*P*)
 resp. SuPM(*P*) denote the set of stable (resp. supported) partial models of *P*; let StM(*P*) (resp. SuM(*P*)
denote the set of stable (resp. supported) models of *P*; and let RegM(*P*) denote the set of regular models
of *P*.
**4.1 Relationships with the Stable and Supported Class Semantics**

By leveraging the concept of stable or supported trap set underlying the trap space semantics, we correct a flaw in the existing alternative characterization of strict stable or supported classes proved in [27]. Due to space limitations, we refer the reader to Section B for the technical details.

We now prove a similar version of Lemma 3.1, but for stable trap sets instead of stable trap spaces. The proof technique is analogous to that of Lemma 3.1.

**Lemma 4.1.** Consider an NLP *P* and a non-empty set *S* of two-valued interpretations of *P*. If *S* is a stable trap set of *P*, then there exists a *⊆*-minimal stable trap set *S'* of *P* such that *S'* ⊆ *S*.

This is similar for supported trap sets:

**Lemma 4.2.** Given an NLP *P*, if a non-empty set *S* of two-valued interpretations of *P* is a supported trap set of *P*, then there exists a *⊆*-minimal supported trap set *S'* of *P* such that *S'* ⊆ *S*.

Based on Lemma 4.1, we obtain the following main result:

**Theorem 4.1 (main result).** Consider an NLP *P*. A non-empty set *S* of two-valued interpretations is a *⊆*-minimal stable trap set of *P* iff *S* is a strict stable class of *P*.

Analogously, based on Lemma 4.2, we obtain the following:

**Theorem 4.2.** Consider an NLP *P*. A non-empty set *S* of two-valued interpretations is a *⊆*-minimal supported trap set of *P* iff *S* is a strict supported class of *P*.

Theorem 4.1 and Theorem 4.2 immediately entail that every stable (resp. supported) trap space always covers at least one strict stable (resp. supported) class in an NLP:

**Corollary 4.1.** Consider an NLP *P*. For every stable (resp. supported) trap space *I* of *P*, *S*(*I*) contains at least one strict stable (resp. supported) class of *P*.

They also naturally entail the disjointness of two strict stable or supported classes:

**Proposition 4.1.** *Two distinct strict stable (resp. supported) classes of an NLP *P* are disjoint.*

In [4], the authors prove the disjointness of two strict stable classes in Datalog⁻ programs only. In [27], the authors prove the disjointness of two strict supported classes in Datalog⁻ programs only.

**4.2 Relationships with the Stable and Supported Partial Model Semantics**

We first establish a model-theoretic characterization for supported trap spaces in an NLP.

**Theorem 4.3 (main result).** Given an NLP *P*, *I* is a supported trap space of *P* iff *I*(rhs*<sub>P</sub>(*a*)) ≤*s* *I*(*a*) for every *a* ∈ HB*<sub>P</sub>*.

Theorem 4.3 also points out that a supported trap space may not be a three-valued model of comp(*P*), as it considers the order ≤*, whereas the completion considers the equivalence ↔. Indeed, given the NLP *P* of Example 2.2, let *I*₄ be the three-valued interpretation where *I*₄(*a*₀) = ⋆ and *I*₄(*a*) = 0 for every *a* ∈ HB*<sub>P</sub>* \ {*a*₀*}.

It is easy to verify that *I*₄ is a supported trap space but not a three-valued model of comp(*P*).

To reason about stable trap spaces, we apply the least fixpoint transformation, which always produces a negative NLP. We then show that for negative NLPs, the stable transition graph coincides with the supported transition graph, entailing the coincidence between stable and supported trap spaces.

**Theorem 4.4.** The stable and supported transition graphs of a negative NLP *P* are the same.
**Corollary 4.2.** Let P be a negative NLP. Then the set of stable trap spaces of P coincides with the set of supported trap spaces of P.

**Theorem 4.5** ([42]). Given a negative NLP P, then the set of stable partial models of P coincides with the set of supported partial models of P.

**Theorem 4.6** (Theorem 3.1 of [3]). Consider an NLP P. Let lfp(P) be the least fixpoint of P. Then P and lfp(P) have the same set of stable partial models, the same sets of regular models, and the same set of stable models.

Based on the property that $F_P(I) = F_{lfp(P)}(I)$ for any two-valued interpretation $I$, proved in [27], we directly obtain the following:

**Theorem 4.7.** Let P be an NLP and lfp(P) denote the least fixpoint of P. Then $\text{tg}_{\text{st}}(P) = \text{tg}_{\text{st}}(\text{lfp}(P))$, i.e., P and lfp(P) have the same stable transition graph.

Since stable trap spaces are defined based on the stable transition graph, the above result immediately implies the following:

**Corollary 4.3.** Let P be an NLP and lfp(P) denote the least fixpoint of P. Then P and lfp(P) have the same set of stable trap spaces.

By Theorem 4.3, it is easy to derive the following simple relationship between supported partial models and supported trap spaces of an NLP:

**Proposition 4.2.** Given an NLP P, if I is a supported partial model of P, then it is also a supported trap space of P.

By applying the least fixpoint transformation, we obtain a similar relationship:

**Proposition 4.3.** Given an NLP P, if I is a stable partial model of P, then it is also a stable trap space of P.

Next, we establish a deeper relationship between supported trap spaces and supported partial models. We start with defining a new concept as follows:

**Definition 4.1.** Consider an NLP P. We define a mapping $f_P: \text{SuTS}(P) \rightarrow \text{SuTS}(P)$ as follows: if $m$ is a supported trap space, then $f_P(m)(v) = m(\text{rhs}_P(v))$, $\forall v \in \text{HB}_P$. The mapping $f_P$ is well-defined because $f_P(m)$ is always a supported trap space if $m$ is a supported trap space (see Lemma 4.3).

We then show that the mapping $f_P$ preserves the supported trap space property:

**Lemma 4.3.** Given an NLP P and a supported trap space I of P, $f_P(I)$ is a supported trap space of P and $I \leq_i f_P(I)$.

By combining Lemma 4.3 and the use of Hartogs' lemma (see Lemma 2.3), we obtain the following main result:

**Theorem 4.8 (main result).** Consider an NLP P. For every supported trap space $I \in \text{SuTS}(P)$, there is a unique supported partial model $I' \in \text{SuPM}(P)$ such that $I' \leq_s I$.

The beauty of Theorem 4.8 is that the function $f_P$ delivers a unique supported partial model starting from any supported trap space. This insight is key to prove the following results.

**Corollary 4.4.** Consider an NLP P. A three-valued interpretation $I$ is a $\leq_s$-minimal supported partial model of P iff $I$ is a $\leq_s$-minimal supported trap space of P.
Corollary 4.4 is insightful as it indicates that, although the set of supported partial models may be different from the set of supported trap spaces, their $\leq_s$-minimal elements are the same. Hereafter, we show an interesting implication of the above relationships between supported trap spaces and supported partial models. We start by proving that a supported class that is included in a supported trap space is also included in the application of $f_P$ to this supported trap space:

**Lemma 4.4.** Consider an NLP *P*. Let *I* be a supported trap space of *P*. If *S* is a supported class of *P* such that $S \subseteq \mathcal{S}(*I*)$, then $S \subseteq \mathcal{S}(f_P(*I*))$.

We now prove the case of supported classes:

**Proposition 4.4.** Given an NLP *P*, if *S* is a supported class, then $\langle S \rangle_P^{sp}$ is a supported partial model.

This is similar for stable classes:

**Proposition 4.5.** Given an NLP *P*, if *S* is a stable class of *P*, then $\langle S \rangle_P^{st}$ is a stable partial model.

Proposition 4.4 (resp. Proposition 4.5) gives us deeper understanding about relationships between the supported (resp. stable) classes and supported (resp. stable) partial models of an NLP.

## 4.3 Relationships with the Regular Model Semantics

Recall that a stable trap space may not be a stable partial model. Indeed, given the NLP *P* of Example 2.2, let $I_4$ be the three-valued interpretation where $I_4(a_0) = \star$ and $I_4(a) = 0$ for every $a \in \text{HB}_P \setminus \{a_0\}$. It is easy to verify that $I_4$ is a stable trap space of *P*, but it is not a stable partial model of *P*. However, since every two-valued interpretation of *P* has an arc to $I_1$ in the stable transition graph of *P*, for every stable trap space *I* of *P*, $I(a) \neq 1$ for every $a \in \text{HB}_P$. This implies that $I_1$ is the $\leq_s$-minimal stable trap space of *P*. Since $I_1$ is also the regular model of *P*, we wonder if the set of regular models of *P* coincides with the set of $\leq_s$-minimal stable trap spaces of *P*, which if true is really interesting. We answer this question for NLPs as follows:

**Theorem 4.9 (main result).** Given an NLP *P*, a three-valued interpretation *I* is a regular model of *P* iff *I* is a $\leq_s$-minimal stable trap space of *P*.

By Corollary 4.1, Proposition 3.3, and Theorem 4.9, each regular model of an NLP contains at least one strict stable class of this NLP, which is a new insight to the best of our knowledge.

## 4.4 Relationships with the L-stable Model Semantics

We first define a new order on $\mathbb{B}_*$, which considers only the undefined value $\star$:

**Definition 4.2.** The order $\leq_u$ on $\mathbb{B}_*$ is given by $0 \leq_u 1$, $1 \leq_u 0$, $0 <_u \star$, $1 <_u \star$, and there is no other relation. Given two three-valued interpretations $I_1$ and $I_2$ of an NLP *P*, $I_1 \leq_u I_2$ iff $I_1(v) \leq_u I_2(v)$ for all $v \in \text{HB}_P$. It is easy to see that $I_1 \leq_u I_2$ implies $I_1 \leq_u I_2$.

**Proposition 4.6.** Given two three-valued interpretations $I_1$ and $I_2$ of an NLP *P*, $I_1 \leq_u I_2$ iff $I_1^u \subseteq I_2^u$.

Proposition 4.6 entails an equivalent definition for an L-stable model:

**Corollary 4.5.** Given an NLP *P*, *I* is an L-stable model iff it is a $\leq_u$-minimal stable partial model.

It is easy to derive that an L-stable model is also a regular model by Corollary 4.5 and the fact that $I_1 \leq_s I_2$ implies $I_1 \leq_u I_2$. However, the reverse might be not true in general. The relationship between $\leq_s$ and $\leq_u$ leads us to the following, which is similar to Theorem 4.8:
**Proposition 4.7.** Consider an NLP P. For every supported trap space $I \in \text{SuTS}(P)$, there is a supported partial model $J \in \text{SuPM}(P)$ such that $J \leq_u I$.

This property immediately implies that the $\leq_u$-minimal elements of the set of supported partial models and the set of supported trap spaces are the same.

**Corollary 4.6.** Consider an NLP P. A three-valued interpretation $I$ is a $\leq_u$-minimal supported partial model of P iff $I$ is a $\leq_u$-minimal supported trap space of P.

By using the least fixpoint transformation, we obtain the following equivalence:

**Theorem 4.10.** Given an NLP P, $I$ is an L-stable model iff $I$ is a $\leq_u$-minimal stable trap space.

Combining the above relationship, the least fixpoint transformation, and Theorem 4.9, we obtain the following:

**Proposition 4.8.** Given an NLP P, $I$ is an L-stable model of P iff $I$ is a $\leq_u$-minimal regular model.

The work by [35] shows that an L-stable model is a regular model. Proposition 4.8 provides a deeper relationship between the L-stable models and the regular models. Interestingly, this helps us to reveal the following insight:

**Corollary 4.7.** If an NLP P has no L-stable model, then it has infinitely many regular models.

# 5 Existence Results

Whether a given semantics is consistent (i.e., it contains at least one respective object) is a main property of interest [36, 38]. For Datalog$^-$ programs, proving or refuting this property is mostly straightforward [6]. However, for arbitrary NLPs with an infinite Herbrand base, conducting such proofs or refutations is more intricate. It often needs a precise use of set-theoretic axioms or equivalent statements. We here show that previous arguments for the existence of supported classes, strict supported (stable) classes, and regular models are either missing or imprecise; and that the trap space semantics can offer a unified and precise framework to prove the model or class existence. Furthermore, we reveal problems in the proof of [35] for the existence of L-stable models and correct it for uni-rule programs only (see more details in Section C).

We first recall a well-known result:

**Theorem 5.1 (Theorem 1 of [4]).** Any NLP P has a stable class.

The proof of Theorem 5.1 relies on the anti-monotonicity of $F_P$ and the monotonicity of $F_P^2$ to construct two two-valued interpretations that form a stable class. However, this approach may not be directly applicable to supported classes, as $T_P$ may be neither monotonic nor anti-monotonic. In [27, Proposition 5.6], the authors assert the guaranteed existence of stable and supported classes but do not provide formal proofs. While they state that “As explained in previous sections, existence of stable/supported classes is always guaranteed”, our analysis indicates that this claim is not clearly substantiated by the preceding discussions in their work. Relying on the existence of $\subseteq$-minimal stable (resp. supported) trap sets, which can be easily derived from Lemma 4.1 (resp. Lemma 4.2), we provide an alternative proof for the existence of stable classes (resp. a new proof for the existence of supported classes) in an NLP.

**Theorem 5.2.** An NLP P always has a $\subseteq$-minimal stable (or supported) trap set.

**Theorem 5.3.** Any NLP P has a supported class.
While the existence of stable classes is precisely proved in [4], there has been no formal proof for the existence of strict stable (supported) classes so far. The work by [5] considers (finite) stable classes and suggests that verifying the existence of strict stable classes in such cases is straightforward, but even under these constraints, the derivation is not always evident indeed. Thanks to the relationships with $\subseteq$-minimal stable (resp. supported) trap sets established in the previous section, we can easily derive the existence of strict stable (resp. supported) classes:

**Corollary 5.1 (main result).** An NLP *P* always has a strict stable (or supported) class.

The equivalence between the regular models and the $\leq_s$-minimal stable trap spaces (see Theorem 4.9) and the existence of $\leq_s$-minimal stable trap spaces (see Theorem 3.1) immediately entail the existence of regular models in an NLP:

**Corollary 5.2.** An NLP *P* always has a regular model.

[42, Proposition 5.1] proves the existence of regular models in an NLP by showing that the NLP has at least one justifiable model (i.e., stable partial model) and that $<_{undef} (\text{i.e.,} <_s)$ is a quasi-order (i.e., a transitive and reflexive relation) on the set of justifiable models. However, this argument is only valid for finite sets, whereas the set of stable partial models of an NLP can be infinite. An infinite set can have no minimal element in general (see more examples in [38]). For infinite sets, it should follow the axiom of choice or equivalent statements [6]. With our new semantics, we can have an elegant proof for the existence of regular models that is precise w.r.t. the use of set-theoretic axioms.

Note that for NLPs, regular models are equivalent to M-stable models [19]. Since the existence of M-stable models is proved in [35, Corollary 5.4], the existence of regular models immediately follows. Hence, our proof of Corollary 5.2 offers an alternative (perhaps simpler) for the proof of [35, Corollary 5.4].

# 6 Conclusion

In this paper, we introduce the *trap space semantics* as a novel and general framework for interpreting NLPs. Extending prior work on Datalog⁻ programs and their correspondence with Boolean networks, we generalize the concept of trap spaces to apply to arbitrary NLPs, including those with infinite Herbrand bases. This generalization provides a unified, semantics-based foundation that captures both model-theoretic and dynamical perspectives on NLPs.

We formally define the trap space semantics and established its foundational properties. Notably, we demonstrate that it encompasses and connects existing model-theoretic and dynamical semantics. Through this unification, the trap space semantics clarifies the relationships among these diverse approaches and provides a systematic means to compare and interpret them. See Figure 2 for a summary of the main relationships shown in Section 4.

Another significant contribution is the use of the trap space semantics as a unified framework for establishing existence results. We demonstrate how this framework enables rigorous proofs of the existence of supported classes, strict supported classes, strict stable classes, and regular models—results which were previously either absent or only informally stated in the literature.

More broadly, the trap space semantics advances the field by offering a conceptual bridge between the model-theoretic and dynamical views of NLPs. It allows us to reason simultaneously about fixed points of semantics-based operators and the dynamical behavior of NLPs over time. This duality opens up new avenues for understanding the behavior of NLPs comprehensively.

Looking forward, future research should focus on extending the trap space semantics to richer classes of programs, such as disjunctive logic programs, constraint logic programs, and extended logic programs.
<figure><img src="image_4.png" /><figcaption>Figure 2: Summary of the main relationships shown in Section 4. A full arc indicates a set-inclusion relation, whereas a dashed line along with a box indicate the relationship between the two end vertices.</figcaption></figure>

Furthermore, there are many other semantic proposals, for example, those that consider abstract properties such as cumulativity [15, 16]. Relating the trap space semantics to such semantics is interesting and can help clarify the semantic landscape. Finally, it is worth exploring the semantics’ applications in areas that benefit from the interplay between logic and dynamics, including knowledge representation, verification, and systems biology.

## References

[1] Krzysztof R Apt & Marc Bezem (1991): *Acyclic programs*. New Gener. Comput. 9, pp. 335–363, doi:10.1007/BF03037168.

[2] Krzysztof R Apt, Howard A Blair & Adrian Walker (1988): *Towards a theory of declarative knowledge*. In: *Foundations of Deductive Databases and Logic Programming*, Elsevier, San Francisco, pp. 89–148.

[3] Chandrabose Aravindan & Phan Minh Dung (1995): *On the Correctness of Unfold/Fold Transformation of Normal and Extended Logic Programs*. J. Log. Program. 24(3), pp. 201–217, doi:10.1016/0743-1066(94)00104-E.

[4] Chitta Baral & V. S. Subrahmanian (1992): *Stable and Extension Class Theory for Logic Programs and Default Logics*. J. Autom. Reason. 8(3), pp. 345–366, doi:10.1007/BF02341854.
[5] Chitta Baral & V. S. Subrahmanian (1993): *Dualities Between Alternative Semantics for Logic Programming and Nonmonotonic Reasoning*. J. Autom. Reason. 10(3), pp. 399–420, doi:10.1007/BF00881799.

[6] Ringo Baumann & Christof Spanring (2015): *Infinite argumentation frameworks: On the existence and uniqueness of extensions*. In: *Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation: Essays Dedicated to Gerhard Brewka on the Occasion of his 60th Birthday*, Springer, Cham, pp. 281–295, doi:10.1007/978-3-319-14726-0_19.

[7] Belaid Benhamou & Pierre Siegel (2012): *A New Semantics for Logic Programs Capturing and Extending the Stable Model Semantics*. In: *Proc. of ICTAI*, IEEE Computer Society, Athens, Greece, pp. 572–579, doi:10.1109/ICTAI.2012.167.

[8] Howard A. Blair, Fred Dushin & Paul R. Humenn (1997): *Simulations between Programs as Cellular Automata*. In: *Proc. of LPNMR*, Springer, Berlin, Heidelberg, pp. 115–131, doi:10.1007/3-540-63255-7_9.

[9] Martin Caminada, Samy Sá, João F. L. Alcântara & Wolfgang Dvorák (2015): *On the equivalence between logic programming semantics and argumentation semantics*. Int. J. Approx. Reason. 58, pp. 87–111, doi:10.1016/J.IJAR.2014.12.004.

[10] Martin Caminada & Claudia Schulz (2017): *On the Equivalence between Assumption-Based Argumentation and Logic Programming*. J. Artif. Intell. Res. 60, pp. 779–825, doi:10.1613/JAIR.5581.

[11] Martin W. A. Caminada & Dov M. Gabbay (2009): *A Logical Account of Formal Argumentation*. Stud Logica 93(2-3), pp. 109–145, doi:10.1007/S11225-009-9218-X.

[12] Stefano Ceri, Georg Gottlob & Letizia Tanca (1990): *Logic Programming and Databases: An Overview*. Springer, Berlin, doi:10.1007/978-3-642-83952-8.

[13] Keith L. Clark (1977): *Negation as Failure*. In: *Logic and Data Bases, Symposium on Logic and Data Bases*, Plemum Press, New York, pp. 293–322, doi:10.1007/978-1-4684-3384-5_11.

[14] Emmanuelle-Anna Dietz, Steffen Hölldobler & Christoph Wernhard (2014): *Modeling the suppression task under weak completion and well-founded semantics*. J. Appl. Non Class. Logics 24(1-2), pp. 61–85, doi:10.1080/11663081.2014.911520.

[15] Jürgen Dix (1995): *A Classification Theory of Semantics of Normal Logic Programs: I. Strong Properties*. Fundam. Informaticae 22(3), pp. 227–255, doi:10.3233/FI-1995-2233.

[16] Jürgen Dix (1995): *A Classification Theory of Semantics of Normal Logic Programs: II. Weak Properties*. Fundam. Informaticae 22(3), pp. 257–288, doi:10.3233/FI-1995-2234.

[17] Phan Minh Dung (1995): *On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games*. Artif. Intell. 77(2), pp. 321–358, doi:10.1016/0004-3702(94)00041-X.

[18] Phan Minh Dung & Kanchana Kanchanasut (1989): *A Fixpoint Approach to Declarative Semantics of Logic Programs*. In: *Proc. of NACLP*, MIT Press, Cleveland, Ohio, pp. 604–625.

[19] Thomas Eiter, Nicola Leone & Domenico Saccà (1997): *On the Partial Semantics for Disjunctive Deductive Databases*. Ann. Math. Artif. Intell. 19(1-2), pp. 59–96, doi:10.1023/A:1018947420290.

[20] François Fages (1994): *Consistency of Clark's completion and existence of stable models*. Methods Log. Comput. Sci. 1(1), pp. 51–60.

[21] François Fages (1991): *A New Fixpoint Semantics for General Logic Programs Compared with the Well-Founded and the Stable Model Semantics*. New Gener. Comput. 9(3/4), pp. 425–444, doi:10.1007/BF03037172.

[22] Allen Van Gelder, Kenneth A. Ross & John S. Schlipf (1988): *Unfounded Sets and Well-Founded Semantics for General Logic Programs*. In: *Proc. of ACM SIGACT-SIGMOD-SIGART*, ACM, Austin, Texas, pp. 221–230, doi:10.1145/308386.308444.

[23] Allen Van Gelder, Kenneth A. Ross & John S. Schlipf (1991): *The Well-Founded Semantics for General Logic Programs*. J. ACM 38(3), pp. 620–650, doi:10.1145/116825.116838.
[24] Michael Gelfond & Vladimir Lifschitz (1988): *The Stable Model Semantics for Logic Programming*. In: Proc. of ICLP/SLP, MIT Press, Seattle, pp. 1070–1080.

[25] Paul Richard Halmos (1960): *Naive set theory*. van Nostrand, New York, doi:10.1007/978-1-4757-1645-0.

[26] F. Hartogs (1915): *Über das Problem der Wohlordnung*. Mathematische Annalen 76(4), p. 438–443, doi:10.1007/bf01458215.

[27] Katsumi Inoue & Chiaki Sakama (2012): *Oscillating Behavior of Logic Programs*. In: Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Springer, Berlin, pp. 345–362, doi:10.1007/978-3-642-30743-0_23.

[28] Hannes Klarner, Alexander Bockmayr & Heike Siebert (2015): *Computing maximal and minimal trap spaces of Boolean networks*. Nat. Comput. 14(4), pp. 535–544, doi:10.1007/S11047-015-9520-7.

[29] Dénes König (1990): *Theory of finite and infinite graphs*. In: Theory of Finite and Infinite Graphs, Springer, Birkhäuser Boston, MA, pp. 45–421, doi:10.1007/978-1-4684-8971-2.

[30] John Wylie Lloyd (1984): *Foundations of Logic Programming*. Springer, Berlin Heidelberg, doi:10.1007/978-3-642-96826-6.

[31] V. Wiktor Marek & V. S. Subrahmanian (1992): *The Relationship Between Stable, Supported, Default and Autoepistemic Semantics for General Logic Programs*. Theor. Comput. Sci. 103(2), pp. 365–386, doi:10.1016/0304-3975(92)90019-C.

[32] David Pearce (2006): *Equilibrium logic*. Ann. Math. Artif. Intell. 47(1), pp. 3–41, doi:10.1007/s10472-006-9028-z.

[33] Teodor C. Przymusinski (1990): *The Well-Founded Semantics Coincides with the Three-Valued Stable Semantics*. Fundam. Inform. 13(4), pp. 445–463, doi:10.3233/FI-1990-13404.

[34] Teodor C. Przymusinski (1994): *Well-founded and Stationary Models of Logic Programs*. Ann. Math. Artif. Intell. 12(3-4), pp. 141–187, doi:10.1007/BF01530784.

[35] Domenico Saccà & Carlo Zaniolo (1997): *Deterministic and Non-Deterministic Stable Models*. J. Log. Comput. 7(5), pp. 555–579, doi:10.1093/LOGCOM/7.5.555.

[36] Taisuke Sato (1990): *Completed Logic Programs and their Consistency*. J. Log. Program. 9(1), pp. 33–44, doi:10.1016/0743-1066(90)90032-Z.

[37] J. Seitzer & John S. Schlipf (1997): *Affordable Classes of Normal Logic Programs*. In: Proc. of LPNMR, Springer, Berlin, Heidelberg, pp. 92–111, doi:10.1007/3-540-63255-7_7.

[38] Christof Spanring (2017): *Set- and graph-theoretic investigations in abstract argumentation*. Ph.D. thesis, University of Liverpool, UK. Available at https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.755437.

[39] Van-Giang Trinh, Belaid Benhamou & Sylvain Soliman (2023): *Trap spaces of Boolean networks are conflict-free siphons of their Petri net encoding*. Theor. Comput. Sci. 971, p. 114073, doi:10.1016/j.tcs.2023.114073.

[40] Van-Giang Trinh, Belaid Benhamou, Sylvain Soliman & François Fages (2025): *On the Boolean Network Theory of Datalog*. arXiv:2504.15417. https://arxiv.org/abs/2504.15417.

[41] Yining Wu, Martin Caminada & Dov M. Gabbay (2009): *Complete Extensions in Argumentation Coincide with 3-Valued Stable Models in Logic Programming*. Stud Logica 93(2-3), pp. 383–403, doi:10.1007/S11225-009-9210-5.

[42] Jia-Huai You & Li-Yan Yuan (1994): *A Three-Valued Semantics for Deductive Databases and Logic Programs*. J. Comput. Syst. Sci. 49(2), pp. 334–361, doi:10.1016/S0022-0000(05)80053-4.

[43] Jia-Huai You & Li-Yan Yuan (1995): *On the Equivalence of Semantics for Normal Logic Programs*. J. Log. Program. 22(3), pp. 211–222, doi:10.1016/0743-1066(94)00023-Y.

[44] Max Zorn (1935): *A remark on method in transfinite algebra*. Bull. Am. Math. Soc. 41(10), pp. 667–670.
# A Detailed Proofs

This appendix shows the detailed proofs of the results shown in the main text of the present paper.

**Proposition 3.1.** An NLP *P* always has a stable or supported trap space.

*Proof.* Let $I^*$ be a three-valued interpretation that corresponds to all the two-valued interpretations, i.e., $\forall a \in HB_P, I^*(a) = \star$. By setting $S = \mathcal{S}(I^*)$, the condition $\{F_P(I) \mid I \in S\} \subseteq S$ (resp. $\{T_P(I) \mid I \in S\} \subseteq S$) always holds. Hence, $\mathcal{S}(I^*)$ is a stable (resp. supported) trap set of *P*. By definition, $I^*$ is a stable (resp. supported) trap space of *P*.

**Lemma 3.1.** Consider an NLP *P* and a three-valued interpretation *J* of *P*. If *J* is a stable trap space of *P*, then there exists a $\leq_s$-minimal stable trap space *J'* of *P* such that $J' \leq_s J$.

*Proof.* Clearly, $(\mathrm{StTS}(P), \leq_i)$ is a partially ordered set. Consider a $\leq_i$-chain $(E_k)_{k \in I}$. Note that *I* is the set of all elements of the $\leq_i$-chain, and it can be written as an indexed family, which can be done via using the set itself as index set. Consider now the intersection of all elements in *I*, said $\sqcap_I$ whose existence is guaranteed by Definition 3.5. Following from the definition, we have $\mathcal{S}(\sqcap_I) = \bigcap_{k \in I} \mathcal{S}(E_k)$. It follows that $\sqcap_I \leq_s E_k$ for all $E_k, k \in I$. Equivalently, $E_k \leq_i \sqcap_I$ for all $E_k, k \in I$, implying that $\sqcap_I$ is an upper bound w.r.t. $\leq_i$ of $(E_k)_{k \in I}$. It remains to show that $\sqcap_I$ is a stable trap space of *P*.

Consider a two-valued interpretation *A* of *P*. Let *B* be the successor of *A* in $\mathrm{tg}_{\mathrm{st}}(P)$, i.e., $B = F_P(A)$. Assume that $A \in \mathcal{S}(\sqcap_I)$. Then for all $k \in I$, we have that $A \in \mathcal{S}(E_k)$. Thus $B \in \mathcal{S}(E_k)$, since $E_k$ is a stable trap space. Hence, $B \in \mathcal{S}(\sqcap_I)$. This implies that if $A \in \mathcal{S}(\sqcap_I)$ then $F_P(A) \in \mathcal{S}(\sqcap_I)$, thus $\sqcap_I$ is a stable trap set of *P*. Since $\sqcap_I$ is a three-valued interpretation by definition, it is a stable trap space of *P*.

By definition, a $\leq_s$-minimal stable trap space is equivalent to a $\leq_i$-maximal stable trap space. By Lemma 2.2, if *J* is a stable trap space of *P*, then there exists a $\leq_s$-minimal stable trap space *J'* of *P* such that $J \leq_i J'$ (equivalently, $J' \leq_s J$).

**Lemma 3.2.** Consider an NLP *P* and a three-valued interpretation *J* of *P*. If *J* is a supported trap space of *P*, then there exists a $\leq_s$-minimal supported trap space *J'* of *P* such that $J' \leq_s J$.

*Proof.* The proof of Lemma 3.2 can be applied here by substituting $F_P(A)$ in Lemma 3.1 with $T_P(A)$. $\square$

**Theorem 3.1 (main result).** Any NLP *P* has a $\leq_s$-minimal stable (resp. supported) trap space.

*Proof.* For the case of $\leq_s$-minimal stable trap spaces, this immediately follows from Lemma 3.1 and the fact that *P* has at least one stable trap space by Proposition 3.1.

For the case of $\leq_s$-minimal supported trap spaces, this immediately follows from Lemma 3.2 and the fact that *P* has at least one supported trap space by Proposition 3.1. $\square$

**Proposition 3.2.** Consider an NLP *P*. Let *S* be a non-empty set of two-valued interpretations of *P*. Then there is a unique $\leq_s$-minimal stable (resp. supported) trap space, denoted by $\langle S \rangle_P^{st}$ (resp. $\langle S \rangle_P^{sp}$), covering *S*, i.e., $S \subseteq \mathcal{S}(\langle S \rangle_P^{st})$ (resp. $S \subseteq \mathcal{S}(\langle S \rangle_P^{sp})$).

*Proof.* Hereafter, we prove the case of stable trap spaces. The proof for the case of supported trap spaces is analogous. Let *T* be the set of all stable trap spaces *I* such that $S \subseteq \mathcal{S}(I)$. The set *T* is non-empty as it contains $\varepsilon$ that is a stable trap space in which all atoms are assigned to $\star$ (see Proposition 3.1). Since *S* is non-empty, the elements in *T* are mutually consistent, thus we can take the intersection of all these elements said $\sqcap_T$.
Next, we show that $\sqcap_T$ is also a stable trap space of P. Consider a two-valued interpretation A of P. Let B be the successor of A in $\text{tg}_{\text{st}}(P)$, i.e., $B = F_P(A)$. Assume that $A \in \mathcal{S}(\sqcap_T)$. Then for all $E_k \in T$, we have that $A \in \mathcal{S}(E_k)$. Thus $B \in \mathcal{S}(E_k)$, since $E_k$ is a stable trap space. Hence, $B \in \mathcal{S}(\sqcap_T)$. This implies that if $A \in \mathcal{S}(\sqcap_T)$ then $F_P(A) \in \mathcal{S}(\sqcap_T)$, thus $\sqcap_T$ is a stable trap set of P. Since $\sqcap_T$ is a three-valued interpretation by definition, it is a stable trap space of P.

By definition, $\sqcap_T$ is unique and $\leq_S$-minimal. Since $S \subseteq \mathcal{S}(E_k)$ for all $E_k \in T$, $S \subseteq \mathcal{S}(\sqcap_T)$. By setting $\langle S \rangle_P^{\text{st}} = \sqcap_T$, we can conclude the proof. $\square$

**Proposition 3.3.** *Consider an NLP P. Let $I_1$ and $I_2$ be two distinct $\leq_S$-minimal stable (resp. supported) trap spaces of P. Then $I_1$ and $I_2$ are not consistent.*

*Proof.* Hereafter, we prove the case of stable trap spaces. The proof for the case of supported trap spaces is analogous. Assume that $I_1$ and $I_2$ are consistent. Then $I = \sqcap_{i \in I} \{I_1, I_2\}$ exists and $\mathcal{S}(I) = \mathcal{S}(I_1) \cap \mathcal{S}(I_2)$. By similarly applying the arguments of Proposition 3.2, we have *I* is also a stable trap space of *P*. Since $I_1$ and $I_2$ are distinct, we have $\mathcal{S}(I_1) \subset \mathcal{S}(I)$ or $\mathcal{S}(I_2) \subset \mathcal{S}(I)$ must hold. This leads to a contradiction because $I_1$ and $I_2$ are $\leq_S$-minimal stable trap spaces of *P*. Hence, $I_1$ and $I_2$ are not consistent. $\square$

**Lemma 4.1.** *Consider an NLP P and a non-empty set *S* of two-valued interpretations of *P*. If *S* is a stable trap set of *P*, then there exists a *⊆*-minimal stable trap set *S'* of *P* such that *S'* $\subseteq$ *S*.*

*Proof.* Let $TS(P)$ denote the set of all stable trap sets of $P$. Clearly, $(TS(P), \supseteq)$ is a partially ordered set. Given a $\supseteq$-chain $(E_i)_{i \in I}$. Note that $I$ is the set of all elements of the $\supseteq$-chain, and it can be written as an indexed family, which can be done via using the set itself as index set. Consider now $E = \bigcap_{i \in I} E_i$. Obviously, $E$ is an upper bound of $(E_i)_{i \in I}$, i.e., $E_i \supseteq E$, for all $i \in I$. It remains to show that $E$ is a stable trap set of $P$.

Consider a two-valued interpretation A. $A \in E$ iff $A \in E_i, \forall i \in I$. This implies that $F_P(A) \in E_i, \forall i \in I$ since $E_i$ is a stable trap set of P. Then $F_P(A) \in E$. This implies that $\{F_P(B) | B \in E\} \subseteq E$. By definition, $E$ is a stable trap set of P.

By definition, $\subseteq$-minimal stable trap set is equivalent to a $\supseteq$-maximal stable trap set. By Lemma 2.2, if *S* is a stable trap set of *P*, then there exists a $\subseteq$-minimal stable trap set *S'* of *P* such that *S* $\supseteq$ *S'* (equivalently, *S'* $\subseteq$ *S*). $\square$

**Lemma 4.2.** *Given an NLP P, if a non-empty set *S* of two-valued interpretations of *P* is a supported trap set of *P*, then there exists a *subseteq*-minimal supported trap set *S'* of *P* such that *S'* $\subseteq$ *S*.*

*Proof.* The proof of Lemma 4.1 can be applied here by substituting $F_P(I)$ in Lemma 4.1 with $T_P(I)$. $\square$

**Theorem 4.1 (main result).** *Consider an NLP P. A non-empty set *S* of two-valued interpretations is a *subseteq*-minimal stable trap set of *P* iff *S* is a strict stable class of *P*.*

*Proof.* “⇒” Assume that *S* is a *subseteq*-minimal stable trap set of *P*. Then {$F_P(I) | I \in S$} $\subseteq$ *S* by definition. Suppose that {$F_P(I) | I \in S$} $\subsetneq$ *S*. Then there exists *J* $\in S$ such that for all *I* $\in S$, $F_P(I) \neq J$. We have {$F_P(I) | I \in S \setminus \{J\}$} $\subseteq$ {$F_P(I) | I \in S$} $\subseteq$ *S* $\setminus \{J\}$. Thus *S* $\setminus \{J\}$ is a stable trap set of *P*, which contradicts the *subseteq*-minimality of *S*. Hence {$F_P(I) | I \in S$} = *S*, i.e., *S* is a stable class of *P*. Since a stable class is a stable trap set, *S* must be a strict stable class.

“ ⇐ ” Assume that S is a strict stable class of P. Then {F<sub>P</sub>(I) | I ∈ S} = S by definition. This implies that S is a stable trap set of P. By Lemma 4.1, there is a ⊆-minimal stable trap set S' such that S' ⊆ S. We have {F<sub>P</sub>(I) | I ∈ S'} ⊆ S' by definition. Suppose that {F<sub>P</sub>(I) | I ∈ S'} ⊈ S'. Then there is J ∈ S' such
that $F_P(I) \neq J$ for all $I \in S'$. We have $\{F_P(I) \mid I \in S' \setminus \{J\}\} \subseteq \{F_P(I) \mid I \in S'\} \subseteq S' \setminus \{J\}$. By definition, $S' \setminus \{J\}$ is a stable trap set of $P$, which contradicts the $\subseteq$-minimality of $S'$. Thus, $\{F_P(I) \mid I \in S'\} = S'$, i.e., $S'$ is a stable class of $P$. $S$ is a strict stable class of $P$, thus $S = S'$ because of the $\subseteq$-minimality of a strict stable class. Hence, $S$ is a $\subseteq$-minimal stable trap set of $P$. $\square$

**Theorem 4.2.** *Consider an NLP P. A non-empty set *S* of two-valued interpretations is a *subseteq*-minimal supported trap set of *P* iff *S* is a strict supported class of *P*.*

*Proof.* The proof of Theorem 4.1 can be applied here by substituting $F_P(I)$ and Lemma 4.1 in Theorem 4.1 with $T_P(I)$ and Lemma 4.2, respectively. $\square$

**Corollary 4.1.** *Consider an NLP P. For every stable (resp. supported) trap space *I* of *P*, *S*(*I*) contains at least one strict stable (resp. supported) class of *P*.*

*Proof.* Assume that *I* is a stable trap space of *P*. By definition, *S*(*I*) is a stable trap set of *P*. There exists a *subseteq*-minimal stable trap set $S' \subseteq S*(*I*)$. By Theorem 4.1, $S'$ is also a strict stable class of *P*.

Assume that *I* is a supported trap space of *P*. By definition, *S*(*I*) is a supported trap set of *P*. There exists a *subseteq*-minimal supported trap set $S' \subseteq S*(*I*)$. By Theorem 4.2, $S'$ is also a strict supported class of *P*. $\square$

**Proposition 4.1.** *Two distinct strict stable (resp. supported) classes of an NLP P are disjoint.*

*Proof.* We prove the case of strict stable classes first.

Let $S_1$ and $S_2$ be two distinct strict stable classes of $P$. By Theorem 4.1, $S_1$ and $S_2$ are two distinct $\subseteq$-minimal stable trap sets of $P$. Assume that $S_1$ and $S_2$ are not disjoint. It follows that $S_1 \cap S_2 \neq \emptyset$. Consider $I \in S_1 \cap S_2$. We have $I \in S_1$ and $I \in S_2$, then $F_P(I) \in S_1$ and $F_P(I) \in S_2$ because $S_1$ and $S_2$ are stable trap sets, thus $F_P(I) \in S_1 \cap S_2$. It follows that $S_1 \cap S_2$ is a stable trap set of $P$. Then $S_1 \cap S_2 \subseteq S_1$ or $S_1 \cap S_2 \subseteq S_2$ must hold because $S_1 \neq S_2$, which contradicts the $\subseteq$-minimality of $S_1$ and $S_2$. Hence, $S_1$ and $S_2$ are disjoint.

For the case of strict supported classes, we only need to replace $F_P$ and Theorem 4.1 with $T_P$ and Theorem 4.2, respectively. $\square$

**Theorem 4.3 (main result).** *Given an NLP P, *I* is a supported trap space of *P* iff $I(\text{rhs}_P(a)) \leq_s I(a)$ for every $a \in \text{HB}_P$.*

*Proof.* “⇒” Assume that *I* is a supported trap space of *P*. Suppose that there is an atom *a* ∈ HB<sub>P</sub> such that *I*(*a*) <sub>*s*</sub> *I*(*rhs*<sub>*P*</sub>(*a*)). By the definition of the order <sub>*s*</sub>, we have *I*(*rhs*<sub>*P*</sub>(*a*)) = ⋆ and *I*(*a*) ≠ ⋆. Since *I*(*rhs*<sub>*P*</sub>(*a*)) = ⋆, there exists a two-valued interpretation *J* ∈ S*(*I*) such that *J*(*rhs*<sub>*P*</sub>(*a*)) = ¬*I*(*a*). By definition, *T*<sub>*P*</sub>(*J*)(*a*) = *J*(*rhs*<sub>*P*</sub>(*a*)), thus *T*<sub>*P*</sub>(*J*) does not belong to S*(*I*). This implies that S*(*I*) is not a supported trap set by definition, which is a contradiction. Hence, *I*(*rhs*<sub>*P*</sub>(*a*)) ≤<sub>*s*</sub> *I*(*a*) for every *a* ∈ HB<sub>*P*</sub>.

“⇔” Assume that $I(\text{rhs}_P(a)) \leq_s I(a)$ for every atom $a \in \text{HB}_P$. Let $A$ be a two-valued interpretation in $S*(*I*)$. Of course, $A \leq_s I$. By the characteristics of the three-valued logic, we have $A(\text{rhs}_P(a)) \leq_s I(\text{rhs}_P(a))$, then $A(\text{rhs}_P(a)) \leq_s I(a)$ for every $a \in \text{HB}_P$. This implies that $T_P(A) \leq_s I$, thus $T_P(A) \in S*(*I*)$. Hence, $S*(*I*)$ is a supported trap set of $P$. By definition, $I$ is a supported trap space of $P$. $\square$

**Theorem 4.4.** *The stable and supported transition graphs of a negative NLP P are the same.*

*Proof.* It has been shown in [27] that for any two-valued interpretation *I*, $F_P(I) = T_P(I)$, if *P* is a negative NLP. By the definitions of stable and supported transition graphs, we have that $\text{tg}_{st}(P) = \text{tg}_{sp}(P)$. $\square$
**Corollary 4.2.** Let P be a negative NLP. Then the set of stable trap spaces of P coincides with the set of supported trap spaces of P.

*Proof.* This immediately follows from Theorem 4.4. □

**Theorem 4.7.** Let P be an NLP and lfp(P) denote the least fixpoint of P. Then tg<sub>st</sub>(P) = tg<sub>st</sub>(lfp(P)), i.e., P and lfp(P) have the same stable transition graph.

*Proof.* It has been shown in [27] that for any two-valued interpretation I, we have that $F_P(I) = F_{lfp(P)}(I)$. By the definition of stable transition graph, we have that $tg_{st}(P) = tg_{st}(lfp(P))$. □

**Corollary 4.3.** Let P be an NLP and lfp(P) denote the least fixpoint of P. Then P and lfp(P) have the same set of stable trap spaces.

*Proof.* This immediately follows from Theorem 4.7. □

**Proposition 4.2.** Given an NLP P, if I is a supported partial model of P, then it is also a supported trap space of P.

*Proof.* Assume that I is a supported partial model of P. Then I is a three-valued model of comp(P). It follows that $I(a) = I(\text{rhs}_P(a))$, $\forall a \in \text{HB}_P$. Thus, I also satisfies the condition $I(\text{rhs}_P(a)) \leq_s I(a)$, $\forall a \in \text{HB}_P$. By Theorem 4.3, I is also a supported trap space of P. □

**Proposition 4.3.** Given an NLP P, if I is a stable partial model of P, then it is also a stable trap space of P.

*Proof.* Assume that I is a stable partial model of P. Then I is also a stable partial model of lfp(P) by Theorem 4.6. Since lfp(P) is a negative NLP, I is also a supported partial model of lfp(P) by Theorem 4.5. By Proposition 4.2, I is a supported trap space of lfp(P). By Corollary 4.2, I is also a stable trap space of lfp(P). By Corollary 4.3, I is a stable trap space of P. □

**Lemma 4.3.** Given an NLP P and a supported trap space I of P, $f_P(I)$ is a supported trap space of P and $I \leq_i f_P(I)$.

*Proof.* By definition, $f_P(I)(v) = I(\text{rhs}_P(v))$ for all $v \in \text{HB}_P$. Since I is a supported trap space of P, $I(v) \leq_i I(\text{rhs}_P(v))$ for all $v \in \text{HB}_P$ by Theorem 4.3. Thus, $I \leq_i f_P(I)$. Then, by the truth table of the three-valued logic, $I(\text{rhs}_P(v)) \leq_i f_P(I)(\text{rhs}_P(v))$ for all $v \in \text{HB}_P$. This implies that $f_P(I)(v) \leq_i f_P(I)(\text{rhs}_P(v))$ for all $v \in \text{HB}_P$. Hence, $f_P(I)$ is a supported trap space of P by Theorem 4.3. □

**Theorem 4.8 (main result).** Consider an NLP P. For every supported trap space I ∈ SuTS(P), there is a unique supported partial model I' ∈ SuPM(P) such that $I' \leq_s I$.

*Proof.* We define a function K recursively on the ordinals as follows:

$$K(0) = I$$ 
$$K(\alpha + 1) = f_P(K(\alpha)).$$

If $\beta$ is a limit ordinal, then by construction and Lemma 4.3 {$K(\alpha) : \alpha < \beta$} is a chain w.r.t. $\leq_i$ in SuTS(P). Define $K(\beta) = \sup_{\leq_i} \{K(\alpha) : \alpha < \beta\}$, where $\sup_{\leq_i}$ denotes the least upper bound w.r.t. $\leq_i$.
We have $K$ is an increasing function from the ordinals into $\text{SuTS}(P)$. It cannot be strictly increasing, as if it was, then we would have an injection from the ordinals into $\text{SuTS}(P)$, which violates Lemma 2.3. Hence, $K$ must be eventually constant. It follows that for some ordinal $\alpha$, $K(\alpha + 1) = K(\alpha)$, then $f_P(K(\alpha)) = K(\alpha)$. Let $\alpha^*$ be the least ordinal such that $K(\alpha^* + 1) = K(\alpha^*)$. We have $K(\beta) = K(\alpha^*)$ for all $\beta > \alpha^*$. Hence, $K(\alpha^*)$ is unique. Set $I' = K(\alpha^*)$. We have $f_P(I') = I'$, i.e., $I'$ is a three-valued model of $\text{comp}(P)$. Therefore, $I' \in \text{SuPM}(P)$. By construction and Lemma 4.3, $I \leq_I I'$. This implies that $I' \leq_I I$. $\square$

**Corollary 4.4.** Consider an NLP $P$. A three-valued interpretation $I$ is a $\leq_s$-minimal supported partial model of $P$ iff $I$ is a $\leq_s$-minimal supported trap space of $P$.

*Proof.* Recall that $\text{SuTS}(P)$ (resp. $\text{SuPM}(P)$) denotes the set of all supported trap spaces (resp. partial models) of $P$. We have $\text{SuPM}(P) \subseteq \text{SuTS}(P)$ by Proposition 4.2.

“⇒” Assume that $I$ is not a $\leq_s$-minimal supported trap space of $P$. Then there exists $I' \in \text{SuTS}(P)$ such that $I' <_s I$. By Theorem 4.8, there exists $J \in \text{SuPM}(P)$ such that $J \leq_I I'$. This implies that $J <_s I$, which contradicts the $\leq_s$-minimality of $I$. Hence, $I$ is a $\leq_s$-minimal supported trap space of $P$.

“←” This direction is trivial because $\text{SuPM}(P) \subseteq \text{SuTS}(P)$. $\square$

**Lemma 4.4.** Consider an NLP $P$. Let $I$ be a supported trap space of $P$. If $S$ is a supported class of $P$ such that $S \subseteq \mathcal{S}(I)$, then $S \subseteq \mathcal{S}(f_P(I))$.

*Proof.* Consider $J \in S$. Since $S \subseteq \mathcal{S}(I)$, we have $J \in \mathcal{S}(I)$. Let $J' = T_P(J)$. For any atom $a \in \text{HB}_P$, we have $J'(a) = J(\text{rhs}_P(a)) \leq_S I(\text{rhs}_P(a)) = f_P(I)(a)$. This implies that $J' \in \mathcal{S}(f_P(I))$. Hence, $\{T_P(J) \mid J \in S\} \subseteq \mathcal{S}(f_P(I))$. Since $S$ is a supported class, $\{T_P(J) \mid J \in S\} = S$ by definition. This implies that $S \subseteq \mathcal{S}(f_P(I))$. $\square$

**Proposition 4.4.** Given an NLP $P$, if $S$ is a supported class, then $\langle S \rangle_P^{sp}$ is a supported partial model.

*Proof.* By Proposition 3.2, $\langle S \rangle_P^{sp}$ is a supported trap space of $P$. Assume that it is not a supported partial model of $P$. Then by definition, we have $f_P(\langle S \rangle_P^{sp}) \neq \langle S \rangle_P^{sp}$. By Lemma 4.3, $f_P(\langle S \rangle_P^{sp}) \leq_S \langle S \rangle_P^{sp}$. It follows that $f_P(\langle S \rangle_P^{sp}) <_S \langle S \rangle_P^{sp}$. By Lemma 4.4, $S \subseteq \mathcal{S}(f_P(\langle S \rangle_P^{sp}))$ because $S$ is a supported class and $S \subseteq \mathcal{S}(\langle S \rangle_P^{sp})$ by definition. This implies that $\langle S \rangle_P^{sp}$ is not a $\leq_s$-minimal supported trap space covering $S$, which is a contradiction. Hence, $\langle S \rangle_P^{sp}$ is a supported partial model of $P$. $\square$

**Proposition 4.5.** Given an NLP $P$, if $S$ is a stable class of $P$, then $\langle S \rangle_P^{st}$ is a stable partial model.

*Proof.* By Theorem 4.7 and Theorem 4.4, $\text{tg}_{\text{st}}(P) = \text{tg}_{\text{st}}(\text{lfp}(P)) = \text{tg}_{\text{sp}}(\text{lfp}(P))$. Hence, $S$ is a supported class of $\text{lfp}(P)$. In addition, $\langle S \rangle_P^{st} = \langle S \rangle_{\text{lfp}(P)}^{sp}$. By Proposition 4.4, $\langle S \rangle_{\text{lfp}(P)}^{sp}$ is a supported partial model of $\text{lfp}(P)$. It is also a stable partial model of $\text{lfp}(P)$ by Theorem 4.5, since $\text{lfp}(P)$ is negative. By Theorem 4.6, $\langle S \rangle_P^{st}$ is a stable partial model of $P$. $\square$

**Theorem 4.9 (main result).** Given an NLP $P$, a three-valued interpretation $I$ is a regular model of $P$ iff $I$ is a $\leq_s$-minimal stable trap space of $P$.

*Proof.* The programs $P$ and $\text{lfp}(P)$ have the same set of regular models by Theorem 4.6. They also have the same set of stable trap spaces by Corollary 4.3. Hence, it suffices to show that $I$ is a regular model of $\text{lfp}(P)$ iff $I$ is a $\leq_s$-minimal stable trap space of $\text{lfp}(P)$.

Recall that $\text{lfp}(P)$ is a negative NLP. Then $I$ is a regular model of $\text{lfp}(P)$ iff $I$ is a $\leq_s$-minimal stable partial model of $\text{lfp}(P)$ by definition
iff I is a $\leq_s$-minimal supported partial model of $\text{lfp}(P)$ by Theorem 4.5

iff I is a $\leq_s$-minimal supported trap space of $\text{lfp}(P)$ by Corollary 4.4

iff I is a $\leq_s$-minimal stable trap space of $\text{lfp}(P)$ by Corollary 4.2.

**Proposition 4.6.** *Given two three-valued interpretations $I_1$ and $I_2$ of an NLP $P$, $I_1 \leq_u I_2$ iff $I_1^u \subseteq I_2^u$.*

*Proof.* We have $I_1 \leq_u I_2$

iff $I_1(v) \leq_u I_2(v)$ for all $v \in \text{HB}_P$

iff either $I_1(v), I_2(v) \neq \star$ or $I_1(v) <_u I_2(v)$ for all $v \in \text{HB}_P$

iff $I_1^u \subseteq I_2^u$.

**Corollary 4.5.** *Given an NLP $P$, $I$ is an $L$-stable model iff it is a $\leq_u$-minimal stable partial model.*

*Proof.* This immediately follows from Proposition 4.6.

**Proposition 4.7.** *Consider an NLP $P$. For every supported trap space $I \in \text{SuTS}(P)$, there is a supported partial model $J \in \text{SuPM}(P)$ such that $J \leq_u I$.*

*Proof.* By Theorem 4.8, there is a unique supported partial model $J \in \text{SuPM}(P)$ such that $J \leq_s I$. Since $I' \leq_s I$ implies $I' \leq_u I$, we can conclude the proof. Note that for $\leq_u$, such a supported partial model may not be unique.

**Corollary 4.6.** *Consider an NLP $P$. A three-valued interpretation $I$ is a $\leq_u$-minimal supported partial model of $P$ iff $I$ is a $\leq_u$-minimal supported trap space of $P$.*

*Proof.* We have $\text{SuPM}(P) \subseteq \text{SuTS}(P)$ by Proposition 4.2.

“⇒” Assume that $I$ is not a $\leq_u$-minimal supported trap space of $P$. Then there exists $I' \in \text{SuTS}(P)$ such that $I' <_u I$. By Proposition 4.7, there exists $J \in \text{SuPM}(P)$ such that $J \leq_u I'$. This implies that $J <_u I$, which contradicts the $\leq_u$-minimality of $I$. Hence, $I$ is a $\leq_u$-minimal supported trap space of $P$.

“ ⇐ ” This direction is trivial because $\text{SuPM}(P) \subseteq \text{SuTS}(P)$.

**Theorem 4.10.** *Given an NLP $P$, $I$ is an $L$-stable model iff $I$ is a $\leq_u$-minimal stable trap space.*

*Proof.* We have $P$ and $\text{lfp}(P)$ have the same set of stable partial models by Theorem 4.6. They also have the same set of stable trap spaces by Corollary 4.3. Hence, it suffices to show that $I$ is an $L$-stable model of $\text{lfp}(P)$ iff $I$ is a $\leq_u$-minimal stable trap space of $\text{lfp}(P)$.

Recall that $\text{lfp}(P)$ is a negative NLP. We have $I$ is an $L$-stable model of $\text{lfp}(P)$

iff $I$ is a $\leq_u$-minimal stable partial model of $\text{lfp}(P)$ by Corollary 4.5

iff $I$ is a $\leq_u$-minimal supported partial model of $\text{lfp}(P)$ by Theorem 4.5

iff $I$ is a $\leq_u$ supported trap space of $\text{lfp}(P)$ by Corollary 4.6

iff $I$ is a $\leq_u$-minimal stable trap space of $\text{lfp}(P)$ by Corollary 4.2.

**Proposition 4.8.** *Given an NLP $P$, $I$ is an $L$-stable model of $P$ iff $I$ is a $\leq_u$-minimal regular model.*

*Proof.* By Theorem 4.10, it suffices to show that $I$ is a $\leq_u$-minimal stable trap space of $P$ iff $I$ is a $\leq_u$-minimal regular model of $P$. The forward direction is trivial because $\text{RegM}(P) \subseteq \text{StTS}(P)$, i.e., the set of regular models is a subset of the set of stable trap spaces. Now, we prove the backward direction.

Assume that $I$ is a $\leq_u$-minimal regular model of $P$. Then $I$ is a $\leq_u$-minimal regular model of $\text{lfp}(P)$ by Theorem 4.6. Suppose that $I$ is not a $\leq_u$-minimal stable trap space of $\text{lfp}(P)$. Then there is a stable trap space $I'$ of $\text{lfp}(P)$ such that $I' <_u I$. By Theorem 4.9, the regular models of $\text{lfp}(P)$ are the $\leq_s$-minimal
stable trap spaces of lfp(*P*). This implies that there is a regular model *J* of lfp(*P*) such that *J* ≤~*s*~ *I*'. Since *J* ≤~*s*~ *I*' implies *J* ≤~*u*~ *I*', *J* <~*u*~ *I*. By Theorem 4.6, *J* is a regular model of *P*, which contradicts the ≤~*u*~-minimality of *I*. Hence, *I* is a ≤~*u*~-minimal stable trap space of lfp(*P*). By Corollary 4.3, *I* is a ≤~*u*~-minimal stable trap space of *P*.

☐

**Corollary 4.7.** If an NLP *P* has no L-stable model, then it has infinitely many regular models.

*Proof.* By Proposition 4.8, the set of L-stable models of *P* coincides with the set of ≤<sub>*u*</sub>-minimal regular models of *P*. If RegM(*P*) is a finite set, then it always has a ≤<sub>*u*</sub>-minimal element, i.e., the set of ≤<sub>*u*</sub>-minimal regular models of *P* is non-empty, leading to *P* has an L-stable model, which is a contradiction. Hence, *P* has infinitely many regular models.

☐

**Theorem 5.2.** An NLP *P* always has a *⊆*-minimal stable (or supported) trap set.

*Proof.* For the case of ⊆-minimal stable trap sets, this immediately follows from Lemma 4.1 and the fact that *P* has at least one stable trap set by Proposition 3.1.

For the case of ⊆-minimal supported trap sets, this immediately follows from Lemma 4.2 and the fact that *P* has at least one supported trap set by Proposition 3.1.

☐

*Alternative proof of Theorem 5.1.* By Theorem 5.2, *P* has a *⊆*-minimal stable trap set *S*. We show that *S* is a stable class.

By definition, {$F_P(I) | I \in S$} $\subseteq S$. Suppose that {$F_P(I) | I \in S$} $\subsetneq S$. Then there exists $J \in S$ such that for all $I \in S$, $F_P(I) \neq J$. We have {$F_P(I) | I \in S \setminus \{J\}$} $\subseteq \{F_P(I) | I \in S\} \subseteq S \setminus \{J\}$. Thus $S \setminus \{J\}$ is a supported trap set of $P$, which contradicts the $\subseteq$-minimality of $S$. Hence {$F_P(I) | I \in S$} = $S$, i.e., $S$ is a supported class of $P$.

☐

**Theorem 5.3.** Any NLP *P* has a supported class.

*Proof.* By Theorem 5.2, *P* has a *⊆*-minimal supported trap set *S*. We show that *S* is a supported class.

By definition, {$T_P(I) | I \in S$} $\subseteq S$. Suppose that {$T_P(I) | I \in S$} $\subsetneq S$. Then there exists $J \in S$ such that for all $I \in S$, $T_P(I) \neq J$. We have {$T_P(I) | I \in S \setminus \{J\}$} $\subseteq \{T_P(I) | I \in S\} \subseteq S \setminus \{J\}$. Thus $S \setminus \{J\}$ is a supported trap set of $P$, which contradicts the $\subseteq$-minimality of $S$. Hence {$T_P(I) | I \in S$} = $S$, i.e., $S$ is a supported class of $P$.

☐

**Corollary 5.1 (main result).** An NLP *P* always has a strict stable (or supported) class.

*Proof.* This immediately follows from Theorem 5.2 and Theorem 4.1 (resp. Theorem 4.2).

☐

**Corollary 5.2.** An NLP *P* always has a *regular model*.

*Proof.* This immediately follows from Theorem 4.9 and Theorem 3.1.

☐
## B Revisit of the Characterizations of Strict Stable and Supported Classes

We first revisit the basic definitions and results of [27] on stable and supported classes.

**Definition B.1 ([27]).** Consider an NLP P and a two-valued interpretation I of P. A sequence of applications of an operator on the set of two-valued interpretations of P is called an orbit. The orbit of I w.r.t. $T_P$ is the sequence $\langle T_P^k(I) \rangle_{k \in \omega}$, where $T_P^0(I) = I$ and $T_P^{k+1}(I) = T_P(T_P^k(I))$. Similarly, we have the definition for the orbit of I w.r.t. $F_P$.

**Definition B.2 ([27]).** Consider an NLP P and a two-valued interpretation I of P. Let $\mathcal{T}_P(I)$ be the set of two-valued interpretations defined as:

$$ \mathcal{T}_P(I) = \{T_P^k(I) | k \in \omega\}. $$

Let $\mathcal{F}_P(I)$ be the set of two-valued interpretations defined as:

$$ \mathcal{F}_P(I) = \{F_P^k(I) | k \in \omega\}. $$

**Theorem B.1 ([27]).** Given an NLP P, a non-empty set S of two-valued interpretations is a strict stable (resp. supported) class of P iff $\mathcal{T}_P(I) = S$ (resp. $\mathcal{F}_P(I) = S$) for every $I \in S$.

Theorem B.1 provides an alternative characterization for strict stable (or supported) classes. This theorem mainly relies on the definitions of stable and supported orbits (see Definition B.1). This may be a problem here, as these definitions only limit the length of the sequence to $\omega$ (the first infinite limit ordinal). Since the sequence can traverse through the set of all two-valued interpretations, which may be an infinite set, thus the length can be a bigger ordinal. With Definition B.1, it seems that Theorem B.1 only consider Datalog$^-$ programs rather than any NLPs. We fix the above problem as follows.

First, we recursively define the stable or supported reachable closure of a two-valued interpretation over all ordinals.

**Definition B.3.** Given an NLP P, let I is a two-valued interpretation of P. The supported reachable closure of I is defined as:

$$ \Pi_P^I \uparrow 0 = \{I\} \\ \Pi_P^I \uparrow \alpha + 1 = \Pi_P^I \uparrow \alpha \cup \bigcup_{J \in \Pi_P^I \uparrow \alpha} \{T_P(J)\}. $$

If $\beta$ is a limit ordinal, then by construction $\{\Pi_P^I \uparrow \alpha: \alpha < \beta\}$ is a $\subseteq$ chain. Define $\Pi_P^I \uparrow \beta = \sup_{\subseteq} \{\Pi_P^I \uparrow \alpha: \alpha < \beta\}$, where $\sup_{\subseteq}$ denotes the least upper bound w.r.t. $\subseteq$. By replacing $T_P(J)$ and $\Pi_P^I$ with $F_P(J)$ and $\Sigma_P$ respectively, we obtain the definition of the stable reachable closure of I.

Then the two following propositions show that the stable or supported reachable closure eventually reaches a constant w.r.t. any two-valued interpretation. The key to their proofs is the use of Hartogs' lemma (see Lemma 2.3).

**Proposition B.1.** Consider an NLP P. For any two-valued interpretation I of P, there is the unique least ordinal $\alpha_I$ such that $\Pi_P^I \uparrow \alpha_I + 1 = \Pi_P^I \uparrow \alpha_I$.

*Proof.* We have $\Pi_P^I \uparrow$ is an increasing function from the ordinals into $2^{\mathbb{H}_{B_P}}$. It cannot be strictly increasing, as if it was, then we would have an injection from the ordinals into $2^{\mathbb{H}_{B_P}}$, which violates Lemma 2.3. Hence, $\Pi_P^I \uparrow$ must be eventually constant. It follows that for some ordinal $\alpha$, $\Pi_P^I \uparrow \alpha + 1 = \Pi_P^I \uparrow \alpha$. Let $\alpha_I$ be the least ordinal such that $\Pi_P^I \uparrow \alpha_I + 1 = \Pi_P^I \uparrow \alpha_I$. Since the ordinals are ordered, $\alpha_I$ is unique. $\square$
**Proposition B.2.** Consider an NLP *P*. For any two-valued interpretation *I* of *P*, there is the unique least ordinal α<sub>I</sub> such that Σ<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>I</sub> + 1 = Σ<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>I</sub>.

*Proof.* Replace Π<sub>P</sub><sup>I</sup> with Σ<sub>P</sub><sup>I</sup> in the proof of Proposition B.1. □

By using transfinite induction (see more details in [30]), we prove that the supported reachable closure is closed under the supported trap set property.

**Lemma B.1.** Consider an NLP *P*. Let *S* be a supported trap set of *P*. Then for all *I* ∈ *S*, Π<sub>*P*</sub><sup>*I*</sup> ↑ *α* ⊆ *S* for all ordinal *α*.

*Proof.* We prove this by using transfinite induction.

Base case: Π<sub>P</sub><sup>I</sup> ↑ 0 = {I} ⊆ S.

Successor case: Π<sub>P</sub><sup>I</sup> ↑ α + 1 = Π<sub>P</sub><sup>I</sup> ↑ α ∪ ⋃<sub>J∈Π<sub>P</sub><sup>I</sup>↑α</sub> {T<sub>P</sub>(J)} ⊆ S ∪ ⋃<sub>J∈S</sub> {T<sub>P</sub>(J)} because Π<sub>P</sub><sup>I</sup> ↑ α ⊆ S by the induction hypothesis. Then Π<sub>P</sub><sup>I</sup> ↑ α + 1 ⊆ S ∪ S = S because S is a supported trap set.

Limit case: Π<sub>P</sub><sup>I</sup> ↑ α = sup<sub>⊆</sub> {Π<sub>P</sub><sup>I</sup> ↑ β : β < α} ⊆ S because Π<sub>P</sub><sup>I</sup> ↑ β ⊆ S for all β < α by the induction hypothesis. □

On the other hand, we prove that the constant that the supported reachable closure reaches is a supported trap set w.r.t. any two-valued interpretation.

**Lemma B.2.** Given an NLP *P*, for any two-valued interpretation *I* of *P*, Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> is a supported trap set of *P*.

*Proof.* By definition of Π<sub>P</sub><sup>I</sup>, we have Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub> + 1 = Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub> ∪ ⋃<sub>J∈Π<sub>P</sub><sup>I</sup>↑α<sub>I</sub></sub> {T<sub>P</sub>(J)}. By definition of α<sub>I</sub>, we have Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub> + 1 = Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub>. Set S = Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub>. It follows that S = S ∪ ⋃<sub>J∈S</sub> {T<sub>P</sub>(J)}. Then ⋃<sub>J∈S</sub> {T<sub>P</sub>(J)} ⊆ S, implying that S is a supported trap set of P. □

Combining Lemma B.1 and Lemma B.2, we now obtain a new characterization for ⊆-minimal supported trap sets of an NLP:

**Theorem B.2.** Given an NLP *P*, *S* is a *⊆*-minimal supported trap set of *P* iff Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> = *S* for all *I* ∈ *S*.

*Proof.* “⇒” Assume that *S* is a *⊆*-minimal supported trap set of *P*. Suppose that there exists *I* ∈ *S* such that Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> ≠ *S*. By Lemma B.1, Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> ⊆ *S* since *S* is a supported trap set. Then Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> ⊂ *S*. By Lemma B.2, Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> is a supported trap set, which contradicts the *⊆*-minimality of *S*. Hence, Π<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> = *S* for all *I* ∈ *S*.

“⇔” Assume that Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub> = S for all I ∈ S. We have Π<sub>P</sub><sup>I</sup> ↑ α<sub>I</sub> + 1 = S = S ∪ ⋃<sub>J∈S</sub> {T<sub>P</sub>(J)}. This implies that ⋃<sub>J∈S</sub> {T<sub>P</sub>(J)} ⊆ S, thus S is a supported trap set of P. Suppose that S is not ⊆-minimal. Then there is a supported trap set S' of P such that S' ⊂ S. Consider J ∈ S'. By Lemma B.1, Π<sub>P</sub><sup>I</sup> ↑ α<sub>J</sub> ⊆ S' ⊂ S, which is a contradiction because J ∈ S. Hence, S is a ⊆-minimal supported trap set of P. □

This is similar for stable trap sets by replacing Π<sub>P</sub><sup>I</sup> by Σ<sub>P</sub><sup>I</sup> in the proof of Theorem B.2:

**Theorem B.3.** Given an NLP *P*, *S* is a *⊆*-minimal stable trap set of *P* iff Σ<sub>*P*</sub><sup>*I*</sup> ↑ α<sub>*I*</sub> = *S* for all *I* ∈ *S*.

*Proof.* Replace Π<sub>P</sub><sup>I</sup> by Σ<sub>P</sub><sup>I</sup> in the proof of Theorem B.2. □

Theorem B.2 and Theorem B.3 are the corrected version of Theorem B.1 in the case of NLPs, as we show that the ⊆-minimal supported (resp. stable) trap sets are equivalent to strict supported (resp. stable) classes (see Theorem 4.1 and Theorem 4.2). In the case of Datalog<sup>−</sup> programs, HB<sub>P</sub> is finite, then ℱ<sub>P</sub>(I) = Π<sub>P</sub><sup>I</sup> ↑ ω (resp. ℱ<sub>P</sub>(I) = Σ<sub>P</sub><sup>I</sup> ↑ ω). Hence, in this case, Theorem B.2 and Theorem B.3 are equivalent to Theorem B.1.
# C Revisit of the Existence of L-stable Models

The existence of L-stable models in an NLP is stated and proved in [35, Proposition 5.11]. The main idea of the proof is similar to what is used for proving the existence of M-stable models in an NLP (see [35, Theorem 5.3]). However, this may pose a problem here because the case of L-stable models is actually not the same as the case of M-stable models. More specifically, the union of all the partial stable models in a maximal chain w.r.t. $\subseteq$-minimal $I^u$ might be not a partial stable model (even the union does not exist, see Example C.1), whereas the union of all the stable partial models in a $\leq_i$-chain is a stable partial model as shown in the proof of [35, Theorem 5.3]. This problem is more justified by the bijection between the L-stable models of an NLP and the semi-stable extensions of an Abstract Argumentation Framework (AF) [9]. It has been shown that there is an infinite AF without a semi-stable extension [6].

**Example C.1.** Consider the NLP $P = \{a \leftarrow \sim b; b \leftarrow \sim a; c \leftarrow \sim c\}$. The program *P* has three stable partial models: $I_1 = \{a = \star, b = \star, c = \star\}$, $I_2 = \{a = 0, b = 1, c = \star\}$, and $I_3 = \{a = 1, b = 0, c = \star\}$. Using the notations of [35], we have $I_1 = \langle\emptyset, \emptyset\rangle$, $I_2 = \langle\{b\}, \{a\}\rangle$, and $I_3 = \langle\{a\}, \{b\}\rangle$. Every maximal chain w.r.t. $\subseteq$-minimal $I^u$ of *P* contains all $I_1$, $I_2$, and $I_3$. However, the union of all elements in such a chain is $\langle\{a, b\}, \{a, b\}\rangle$, which does not represent a valid three-valued interpretation. Hence, the union does not exist.

We make the following two conjectures, inspired by existing related results in abstract argumentation frameworks [6, 38].

**Conjecture C.1.** An internal-variable-free NLP *P* has at least one L-stable model.

**Conjecture C.2.** There exists an NLP *P* such that *P* has no L-stable model.

We here prove a special case of Conjecture C.1, however this conjecture and Conjecture C.2 are still open. This result is meaningful because 1) the class of uni-rule NLPs is easily identifiable by a syntatic characterization, 2) uni-rule Datalog$^-$ programs are as hard as general Datalog$^-$ programs w.r.t the stable model semantics, since identifying whether a uni-rule Datalog$^-$ program has a stable model or not is NP-complete [37], and 3) this class is straightforwardly related to (possibly infinite) AFs [17, 11].

**Theorem C.1.** Consider an NLP *P*. If *P* is uni-rule, then it has at least one L-stable model.

*Proof*. Since *P* is uni-rule, it is easy to derive that *lfp*(*P*) is also uni-rule thanks to the definition of the least fixpoint. If *lfp*(*P*) = $\emptyset$, then it trivially has a L-stable model $I^*$ where $I^*(a) = 0$ for every $a \in \text{HB}_{\text{lfp}(*P)}$. We then only consider the case $\text{lfp}(*P) \neq \emptyset$. If there is an atom $a \in \text{HB}_{\text{lfp}(*P)}$ not being the head of any rule in *lfp*(*P*), it is always 0 in any stable or supported partial model of *lfp*(*P*). Hence we can "propagate" such atoms to get a new NLP $P'$ such that the set of stable partial models of $P'$ one-to-one corresponds to the set of stable partial models of *lfp*(*P*). This implies that the set of L-stable models of $P'$ one-to-one corresponds to the set of L-stable models of *lfp*(*P*). Since *lfp*(*P*) is uni-rule and negative, $P'$ also does. There is a (possibly infinite) AF (say $\mathcal{A}$) corresponding to $P'$ where the set of arguments of $\mathcal{A}$ is $\text{HB}_{P'}$ and each atom in the body of a rule whose head is $a$ corresponds to an attacker of $a$ in $\mathcal{A}$. Since the body of a rule is finite by definition, $\mathcal{A}$ is finitary, i.e., every argument has finitely many attackers [6].

A labelling of an AF is identical to a three-valued interpretation of an NLP. An extension of an AF is defined as a subset of arguments and correponds to a two-valued interpretation of an NLP. There is a one-to-one correspondence between the set of labellings and the set of extensions of a given type [11]. [6, Theorem 14] points out that a finitary AF has at least one semi-stable extension. We can easily to derive the existence of semi-stable labellings in $\mathcal{A}$.
A complete labelling $I$ is a semi-stable labelling if $I^u$ is $\subseteq$-minimal [9]. By the definition of complete labellings [11], we can derive that the set of complete lablellings of $\mathcal{A}$ coincides with the set of supported partial models of $P'$. Since the stable partial models of $P'$ coincide with the supported partial models of $P'$ by Theorem 4.5, $P'$ has at least one L-stable model, leading to $\text{lfp}(P)$ does. Since $P$ and $\text{lfp}(P)$ have the same set of stable partial models by Theorem 4.6, $P$ has at least one L-stable model. $\square$