# Graphical conditions for the existence, unicity and number of regular models

Van-Giang Trinh

Belaid Benhamou

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

trinh.van-giang@lis-lab.fr

belaid.benhamou@lis-lab.fr

Sylvain Soliman

François Fages

Inria Saclay, EP Lifeware, Palaiseau, France

Sylvain.Soliman@inria.fr

francois.fages@inria.fr

The regular models of a normal logic program are a particular type of partial (i.e. 3-valued) models which correspond to stable partial models with minimal undefinedness. In this paper, we explore graphical conditions on the dependency graph of a finite ground normal logic program to analyze the existence, unicity and number of regular models for the program. We show three main results: 1) a necessary condition for the existence of non-trivial (i.e. non-2-valued) regular models, 2) a sufficient condition for the unicity of regular models, and 3) two upper bounds for the number of regular models based on positive feedback vertex sets. The first two conditions generalize the finite cases of the two existing results obtained by You and Yuan (1994) for normal logic programs with well-founded stratification. The third result is also new to the best of our knowledge. Key to our proofs is a connection that we establish between finite ground normal logic programs and Boolean network theory.

**Keywords:** logic programming, semantics of negation, canonical model, three-valued model, Datalog, abstract argumentation, Boolean network, feedback vertex set, model counting

## 1 Introduction

Relating graphical representations of a normal logic program (or just *program* if not otherwise said) and its model-theoretic semantics is an interesting research direction in theory that also has many useful applications in practice [14, 6, 20]. Historically, the first studies of this direction focused on the existence of a unique stable model in classes of programs with special graphical properties on (positive) dependency graphs, including positive programs [16], acyclic programs [1], and locally stratified programs [16]. In 1991, Fages gave a simple characterization of stable models as well-supported models in [13], and then showed that for *tight* programs (i.e. without non-well-founded positive justifications), the stable models of the program coincide with the Herbrand models of its Clark's completion [14]. Being finer-represented but more computationally expensive than dependency graphs, several other graphical representations (e.g., cycle and extended dependency graphs, rule graphs, block graphs) were introduced and several improved results were obtained [6, 7, 9, 20]. There are some recent studies on dependency graphs [15, 28], but they still focus only on stable models. In contrast, very few studies were made about regular models despite of their prominent importance in argumentation frameworks [32, 4] and program semantics [18]. The work of [12] showed the unicity of regular and stable models in locally stratified programs. The work of [33] showed two sufficient graphical conditions, one for the coincidence between stable and regular models, and another one for the unicity of regular models. However, these two conditions were only proven in the case of well-founded stratification programs, and the question if they are still valid for any program is still open to date.
The stable partial semantics is the 3-valued generalization of the (2-valued) stable model semantics [23]. The regular model semantics not only inherits the advantages of the stable partial model semantics but also imposes two notable principles in non-monotonic reasoning: *minimal undefinedness* and *justifiability* (which is closely related to the concept of labeling-based justification in Doyle's truth maintenance system [10]), making it become one of the well-known semantics in logic programming [33, 18]. Furthermore, regular models in ground programs were proven to correspond to preferred extensions in Dung's frameworks [32] and assumption-based argumentation [4], which are two central focuses in abstract argumentation [3].

Recently, we have proposed a new semantics for finite ground programs, called the *trap space semantics*, which establishes formal links between the model-theoretic and dynamical semantics of a finite ground program [31]. It is built on two newly proposed concepts: *stable* and *supported trap spaces*, which are inspired by the concepts of *trap* (or its duality, *siphon*) in Petri net theory and *trap space* in Boolean network theory [21, 19, 30, 29]. We relate the new semantics to other widely-known semantics, in particular showing that subset-minimal stable trap spaces of a finite ground program coincide with its regular models. Interestingly, the restriction to finite ground programs applies without loss of generality to normal Datalog programs, i.e. normal logic programs built over an alphabet without function symbols, since their Herbrand base and their ground instanciation are finite [5].

Motivated by the above elements, in this paper, we explore graphical conditions on the dependency graph of a finite ground program to analyze the existence of non-trivial (i.e. not 2-valued) regular models and the unicity and multiplicity of regular models for the program. More specifically, we show three main results: 1) the existence of negative cycles is a necessary condition for the existence of non-trivial regular models, 2) the absence of positive cycles is a sufficient condition for the unicity of regular models, and 3) $3^{|U^+|}$ (resp. $2^{|U^+|}$) is an upper bound (resp. a finer upper bound) for the number of regular models in generic (resp. tight) finite ground programs where $U^+$ is a positive feedback vertex set of the dependency graph. The first two conditions generalize the finite cases of the two existing results obtained by [33] for well-founded stratification normal logic programs. The third result is also new to the best of our knowledge. Key to our proofs is a connection that we establish between finite ground programs and Boolean network theory based on the trap space semantics.

Boolean Networks (BNs) are a simple and efficient mathematical formalism that has been widely applied to many areas from science to engineering [26]. Originated in the early work of [27], studying relationships between the dynamics of a BN and its influence graph has a rich history of research [22, 24]. To date, this research direction is still growing with many prominent and deep results [24, 26, 25]. Hence, the established connection can bring a plenty of existing results in BNs to studying finite ground programs as well as provide a unified framework for exploring and proving more new theoretical results in the logic program theory.

The rest of this paper is organized as follows. In the next section, we recall preliminaries on normal logic programs, regular models, BNs, and related concepts. Section 3 presents the connection that we establish between finite ground programs and BNs. In Section 4, we present the main results on relationships between regular models and graphical conditions. Finally, Section 5 concludes the paper with some perspectives for future work.

## 2 Preliminaries

We assume that the reader is familiar with the logic program theory and the stable model semantics [16]. Unless specifically stated, a *program* means a normal logic program. In addition, we consider the
Boolean domain $\mathbb{B} = \{\text{true, false}\} = \{1, 0\}$, and the Boolean connectives used in this paper include $\land$ (conjunction), $\lor$ (disjunction), $\neg$ (negation), $\leftarrow$ (implication), and $\leftrightarrow$ (equivalence).

## 2.1 Normal logic programs

We consider a first-order language built over an infinite alphabet of variables, and finite alphabets of constant, function and predicates symbol. The set of first-order terms is the least set containing variables, 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 $t_i$ are terms. A normal logic program $P$ is a finite set of rules of the form

$$p \leftarrow p_1, \dots, p_m, \sim p_{m+1}, \dots, \sim p_k$$

where $p$ and $p_i$ are atoms, $k \ge m \ge 0$, and $\sim$ is a symbol for negation. A fact is a rule with $k = 0$. We denote by atom($P$) the set of atoms appearing in $P$. For any rule $r$ of the above form, $h(r) = p$ is 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 $bf(r) = p_1 \land \dots \land p_m \land \neg p_{m+1} \land \dots \land \neg p_k$ is the body formula of $r$. If $b^-(r) = \emptyset, \forall r \in P$, then $P$ is called a positive program. If $b^+(r) = \emptyset, \forall r \in P$, then $P$ is called a quasi-interpretation program.

A term, an atom or a program is ground if it contains no variable. The Herbrand base is the set of ground atoms formed over the alphabet of the program. It is finite in absence of function symbol, which is the case of Datalog programs [5]. The ground instantiation of a program $P$ is the set of the ground instances of all rules in $P$. In the rest of the paper, we restrict ourselves to finite ground normal logic programs.

We shall use the fixpoint semantics of normal logic programs [11] to prove many new results in the next sections. To be self-contained, we briefly recall the definition of the least fixpoint of a normal logic program $P$ as follows. Let $r$ be the rule $p \leftarrow \sim p_1, ..., \sim p_k, q_1, ..., q_j$ and let $r_i$ be rules $q_i \leftarrow \sim q_i^1, ..., \sim q_i^{l_i}$ where $1 \le i \le j$ and $l_i \ge 0$. Then $\sigma_r(\{r_1, ..., r_j\})$ is the following rule

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

$\sigma_P$ is the transformation on quasi-interpretation programs: $\sigma_P(Q) = \{\sigma_r(\{r_1, ..., r_j\}) | r \in P, r_i \in Q, 1 \le i \le j\}$. Let $\text{lfp}_i = \sigma_P^i(\emptyset) = \sigma_P(\sigma_P(... \sigma_P(\emptyset)))$, then $\text{lfp}(P) = \bigcup_{i \ge 1} \text{lfp}_i$ is the least fixpoint of $P$. In the case of finite ground programs, $\text{lfp}(P)$ is finite and also a quasi-interpretation finite ground program [11].

### 2.1.1 Stable and supported partial models

A 3-valued interpretation $I$ of a finite ground program $P$ is a total function $I$: atom($P$) $\rightarrow$ $\{\mathbf{t}, \mathbf{f}, \mathbf{u}\}$ that assigns one of the truth values true ($\mathbf{t}$), false ($\mathbf{f}$) or unknown ($\mathbf{u}$), to each atom of $P$. If $I(a) \neq \mathbf{u}, \forall a \in$ atom($P$), then $I$ is an Herbrand (2-valued) interpretation of $P$. Usually, a 2-valued interpretation is written as the set of atoms that are true in this interpretation. A 3-valued interpretation $I$ characterizes the set of 2-valued interpretations denoted by $\gamma(I)$ as $\gamma(I) = \{J | J \in 2^{\text{atom}(P)}, \forall a \in \text{atom}(P), I(a) \neq \mathbf{u} \Rightarrow J(a) = I(a)\}$. For example, if $I = \{p = \mathbf{t}, q = \mathbf{f}, r = \mathbf{u}\}$, then $\gamma(I) = \{\{p\}, \{p, r\}\}$.

We consider two orders on 3-valued interpretations. The truth order $\le_t$ is given by $\mathbf{f} \prec_t \mathbf{u} \prec_t \mathbf{t}$. Then, $I_1 \le_t I_2$ iff $I_1(a) \le_t I_2(a), \forall a \in \text{atom}(P)$. The subset order $\le_s$ is given by $\mathbf{f} \prec_s \mathbf{u}$ and $\mathbf{t} \prec_s \mathbf{u}$. Then, $I_1 \le_s I_2$ iff $I_1(a) \le_s I_2(a), \forall a \in \text{atom}(P)$. In addition, $I_1 \le_s I_2$ iff $\gamma(I_1) \subseteq \gamma(I_2)$, i.e., $\le_s$ is identical to the subset partial order.
Let $f$ be a propositional formula on atom($P$). Then the valuation of $f$ under a 3-valued interpretation $I$ (denoted by $I(f)$) is defined recursively as follows:

$$I(f) = \begin{cases} I(a) & \text{if } f = a, a \in \text{atom}(P) \\ \neg I(f_1) & \text{if } f = \neg f_1 \\ \min_{\le t} (I(f_1), I(f_2)) & \text{if } f = f_1 \wedge f_2 \\ \max_{\le t} (I(f_1), I(f_2)) & \text{if } f = f_1 \vee f_2 \end{cases}$$

where $\neg t = \mathbf{f}, \neg \mathbf{f} = \mathbf{t}, \neg \mathbf{u} = \mathbf{u}$, 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 3-valued interpretation $I$ is a 3-valued model of a finite ground program $P$ iff for each rule $r \in P$, $I(bf(r)) \le t I(h(r))$.

**Definition 1.** Let $I$ be a 3-valued interpretation of $P$. We build the reduct $P^I$ as follows.

* Remove any rule $a \leftarrow a_1, \dots, a_m, \sim b_1, \dots, \sim b_k \in P$ if $I(b_i) = t$ for some $1 \le i \le k$.

* Afterwards, remove any occurrence of $\sim b_i$ from $P$ such that $I(b_i) = \mathbf{f}$.

* Then, replace any occurrence of $\sim b_i$ left by a special atom $\mathbf{u}$ ($\mathbf{u} \notin \text{atom}(P)$).

$P^I$ is positive and has a unique $\le t$-least 3-valued model. See [23] for the method for computing this $\le t$-least 3-valued model. Then $I$ is a stable partial model of $P$ iff $I$ is equal to the $\le t$-least 3-valued model of $P^I$. A stable partial model $I$ is a regular model if it is $\le s$-minimal. A regular model is non-trivial if it is not 2-valued.

The Clark's completion of a finite ground program $P$ (denoted by $cf(P)$) consists of the following sentences: for each $p \in \text{atom}(P)$, let $r_1, \dots, r_k$ be all the rules of $P$ having the same head $p$, then $p \leftrightarrow$ $bf(r_1) \lor \dots \lor$ $bf(r_k)$ is in $cf(P)$. If there is no rule whose head is $p$, then the equivalence is $p \leftrightarrow \mathbf{f}$. Let $\text{rhs}(a)$ denote the right hand side of atom $a$ in $cf(P)$. A 3-valued interpretation $I$ is a 3-valued model of $cf(P)$ iff for every $a \in \text{atom}(P)$, $I(a) = I(\text{rhs}(a))$. We define a *supported partial model* of $P$ as a 3-valued model of $cf(P)$. Note that 2-valued stable (resp. supported) partial models are stable (resp. supported) models.

### 2.1.2 Dependency and transition graphs

The Dependency Graph (DG) of a finite ground program $P$ (denoted by $dg(P)$) is a signed directed graph $(V, E)$ on the set of signs $\{\oplus, \ominus\}$ where $V = \text{atom}(P)$ and $(uv, \oplus) \in E$ (resp. $(uv, \ominus) \in E$) iff there is a rule $r \in P$ such that $v = h(r)$ and $u \in b^+(r)$ (resp. $u \in b^-(r)$). An arc $(uv, \oplus)$ is positive, whereas an arc $(uv, \ominus)$ is negative. Since atom($P$) is finite, the DG of $P$ is a finite graph, thus we can apply the finite graph theory. A cycle of $dg(P)$ is positive (resp. negative) if it contains an even (resp. odd) number of negative arcs. A positive (resp. negative) feedback vertex set is a set of vertices that intersect all positive (resp. negative) cycles of $dg(P)$. The positive DG of $P$ (denoted by $dg^+(P)$) is a sub-graph of $dg(P)$ that has the same set of vertices but contains only positive arcs. $P$ is *locally stratified* if every cycle of $dg(P)$ contains no negative arc [16]. $P$ is *tight* if $dg^+(P)$ has no cycle [14]. $P$ is *well-founded stratification* if there is a topological order on the set of Strongly Connected Components (SCCs) of $dg(P)$ and for every SCC $B$, there exists SCC $A \le B$ and for any SCC $C$, if $C \le A$ then there are only positive arcs from atoms in $C$ to atoms in $A$ [33]. Herein, $A \le B$ iff there is a path from some atom in $A$ to some atom in $B$. In the case of finite ground programs, the above definition of well-founded stratification (which was originally defined for both finite and infinite ground programs) is equivalent to that a finite ground
program is well-founded stratification iff there is a topological order of its dependency graph such that every SCC at the lowest level only contains positive arcs.

The *immediate consequence operator* (or the *$T_P$ operator*) is defined as a mapping $T_P: 2^{\text{atom}(P)} \to 2^{\text{atom}(P)}$ such that $T_P(I)(a) = I(\text{rhs}(a))$ where $I$ is a 2-valued interpretation. If $I$ is a 2-valued interpretation, then $P^I$ is exactly the reduct defined in [16] and the unique $\le_I$-least model of $P^I$ is 2-valued. The *Gelfond-Lifschitz operator* (or the *$F_P$ operator*) is defined as a mapping $F_P: 2^{\text{atom}(P)} \to 2^{\text{atom}(P)}$ such that $F_P(I)$ is the unique $\le_I$-least model of $P^I$ [16]. The *stable* (resp. *supported*) *transition graph* of $P$ is a directed graph (denoted by $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$)) on the set of all possible 2-valued interpretations of $P$ such that $(I, J)$ is an arc of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$) iff $J = F_P(I)$ (resp. $J = T_P(I)$). A *trap domain* of a directed graph is a set of vertices having no out-going arcs.

### 2.1.3 Stable and supported trap spaces

In [31], we introduce a new semantics for finite ground programs, called the *trap space semantics*. This semantics shall be used in this work as the bridge between finite ground programs and Boolean networks. To be self-contained, we briefly recall the definition and essential properties of this semantics.

A set $S$ of 2-valued interpretations of a finite ground program $P$ is called a *stable trap set* (resp. *supported trap set*) of $P$ if $\{F_P(I) | I \in S\} \subseteq S$ (resp. $\{T_P(I) | I \in S\} \subseteq S$). A 3-valued interpretation $I$ of a finite ground program $P$ is called a *stable trap space* (resp. *supported trap space*) of $P$ if $\gamma(I)$ is a stable (resp. supported) trap set of $P$. By definition, a stable (resp. supported) trap set of $P$ is a trap domain of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$). Hence, we can deduce that a 3-valued interpretation $I$ is a stable (resp. supported) trap space of $P$ if $\gamma(I)$ is a trap domain of $\text{tg}_{\text{st}}(P)$ (resp. $\text{tg}_{\text{sp}}(P)$). We also show in [31] that $I$ is a supported trap space of $P$ iff $I$ is 3-valued model of $\overleftarrow{\text{cf}}(P)$ w.r.t. to the order $\le_S$ where $\overleftarrow{\text{cf}}(P)$ is the $\leftarrow$ part of the Clark's completion of $P$, and a stable (resp. supported) partial model of $P$ is also a stable (resp. supported) trap space of $P$.

**Example 1.** Consider finite ground program $P_1$ (taken from [17]) where $P_1 = \{p \leftarrow \sim q; q \leftarrow \sim p; r \leftarrow q\}$. Herein, we use ‘;’ to separate program rules. Figures 1 (a), (b), and (c) show the dependency graph, the stable transition graph, and the supported transition graph of $P_1$, respectively. $P_1$ is tight, but neither locally stratified nor well-founded stratification. $P_1$ has five stable (also supported) trap spaces: $I_1 = \{p = t, q = f, r = u\}$, $I_2 = \{p = f, q = t, r = u\}$, $I_3 = \{p = u, q = u, r = u\}$, $I_4 = \{p = t, q = f, r = f\}$, and $I_5 = \{p = f, q = t, r = t\}$. Among them, only $I_3$, $I_4$, and $I_5$ are stable (also supported) partial models of $P_1$. $P_1$ has two regular models ($I_4$ and $I_5$). The least fixpoint of $P_1$ is $\text{lfp}(P_1) = \{p \leftarrow \sim q; q \leftarrow \sim p; r \leftarrow \sim p\}$.

<figure><img src="image_1.png" /><figcaption>Figure 1: (a) $\text{dg}(P_1)$, (b) $\text{tg}_{\text{st}}(P_1)$, and (c) $\text{tg}_{\text{sp}}(P_1)$.</figcaption></figure>
## 2.2 Boolean networks

A Boolean Network (BN) $f$ is a *finite* set of Boolean functions on a finite set of Boolean variables denoted by $\text{var}_f$. Each variable $v$ is associated with a Boolean function $f_v: \mathbb{B}^{\text{var}_f} \to \mathbb{B}$. $f_v$ is called *constant* if it is always either 0 or 1 regardless of its arguments. A state $s$ of $f$ is a mapping $s: \text{var}_f \to \mathbb{B}$ that assigns either 0 (inactive) or 1 (active) to each variable. We can write $s_v$ instead of $s(v)$ for short.

Let $x$ be a state of $f$. We use $x[v \leftarrow a]$ to denote the state $y$ so that $y_v = a$ and $y_u = x_u, \forall u \in \text{var}_f, u \neq v$ where $a \in \mathbb{B}$. The Influence Graph (IG) of $f$ (denoted by $\text{ig}(f)$) is a signed directed graph $(V, E)$ on the set of signs $\{\oplus, \ominus\}$ where $V = \text{var}_f, (uv, \oplus) \in E$ (i.e., $u$ positively affects the value of $f_v$) iff there is a state $x$ such that $f_v(x[u \leftarrow 0]) < f_v(x[u \leftarrow 1])$, and $(uv, \ominus) \in E$ (i.e., $u$ negatively affects the value of $f_v$) iff there is a state $x$ such that $f_v(x[u \leftarrow 0]) > f_v(x[u \leftarrow 1])$.

At each time step $t$, variable $v$ can update its state to $s'(v) = f_v(s)$, where $s$ (resp. $s'$) is the state of $f$ at time $t$ (resp. $t+1$). An *update scheme* of a BN refers to how variables update their states over (discrete) time [26]. Various update schemes exist, but the primary types are *synchronous*, where all variables update simultaneously, and *fully asynchronous*, where a single variable is non-deterministically chosen for updating. By adhering to the update scheme, the BN transitions from one state to another, which may or may not be the same. This transition is referred to as the *state transition*. Then the dynamics of the BN is captured by a directed graph referred to as the State Transition Graph (STG). We use $\text{sstg}(f)$ (resp. $\text{astg}(f)$) to denote the synchronous (resp. asynchronous) STG of $f$.

A non-empty set of states is a *trap set* if it has no out-going arcs on the STG of $f$. An *attractor* is a subset-minimal trap set. An attractor of size 1 (resp. at least 2) is called a fixed point (resp. cyclic attractor). A *sub-space* $m$ of a BN is a mapping $m: \text{var}_f \to \mathbb{B} \cup \{\star\}$. A sub-space $m$ is equivalent to the set of all states $s$ such that $s(v) = m(v), \forall v \in \text{var}_f, m(v) \neq \star$. With abuse of notation, we use $m$ and its equivalent set of states interchangeably. For example, $m = \{v_1 = \star, v_2 = 1, v_3 = 1\} = \{011, 111\}$ (for simplicity, we write states as a sequence of values). If a sub-space is also a trap set, it is a *trap space*. Unlike trap sets and attractors, trap spaces of a BN are independent of the update scheme [19]. Then a trap space $m$ is minimal iff there is no other trap space $m'$ such that $m' \subset m$. It is easy to derive that a minimal trap space contains at least one attractor of the BN regardless of the update scheme.

**Example 2.** Consider BN $f_1$ with $f_p = \neg q, f_q = \neg p, f_r = q$. Figures 2 (a), (b), and (c) show the influence graph, the synchronous STG, and the asynchronous STG of $f_1$. Attractor states are highlighted with boxes. $\text{sstg}(f_1)$ has two fixed points and one cyclic attractor, whereas $\text{astg}(f_1)$ has only two fixed points. $f_1$ has five trap spaces: $m_1 = 10\star, m_2 = 01\star, m_3 = \star\star\star, m_4 = 100$, and $m_5 = 011$. Among them, $m_4$ and $m_5$ are minimal.

<figure><img src="image_2.png" /><figcaption>Figure 2: (a) $\text{ig}(f_1)$, (b) $\text{sstg}(f_1)$, and (c) $\text{astg}(f_1)$.</figcaption></figure>
# 3 Finite ground normal logic programs and Boolean networks

We define a BN encoding for finite ground programs in Definition 2. Then, we show two relationships between a finite ground program and its encoded BN (see Theorems 1 and 3).

**Definition 2.** Let $P$ be a finite ground program. We define a BN $f$ encoding $P$ as follows: $\text{var}_f = \text{atom}(P)$, $f_v = \bigvee_{r \in P, v=h(r)} \text{bf}(r)$, $\forall v \in \text{var}_f$. Conventionally, if there is no rule $r \in P$ such that $h(r) = v$, then $f_v = 0$. By considering 1 (resp. 0) as $t$ (resp. $f$), and $\star$ as $u$, sub-spaces (resp. states) of $f$ are identical to 3-valued (resp. 2-valued) interpretations of $P$.

**Theorem 1.** Let $P$ be a finite ground program and $f$ be its encoded BN. Then $\text{ig}(f) \subseteq \text{dg}(P)$.

*Proof.* By construction, $\text{ig}(f)$ and $\text{dg}(P)$ have the same set of vertices. Let $\text{in}_f^+(v)$ (resp. $\text{in}_P^+(v)$) denote the set of vertices $u$ such that $(uv, \oplus)$ is an arc of $\text{ig}(f)$ (resp. $\text{dg}(P)$). We define $\text{in}_f^-(v)$ (resp. $\text{in}_P^-(v)$) similarly. We show that $\text{in}_f^+(v) \subseteq \text{in}_P^+(v)$ and $\text{in}_f^-(v) \subseteq \text{in}_P^-(v)$ for every $v \in \text{atom}(P)$ (*). Consider atom $u$. The case that both $u$ and $\sim u$ appear in rules whose heads are $v$ is trivial. For the case that only $u$ appears in rules whose heads are $v$, $u$ is essential in $f_v$ by construction, and it positively affects the value of $f_v$, leading to $u \in \text{in}_f^+(v)$ and $u \notin \text{in}_f^-(v)$. This implies that (*) still holds. The case that only $\sim u$ appears in rules whose heads are $v$ is similar. By (*), we can conclude that $\text{ig}(f) \subseteq \text{dg}(P)$, i.e., $\text{ig}(f)$ is a sub-graph of $\text{dg}(P)$. In addition, if $P$ is a quasi-interpretation finite ground program, then $\text{ig}(f) = \text{dg}(P)$. $\square$

**Lemma 2** (derived from Theorem 4.5 of [17]). Let $P$ be a finite ground program and $f$ be its encoded BN. Then $\text{tg}_{sp}(P) = \text{sstg}(f)$.

**Theorem 3.** Let $P$ be a finite ground program and $f$ be its encoded BN. Then supported trap spaces of $P$ coincide with trap spaces of $f$.

*Proof.* By Lemma 2, $\text{tg}_{sp}(P) = \text{sstg}(f)$. Note that trap spaces of $f$ are the same under both the synchronous and asynchronous update schemes [19]. Hence, trap spaces of $f$ coincide with trap spaces of $\text{sstg}(f)$. Since $\text{tg}_{sp}(P) = \text{sstg}(f)$, supported trap spaces of $P$ coincide with trap spaces of $f$. $\square$

For illustration, BN $f_1$ of Example 2 is the encoded BN of finite ground program $P_1$ of Example 1. $\text{tg}_{sp}(P_1)$ is identical to $\text{sstg}(f_1)$, and the five supported trap spaces of $P_1$ are identical to the five trap spaces of $f_1$. In addition, $P_1$ is tight and $\text{ig}(f_1) = \text{dg}(P_1)$.

# 4 Graphical analysis results

In this section, we present our new results on graphical conditions for several properties of regular models in finite ground normal logic programs by exploiting the connection established in Section 3.

## 4.1 Preparations

For convenience, we first recall several existing results in both logic programs and Boolean networks that shall be used later.

**Theorem 4** ([17]). Let $P$ be a quasi-interpretation finite ground program. Then $\text{tg}_{st}(P) = \text{tg}_{sp}(P)$, i.e., the stable and supported transition graphs of $P$ are the same.

**Theorem 5** ([17]). Let $P$ be a finite ground program and $\text{lfp}(P)$ denote its least fixpoint. Then $P$ and $\text{lfp}(P)$ have the same stable transition graph.
**Theorem 6** (Theorem 6 of [28]). Let P be a finite ground program and lfp(P) denote its least fixpoint. If P is locally stratified, then dg(lfp(P)) has no cycle.

**Lemma 7.** Let P be a finite ground program and lfp(P) denote its least fixpoint. If dg(P) is has no negative cycle, then dg(lfp(P)) has no negative cycle.

*Proof.* It directly follows from Lemma 5.3 of [14]. □

**Proposition 8** ([31]). Let P be a finite ground program. Let $T(P)$ denote the set of all supported trap spaces of P. Let $C(P)$ denote the set of all 3-valued models of $cf(P)$ (i.e., the Clark's completion of P). For every supported trap space $I \in T(P)$, there is a model $I' \in C(P)$ such that $I' \leq_s I$.

*Sketch of proof.* Let $I^j$ be an arbitrary supported trap space in $T(P)$. We construct a 3-valued interpretation $I^{j+1}$ as follows: $\forall a \in \text{atom}(P), I^{j+1}(a) = I^j(\text{rhs}(a))$. We prove that $I^{j+1}$ is also a supported trap space of P. For every supported trap space $I$ in $T(P)$, we start with $I^j = I$ and repeat the above process by increasing $j$ by 1, and finally reach the case that $I^{j+1} = I^j$ because $\gamma(I)$ is finite. By construction, $I^j(a) = I^j(\text{rhs}(a)), \forall a \in \text{atom}(P)$, and $I^j \leq_s I$. Hence, by setting $I' = I^j$, there is a model $I' \in C(P)$ such that $I' \leq_s I$. □

**Theorem 9** ([31]). Let P be a finite ground program. Then a 3-valued interpretation I is a regular model of P iff I is a $\leq_s$-minimal stable trap space of P.

*Sketch of proof.* Let lfp(P) be the least fixpoint of P. By Proposition 8, we can deduce that $\leq_s$-minimal supported trap spaces of lfp(P) coincide with $\leq_s$-minimal supported (also stable) partial models spaces of lfp(P). P and lfp(P) have the same set of stable partial models [2]. By Theorem 5, P and lfp(P) have the same stable transition graph, thus they have the same set of stable trap spaces. Since stable trap spaces of lfp(P) coincide with its supported trap spaces, we can conclude the theorem. □

**Theorem 10** (Theorem 1 of [24]). Let $f$ be a BN. If $ig(f)$ has no cycle, $astg(f)$ has a unique attractor that is also the unique fixed point of $f$.

**Theorem 11** (Theorem 12 of [24]). Let $f$ be a BN. If $ig(f)$ has no negative cycle, then $astg(f)$ has no cyclic attractor.

## 4.2 Unicity of regular and stable models

To illustrate better applications of the connection between finite ground programs and Boolean networks, we start with providing a probably simpler proof for the finite case of a well-known result on the unicity of regular and stable models in locally stratified programs [12].

**Theorem 12** ([12]). If P is a locally stratified finite ground program, then P has a unique regular model that is also the unique stable model of P.

*New proof.* Let lfp(P) denote the least fixpoint of P. Let $f$ be the encoded BN of lfp(P). By Theorem 6, $dg(lfp(P))$ has no cycle. Since $ig(f)$ is a sub-graph of $dg(lfp(P))$ by Theorem 1, it also has no cycle. By Theorem 10, $astg(f)$ has a unique attractor that is also the unique fixed point of $f$. P and lfp(P) have the same set of regular (also stable) models [2]. By Theorem 9, regular models of lfp(P) are $\leq_s$-minimal stable trap spaces of lfp(P). Since lfp(P) is a quasi-interpretation finite ground program, its stable trap spaces coincide with its supported trap spaces. Supported trap spaces of lfp(P) coincide with trap spaces of $f$ by Theorem 3. Hence, regular models of P coincide with $\leq_s$-minimal trap spaces of $f$. Since the
number of $\leq_s$-minimal trap spaces of $f$ are a lower bound of the number of attractors of $\mathrm{astg}(f)$ and $f$ has at least one $\leq_s$-minimal trap space [19], $f$ has a unique $\leq_s$-minimal trap space that is also the unique fixed point of $f$. Hence, $P$ has a unique regular model that is also the unique stable model of $P$. $\square$

## 4.3 Existence of non-trivial regular models

**Theorem 13** (Theorem 5.3(i) of [33]). *Let $P$ be a well-founded stratification normal logic program. If $dg(P)$ has no negative cycle, then all the regular models of $P$ are 2-valued.*

Theorem 13 provides a sufficient (resp. necessary) condition on the dependency graph for the non-existence (resp. existence) of non-trivial regular models, but it is only limited to well-founded stratification normal logic programs. Note that the well-founded stratification of a normal logic program is defined based on the ground instantiation of this program [33], and the set of all possible well-founded stratification programs in the finite case is only a small piece of the set of all possible finite ground programs [33]. To the best of our knowledge, the question if it is valid for any finite ground program is still open to date. We answer this question in Theorem 14.

**Theorem 14.** Let $P$ be a finite ground program. If $dg(P)$ has no negative cycle, then all the regular models of $P$ are 2-valued.

*Proof.* Let $\mathrm{lfp}(P)$ be the least fixpoint of $P$. By Lemma 7, $dg(\mathrm{lfp}(P))$ has no negative cycle. Let $f$ be the encoded BN of $\mathrm{lfp}(P)$. Since $\mathrm{ig}(f)$ is a sub-graph of $dg(\mathrm{lfp}(P))$ by Theorem 1, $\mathrm{ig}(f)$ also has no negative cycle. By Theorem 11, $\mathrm{astg}(f)$ (i.e., the asynchronous transition graph of $f$) has no cyclic attractor. This implies that all attractors of $\mathrm{astg}(f)$ are fixed points (*). Assume that $f$ has a $\leq_s$-minimal trap space (say $m$) that is not a fixed point. Since every $\leq_s$-minimal trap space of $f$ contains at least one attractor of $\mathrm{astg}(f)$ [19], there is an attractor (say $A$) of $\mathrm{astg}(f)$ such that $A \subseteq \gamma(m)$. By (*), $A$ is a fixed point, leading to $A <_s m$. This is a contradiction because $m$ is $\leq_s$-minimal. Hence, all $\leq_s$-minimal trap spaces of $f$ are fixed points.

By Theorem 3, trap spaces of $f$ coincide with supported trap spaces of $\mathrm{lfp}(P)$. $\mathrm{lfp}(P)$ is a quasi-interpretation finite ground program, thus $\mathrm{tg}_{\mathrm{sf}}(\mathrm{lfp}(P)) = \mathrm{tg}_{\mathrm{sp}}(\mathrm{lfp}(P))$. It follows that its supported trap spaces are also its stable trap spaces. Hence, $\leq_s$-minimal trap spaces of $f$ are $\leq_s$-minimal stable trap spaces of $\mathrm{lfp}(P)$. This implies that all $\leq_s$-minimal stable trap spaces of $\mathrm{lfp}(P)$ are 2-valued. By Theorem 9, all regular models of $\mathrm{lfp}(P)$ are 2-valued. $P$ and $\mathrm{lfp}(P)$ have the same set of regular models [2]. Hence, all regular models of $P$ are 2-valued. $\square$

Theorem 14 implies that the undefinedness is only needed if there is a negative cycle in the DG, i.e., the regular model and stable model semantics are the same under the absence of negative cycles. In addition, we can get from Theorem 14 a straightforward corollary: if the DG of a finite ground program has no negative cycle, then it has at least one stable model. The reason is because a finite ground program always has at least one regular model [33]. This corollary is exactly the generalization of the finite case of Theorem 5.7 of [33] for well-founded stratification programs.

## 4.4 Unicity of regular models

The work of [33] shows a sufficient condition for the unicity of regular models for well-founded stratification normal logic programs.

**Theorem 15** (Theorem 5.3(ii) of [33]). *Let $P$ be a well-founded stratification program. If $dg(P)$ has no positive cycle, $P$ has a unique regular model.*
Hereafter, we would like to show that the finite case of Theorem 15 is also true for any finite ground program. Note however that the technique of using least fixpoint applied for negative cycles seems difficult to use for positive cycles because there is some finite ground program whose dependency graph has no positive cycle but the dependency graph of its least fixpoint can have positive cycle (e.g., $P = \{a \leftarrow c; b \leftarrow c; c \leftarrow \sim a, \sim b\}$). We here use another approach.

**Theorem 16 (Theorem 3.4 of [22]).** Let $f$ be a BN. If $ig(f)$ has no positive cycle, then $astg(f)$ has a unique attractor.

**Theorem 17 (Lemma 16 of [8]).** Supported partial models of a tight finite ground program coincide with its stable partial models.

**Lemma 18.** Let $P$ be a finite ground program and $f$ be its encoded BN. If $P$ is tight, then regular models of $P$ coincide with $\leq_s$-minimal trap spaces of $f$.

*Proof.* Since $P$ is tight, stable partial models of $P$ coincide with supported partial models of $P$ (i.e., 3-valued models of $cf(P)$) by Theorem 17. Then regular models of $P$ coincide with $\leq_s$-minimal supported partial models of $P$. We have that trap spaces of $f$ coincide with supported trap spaces of $P$ by Theorem 3. By Proposition 8, $\leq_s$-minimal supported partial models of $P$ coincide with $\leq_s$-minimal supported trap spaces of $P$. Hence, regular models of $P$ coincide with $\leq_s$-minimal trap spaces of $f$. $\square$

**Theorem 19.** Let $P$ be a finite ground program. If $dg(P)$ has no positive cycle, then $P$ has a unique regular model.

*Proof.* Since $dg(P)$ has no positive cycle, $dg^+(P)$ (i.e., the positive dependency graph of $P$) has no cycle, i.e., $P$ is tight. Let $f$ be the encoded BN of $P$. By Lemma 18, regular models of $P$ coincide with $\leq_s$-minimal trap spaces of $f$. Since $ig(f)$ is a sub-graph of $dg(P)$, it also has no positive cycle. By Theorem 16, $astg(f)$ has a unique attractor. Since every $\leq_s$-minimal trap space of $f$ contains at least one attractor of $astg(f)$ and $f$ has at least one $\leq_s$-minimal trap space [19], $f$ has a unique $\leq_s$-minimal trap space. Hence, we can conclude that $P$ has a unique regular model. $\square$

Since a stable model is also a regular model, Theorem 19 implies that if $dg(P)$ has no positive cycle, then $P$ has at most one stable model. In addition, $P$ may have no stable model because the unique regular model may be not 2-valued. This result seems to be already known in the folklore of the logic program theory, but to the best of our knowledge, there is no existing formal proof for it except the one that we have directly proved recently in [28].

## 4.5 Upper bound for number of regular models

To the best of our knowledge, there is no existing work connecting between regular models of a finite ground program and (positive/negative) feedback vertex sets of its dependency graph. In [28], we have shown that $2^{|U^+|}$ is an upper bound for the number of stable models where $U^+$ is a positive feedback vertex set of the dependency graph. Since stable models are 2-valued regular models, we can naturally generalize this result for the case of regular models, i.e., $3^{|U^+|}$ is an upper bound for the number of regular models. The underlying intuition for the base of three is that in a regular model, the value of an atom can be t, f, or u.

**Theorem 20.** Let $P$ be a finite ground program. Let $U^+$ be a positive feedback vertex set of $dg(P)$. Then the number of regular models of $P$ is at most $3^{|U^+|}$.
**Proof.** By Theorem 9, regular models of $\mathcal{P}$ coincide with $\leq_s$-minimal stable trap spaces of $\mathcal{P}$. For any mapping $\hat{I}: U^+ \to \{\mathbf{t}, \mathbf{f}, \mathbf{u}\}$, we build a new finite ground program $\hat{P}$ from $\mathcal{P}$ as follows. First, remove from $\mathcal{P}$ all the rules whose heads belong to $U^+$. Second, remove all the rules whose body formulas are false under the values of the atoms in $U^+$ and otherwise remove all the appearances of the atoms that are in $U^+$ and not assigned to $\mathbf{u}$ in $\hat{I}$. Third, for any atom $a \in U^+$ such that $\hat{I}(a) = \mathbf{u}$, add the rule $a \leftarrow \sim a$. We can see that the part of $\mathrm{tg}_{st}(\mathcal{P})$ induced by $\hat{I}$ is isomorphic to $\mathrm{tg}_{st}(\hat{P})$. Hence, $\leq_s$-minimal stable trap spaces of $\mathcal{P}$ induced by $\hat{I}$ one-to-one correspond to those of $\hat{P}$. $U^+$ intersects all positive cycles of $\mathrm{dg}(\mathcal{P})$. Every atom $a \in U^+$ such that $\hat{I}(a) \neq \mathbf{u}$ is removed from $\mathrm{dg}(\mathcal{P})$. In the case that $a \in U^+$ and $\hat{I}(a) = \mathbf{u}$, all the arcs ending at $a$ are removed and an negative arc $(aa, \ominus)$ is added. It follows that $\mathrm{dg}(\hat{P})$ has no positive cycle. By Theorem 19, $\hat{P}$ has a unique $\leq_s$-minimal stable trap space. There are $3^{|U^+|}$ possible mappings $\hat{I}$, thus we can conclude the theorem. $\square$

**Theorem 21** (Theorem 3.5 of [22]). Let $f$ be a BN. Let $U^+$ be a positive feedback vertex set of $\mathrm{ig}(f)$. Then the number of attractors of $\mathrm{astg}(f)$ is at most $2^{|U^+|}$.

We observed that the bound of $3^{|U^+|}$ is too rough for many example finite ground programs in the literature. Then inspired by Theorem 21 for an upper bound for the number of attractors of an asynchronous BN, we obtain an interesting result for tight finite ground programs.

**Theorem 22.** Let $\mathcal{P}$ be a tight finite ground program. Let $U^+$ be a positive feedback vertex set of $\mathrm{dg}(\mathcal{P})$. Then the number of regular models of $\mathcal{P}$ is at most $2^{|U^+|}$.

**Proof.** Let $f$ be the encoded BN of $\mathcal{P}$. By Lemma 18, regular models of $\mathcal{P}$ coincide with $\leq_s$-minimal trap spaces of $f$. By definition, $U^+$ intersects all positive cycles of $\mathrm{dg}(\mathcal{P})$. Since $\mathrm{ig}(f)$ is a sub-graph of $\mathrm{dg}(\mathcal{P})$, every positive cycle of $\mathrm{ig}(f)$ is also a positive cycle of $\mathrm{dg}(\mathcal{P})$. Hence, $U^+$ is also a positive feedback vertex set of $\mathrm{ig}(f)$. By Theorem 21, the number of attractors of $\mathrm{astg}(f)$ is at most $2^{|U^+|}$. Since the number of $\leq_s$-minimal trap spaces of $f$ is a lower bound of the number of attractors of $\mathrm{astg}(f)$ [19], the number of regular models of $\mathcal{P}$ is at most $2^{|U^+|}$. $\square$

# 5 Conclusion and perspectives

In this paper, we have shown three main results relating some graphical properties of a finite ground normal logic program to the set of its regular models, namely 1) the presence of negative cycles as a necessary condition for the existence of non-trivial regular models, 2) the absence of positive cycles as a sufficient condition for the unicity of regular models, and 3) two upper bounds on the number of regular models for, respectively generic and tight, finite ground normal logic programs based on the size of positive feedback vertex sets in their dependency graph. The first two conditions generalize the finite cases of the two existing results obtained by [33] for well-founded stratification normal logic programs. Our proofs use an encoding of finite ground normal logic programs by Boolean networks, the equivalence established between regular models and minimal trap spaces, and some recent results obtained in Boolean network theory.

We believe that the established connection can provide more results for the study of Datalog programs and abstract argumentation, and might also be worth considering for normal logic programs without finiteness assumption on their ground intantiation. The results presented in this paper use conditions on either positive cycles or negative cycles. It is thus natural to think that by using both kinds of cycles simultaneously, improved results might be obtained. Finally, we also conjecture that the upper bound for tight finite ground normal logic programs presented here, is in fact valid for generic ones.
# Acknowledgments

This work was supported by Institut Carnot STAR, Marseille, France.

# References

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

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

[3] Pietro Baroni, Martin Caminada & Massimiliano Giacomin (2011): *An introduction to argumentation semantics*. Knowl. Eng. Rev. 26(4), pp. 365–410, doi:10.1017/S0269888911000166.

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

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

[6] Stefania Costantini (2006): *On the existence of stable models of non-stratified logic programs*. Theory Pract. Log. Program. 6(1-2), pp. 169–212, doi:10.1017/S1471068405002589.

[7] Stefania Costantini & Alessandro Provetti (2011): *Conflict, Consistency and Truth-Dependencies in Graph Representations of Answer Set Logic Programs*. In: Second International Workshop on Graph Structures for Knowledge Representation and Reasoning, Springer, pp. 68–90, doi:10.1007/978-3-642-29449-5_3.

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

[9] Yannis Dimopoulos & Alberto Torres (1996): *Graph Theoretical Structures in Logic Programs and Default Theories*. Theor. Comput. Sci. 170(1-2), pp. 209–244, doi:10.1016/S0304-3975(96)80707-9.

[10] Jon Doyle (1979): *A Truth Maintenance System*. Artif. Intell. 12(3), pp. 231–272, doi:10.1016/0004-3702(79)90008-0.

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

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

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

[14] Francois Fages (1994): *Consistency of Clark's completion and existence of stable models*. Methods Log. Comput. Sci. 1(1), pp. 51–60. Available at https://lifeware.inria.fr/~fages/Papers/MLCS.pdf.

[15] Jorge Fandinno & Vladimir Lifschitz (2023): *Positive Dependency Graphs Revisited*. Theory Pract. Log. Program. 23(5), pp. 1128–1137, doi:10.1017/S1471068422000333.

[16] Michael Gelfond & Vladimir Lifschitz (1988): *The Stable Model Semantics for Logic Programming*. In: Proc. of ICLP, MIT Press, pp. 1070–1080.

[17] Katsumi Inoue & Chiaki Sakama (2012): *Oscillating Behavior of Logic Programs*. In: Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Springer, pp. 345–362, doi:10.1007/978-3-642-30743-0_23.
[18] Tomi Janhunen, Ilkka Niemelä, Dietmar Seipel, Patrik Simons & Jia-Huai You (2006): *Unfolding partiality and disjunctions in stable model semantics*. ACM Trans. Comput. Log. 7(1), pp. 1–37, doi:10.1145/1119439.1119440.

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

[20] Thomas Linke (2001): *Graph Theoretical Characterization and Computation of Answer Sets*. In: Proc. of IJCAI, Morgan Kaufmann, pp. 641–648.

[21] T. Murata (1989): *Petri nets: Properties, analysis and applications*. Proc. IEEE 77(4), pp. 541–580, doi:10.1109/5.24143.

[22] Loïc Paulevé & Adrien Richard (2011): *Static Analysis of Boolean Networks Based on Interaction Graphs: A Survey*. In: Proc. of SASB, Elsevier, pp. 93–104, doi:10.1016/J.ENTCS.2012.05.017.

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

[24] Adrien Richard (2019): *Positive and negative cycles in Boolean networks*. J. Theor. Biol. 463, pp. 67–76, doi:10.1016/j.jtbi.2018.11.028.

[25] Adrien Richard & Elisa Tonello (2023): *Attractor separation and signed cycles in asynchronous Boolean networks*. Theor. Comput. Sci. 947, p. 113706, doi:10.1016/J.TCS.2023.113706.

[26] Julian D Schwab, Silke D Kühlwein, Nensi Ikonomi, Michael Kühl & Hans A Kestler (2020): *Concepts in Boolean network modeling: What do they all mean? Comput. Struct. Biotechnol. J.* 18, pp. 571–582, doi:10.1016/j.csbj.2020.03.001.

[27] René Thomas & Richard d'Ari (1990): *Biological feedback*. CRC press.

[28] Van-Giang Trinh & Belaid Benhamou (2024): *Static Analysis of Logic Programs via Boolean Networks*. arXiv:2407.09015.

[29] Van-Giang Trinh, Belaid Benhamou & Loïc Paulevé (2024): *mpbn: a simple tool for efficient edition and analysis of elementary properties of Boolean networks*. CoRR abs/2403.06255, doi:10.48550/ARXIV.2403.06255.

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

[31] Van-Giang Trinh, Belaid Benhamou, Sylvain Soliman & François Fages (2024): *On the trap space semantics of logic programs, basic properties and relevance to program analysis*. Submitted paper.

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

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