# Continuous Petri Nets Faithfully Fluidify Most Permissive Boolean Networks

Stefan Haar, Juri Kolčák

► To cite this version:

Stefan Haar, Juri Kolčák. Continuous Petri Nets Faithfully Fluidify Most Permissive Boolean Networks. CMSB 2025 - 23rd International Conference on Computational Methods in Systems Biology, Sep 2025, Lyon, France. hal-05115273

HAL Id: hal-05115273

https://inria.hal.science/hal-05115273v1

Submitted on 16 Jun 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Continuous Petri Nets Faithfully Fluidify Most Permissive Boolean Networks

Stefan Haar¹ and Juri Kolčák²

¹ INRIA, France

stefan.haar@inria.fr

² Faculty of Technology, Bielefeld University, Germany

juri.kolcak@uni-bielefeld.de

**Abstract.** The analysis of biological networks has benefited from the richness of Boolean networks (BNs) and the associated theory. These results have been further fortified in recent years by the emergence of *Most Permissive (MP)* semantics, combining efficient analysis methods with a greater capacity of explaining pathways to states hitherto thought unreachable, owing to limitations of the classical update modes. While MPBNs are understood to capture any behaviours that can be observed at a lower level of abstraction, all the way down to continuous refinements, the specifics and potential of the models and analysis, especially attractors, across the abstraction scale remain unexplored. Here, we fluidify MPBNs by means of *Continuous Petri nets (CPNs)*, a model of (uncountably infinite) dynamic systems that has been successfully explored for modelling and theoretical purposes. CPNs create a formal link between MPBNs and their continuous dynamical refinements such as ODE models. The benefits of CPNs extend beyond the model refinement, and constitute well established theory and analysis methods, recently augmented by abstract and symbolic reachability graphs. These structures are shown to compact the possible behaviours of the system with focus on events which drive the choice of long-term behaviour in which the system eventually stabilises. The current paper brings an important keystone to this novel methodology for biological networks, namely the proof that extant PN encoding of BNs instantiated as a CPN simulates the MP semantics. In spite of the underlying dynamics being continuous, the analysis remains in the realm of discrete methods, constituting an extension of all previous work.

# 1 Introduction

Boolean networks (BNs) are a powerful and well-established formalism for modelling interacting entities as discrete dynamical systems, enjoying numerous and fruitful applications in live sciences, especially in the area of gene regulation [24, 10, 18, 12].

Boolean networks are considered with multiple different semantics which differ in the “schedule” of variable updates with heavy influence on the dynamics of the model. The classical semantics for BNs are:
- fully asynchronous (often simply asynchronous in literature): only one variable, chosen nondeterministically, updates value in an update round;

- synchronous: all variables update value simultaneously; and

- (generalised) asynchronous: any nondeterministically chosen subset of variables update value simultaneously.

Generalised asynchronous semantics had been considered the all-encompassing updating mode of BNs, capable of expressing all possible behaviours. However, an element of gene regulation incompatible with the classical semantics has been introduced in [17]. The real-world example generates a short term pulse by means of interaction activation thresholds, which distinguish between fast-and slow-acting interactions. The abstraction of such thresholds implicit in the asynchronous semantics fails to capture the observed behaviour, making an extension of the classical BN semantics necessary.

Most permissive (MP) semantics of BNs have been developed [19,8,7] to address this challenge. Instead of switching variable values directly between 0 and 1, MP semantics introduces intermediate dynamic states which can be read, nondeterministically, as either 0 or 1 when updating variables, thus effectively allowing for any combination of activation thresholds. BNs with MP semantics (MPBNs) are proven to capture all behaviours expressed at a level of any multivalued or continuous refinement [19], including the above pulse generator.

MPBNs can be seen as one extremal point of the abstraction scale of dynamical system models, the other being ODE models such as Chemical Reaction Networks. The exact nature of the space between the discrete and continuous models is, however, largely unexplored. We hope to open avenues for the study of that middle ground by establishing a connection between MPBNs and *continuous Petri nets* (CPNs) [9,14].

The connection between discrete Petri nets (DPNs) and Boolean, or more generally, multivalued discrete networks, and especially the encoding of BNs as DPNs, is a well studied topic for classical BN semantics [5,4,6,7]. In this paper we extend these results to encompass the MP semantics with the aid of CPNs, a model with discrete time but continuous state space, where a transition firing may modify non-integer quantities of token mass. In fact, we demonstrate that the encoding of fully asynchronous BNs as safe DPNs used in those works, is also pertinent for encoding MPBNs as CPNs with no modifications to the net structure (but, of course, a continuous semantics). Rather than a formal comparison of expressiveness (see e.g. [3]), our aim is a new practical tool for behaviour representation and analysis. A key outcome is the ability to use abstract tools for CPN analysis to characterise the long-term behaviour of MPBNs, as demonstrated on a small but biologically relevant example.

# 2 Definitions

## 2.1 Boolean Networks

A BN of dimension $n \in \mathbb{N}$ (on $n$ variables) is a Boolean function $f: \mathbb{B}^n \to \mathbb{B}^n$, typically treated component-wise as local functions $f_i: \mathbb{B}^n \to \mathbb{B}$ giving the evo-
lution of the variables $i \in \{1, \dots, n\}$, $f = (f_1, \dots, f_n)$. Assigning a value to each variable constitutes a configuration $\mathbf{x}$: $\{1, \dots, n\} \to \mathbb{B}$, equivalently defined as an $n$-ary Boolean vector, $\mathbf{x} \in \mathbb{B}^n$. An example BN network defined by local

$$ 
\begin{aligned}
f_1(\mathbf{x}) &= \neg \mathbf{x}_2 \\
f_2(\mathbf{x}) &= \neg \mathbf{x}_1 \\
f_3(\mathbf{x}) &= \neg \mathbf{x}_1 \wedge \mathbf{x}_2.
\end{aligned}
 $$

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** A running example BN on three variables (left) with its interaction graph (right). Positive interactions are depicted by pointed green arrows while negative interactions are depicted by flat red arrows. The example is taken from [19] where its biological relevance is also discussed.</figcaption></figure>

functions and the associated interaction graph are given in Figure 1. An interaction graph connects variables that interact, and indicates the nature (positive vs negative) of those interaction, e.g. the mutual negative interactions between variables 1 and 2 in the example BN. The exact interplay of those interactions, e.g. the “and” in $f_3$ as opposed to an “or”, are abstracted away.

For a BN $f$ of dimension $n$ and any two configurations $\mathbf{x}, \mathbf{y} \in \mathbb{B}^n$, let $\Delta(\mathbf{x}, \mathbf{y}) = \{i \in \{1, \dots, n\} \mid \mathbf{x}_i \neq \mathbf{y}_i\}$ be the set of all variables whose value differs between $\mathbf{x}$ and $\mathbf{y}$. Then the fully asynchronous semantics of $f$, $fa(f)$, synchronous semantics of $f$, $syn(f)$, and asynchronous semantics of $f$, $ga(f)$ are defined as follows for any pair of configurations $\mathbf{x}, \mathbf{y} \in \mathbb{B}^n$:

$$ 
\begin{aligned}
(\mathbf{x}, \mathbf{y}) \in fa(f) &\iff \exists i \in \{1, \dots, n\}, \Delta(\mathbf{x}, \mathbf{y}) = \{i\} \wedge f_i(\mathbf{x}) = y_i \\
(\mathbf{x}, \mathbf{y}) \in syn(f) &\iff \forall i \in \{1, \dots, n\}, f_i(\mathbf{x}) = y_i \\
(\mathbf{x}, \mathbf{y}) \in ga(f) &\iff \forall i \in \Delta(\mathbf{x}, \mathbf{y}), f_i(\mathbf{x}) = y_i
\end{aligned}
 $$

It follows immediately that $fa(f) \subseteq ga(f)$ as well as $syn(f) \subseteq ga(f)$.

We use the natural infix notation for the semantics relations, e.g. $\mathbf{x} \xrightarrow{fa} \mathbf{y}$, and omit the BN $f$ where obvious, $\mathbf{x} \xrightarrow{fa} \mathbf{y}$. The associated reachability relations are obtained as the reflexive and transitive closures of the semantics relations, $\mathbf{x} \xrightarrow{fa} \mathbf{y}^*$, etc.

Configurations of the example BN from Figure 1 reachable from $(0, 0, 0)$ under fully asynchronous or asynchronous semantics are visualised in Figure 2. Synchronous semantics are omitted, as the only reachable configurations are $(1, 1, 0)$ and $(0, 0, 0)$ itself (the cycle in asynchronous reachability).

We now introduce the MP semantics of BNs [19,8]. While there are different formalisations of the semantics [19,20], we will present here the original definition [19]. MP differ from the classical semantics by introduction of two transient
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** All configurations of the example BN (Figure 1) reachable from (0, 0, 0) under fully asynchronous semantics (left) and asynchronous semantics (right). The variables are ordered from top to bottom and dark tiles represent value 0 while light tiles represent value 1. Self-loops are omitted.</figcaption></figure>

(or dynamic) values, ↗ to signify that a variable is increasing from 0 to 1 and ↘ to signify that a variable is decreasing from 1 to 0.

For a BN $f$ of dimension $n$ and any MP configuration $\hat{\mathbf{x}} \in \{0, 1, ↗, ↘\}^n$, let $\beta(\hat{\mathbf{x}}) = \{\mathbf{x} \in \mathbb{B}^n | \forall i \in \{1, \dots, n\}, \hat{\mathbf{x}}_i \in \mathbb{B} \Rightarrow \mathbf{x}_i = \hat{\mathbf{x}}_i\}$ be the set of compatible binarisations expressed as Boolean configurations. Then, the MP semantics of a BN $f$, $\hat{m}_p(f)$, is defined as follows for any pair of MP configurations $\hat{\mathbf{x}}, \hat{\mathbf{y}} \in \{0, 1, ↗, ↘\}^n$:

$$ (\hat{\mathbf{x}}, \hat{\mathbf{y}}) \in \hat{m}_p(f) \iff \exists i \in \{1, \dots, n\}, \Delta(\hat{\mathbf{x}}, \hat{\mathbf{y}}) = \{i\} \wedge [(\hat{\mathbf{x}}_i = ↗ \wedge \hat{\mathbf{y}}_i = 1) \vee \\ (\hat{\mathbf{x}}_i = ↘ \wedge \hat{\mathbf{y}}_i = 0) \vee \\ (\hat{\mathbf{x}}_i \neq 1 \wedge \hat{\mathbf{y}}_i = ↗ \wedge \exists \mathbf{x} \in \beta(\hat{\mathbf{x}}), f_i(\mathbf{x}) = 1) \vee \\ (\hat{\mathbf{x}}_i \neq 0 \wedge \hat{\mathbf{y}}_i = ↘ \wedge \exists \mathbf{x} \in \beta(\hat{\mathbf{x}}), f_i(\mathbf{x}) = 0)] $$

The top two lines of the disjunction enable a variable in a transient value to collapse into the target Boolean value at any time. The bottom two lines dictate that for a variable to change to a transient value, a binarisation must exist for which the local function returns the target Boolean value of said transient value.

As we are mostly interested in Boolean configurations, we restrict the MP semantics accordingly, thus for any $\mathbf{x}, \mathbf{y} \in \mathbb{B}^n$:

$$ (\mathbf{x}, \mathbf{y}) \in mp(f) \iff \mathbf{x} \underset{f}{\stackrel{\hat{m}_p}{\longrightarrow}}^* \mathbf{y} $$

We have $ga(f) \subseteq mp(f)$ as any asynchronous update is reproduced by first putting all relevant variables into transient value and subsequently collapsing them. The inclusion is strict in general, as shown in Figure 3 of all Boolean configurations of the example BN from Figure 1 reachable under MP semantics.

## 2.2 Petri Nets

A Petri net has as a skeleton a bipartite directed graph with two sets of nodes, *places* and *transitions*. Places model resource types available in the system, and
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** All Boolean configurations of the example BN (Figure 1) reachable from (0, 0, 0) under MP semantics. While the fixed points are preserved, all other configurations become transiently reachable, as opposed to asynchronous semantics.</figcaption></figure>

can hold a certain amount of *tokens* or *token mass* representing availability of the resource. Transitions allow removing (reducing) or adding tokens (token mass), according to the *arcs* connecting them to places. A simple example net is visualised in Figure 4 on the left.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Left: An example net with two places (depicted as circles) and two transitions (depicted as squares). The arc weight $W(p_2, t_2) = 2$ indicating that $t_2$ consumes “two tokens” is depicted as a label on the arrow. As per convention, arc weights equal to 1 are omitted. Right: An example of a transition firing in a DPN with the same net structure. The tokens assigned by the markings are depicted as black dots inside the places.</figcaption></figure>

Formally, a *net* is a tuple $N = (P, T, W)$, where $P$ is a finite set of places, $T$ is a finite set of transitions and $W: (P \times T) \cup (T \times P) \to \mathbb{N}_0$ is a weight function
assigning each transition the amount of resources consumed or produced in each place. For $x, y \in P \cup T$, we say there is an arc from $x$ to $y$ if $W(x, y) > 0$.

For each place or transition $x \in P \cup T$, we call $\bullet x = \{y \in P \cup T | W(y, x) > 0\}$ the pre-set of $x$. Similarly, $x^\bullet = \{y \in P \cup T | W(x, y) > 0\}$ is the post-set of $x$.

The transitions, as opposed to the functions of BNs, define both the discrete and the continuous semantics of Petri nets. In both cases, a single transition is nondeterministically chosen to be fired, consuming tokens (token mass) in the pre-set and producing tokens (token mass) in the post-set. While transitions can only consume and produce whole tokens in the discrete case, any positive real-valued $(\mathbb{R}_0^+)$ amounts of token mass can be used under the continuous semantics. In the following we formalise the semantics for both DPNs and CPNs.

**Discrete Petri Nets (DPNs).** A DPN $\mathcal{N} = (N, M_0)$ is a net $N = (P, T, W)$ with a (discrete) marking $M_0: P \to \mathbb{N}_0$, called the initial marking.

A transition $t \in T$ is enabled at a marking $M: P \to \mathbb{N}_0$, denoted $M \xrightarrow{t},$ if and only if $\forall p \in \bullet t, M(p) \ge W(p, t)$. An enabled transition can fire, $M \xrightarrow{t} M'$, leading to a new marking $M'$ defined for each $p \in P$ as follows:

$$M'(p) \triangleq M(p) - W(p, t) + W(t, p)$$

Let us consider the example net from Figure 4 with the initial marking $M_0 = \{(p_1, 1), (p_2, 0)\}$. Transition $t_1$ is enabled at $M_0$, leading to marking $M_1 = \{(p_1, 0), (p_2, 1)\}$ as illustrated in Figure 4 on the right hand side. $M_1$, however, is a deadlock, a marking at which no transition is enabled.

A finite firing sequence is a word $w = (t_i)_{i<n \in \mathbb{N}_0}$ over $T$ for which there exists a sequence of markings $(M_i)_{i<n+1}$ such that $M_i \xrightarrow{t_i} M_{i+1}$ for all $i < n$. We denote the set of markings reachable from some marking $M$ in $\mathcal{N}$ by $RS_{\mathcal{N}}(M) = \{M' | \exists w \in T^*, M \xrightarrow{w} M'\}$, or simply $RS(M)$ where $\mathcal{N}$ is obvious.

**Continuous Petri nets.** Like a DPN, a CPN $\mathcal{N} = (N, \mathbf{m}_0)$ is a net $N = (P, T, W)$ with an initial marking $\mathbf{m}_0$; however, in CPNs the place markings are positive real-valued amounts of token mass, $\mathbf{m}_0: P \to \mathbb{R}_0^+$. In CPNs, there is a degree to transitions being enabled.<fnref n="1" /> Formally, $t \in T$ has an enabling degree given by $enab(t, \mathbf{m}) = \min_{p \in \bullet t} \frac{m(p)}{W(p, t)}$ when $\bullet t \neq \emptyset$, and equal to $\infty$ otherwise. The enabling degree is the firing bound determined by the minimal ratio of token mass divided by arc weight over all pre-places. A transition with $enab(t, \mathbf{m}) > 0$ is enabled at $\mathbf{m}$ and can $\alpha$-fire for any $\alpha \in [0, enab(t, \mathbf{m})] \cap \mathbb{R}$, $\mathbf{m} \xrightarrow{\alpha t} \mathbf{m}'$. That is, an enabled $t$ has a continuum of firing possibilities. An $\alpha$-firing of $t$ leads to a new marking $\mathbf{m}'$ defined for each $p \in P$ as follows:

$$\mathbf{m}'(p) \triangleq \mathbf{m}(p) - \alpha W(p, t) + \alpha W(t, p)$$

<footnote n="1">¹ A detailed introduction to CPNs is given in the book [9], where they are presented alongside discrete, timed, stochastic and hybrid models, allowing for comparisons among the models. The theory of CPNs has been developed in a number of articles, of which we cite here [16, 21, 23, 14, 2]. The work on untimed CPNs that most closely relates to the current article (and, so to say, triggered this research), is [15].</footnote>
Note that the Petri net on the right hand side of Figure 4 would, under the CPN semantics, be able to fire $t_2$, with any $\alpha \in [0, 0.5]$.

A finite firing sequence is a finite word $\sigma = (\alpha_i t_i)_{i<n \in \mathbb{N}_0}$ over $\mathbb{R}_0^+ \times \mathcal{T}$ for which there exists a finite sequence of markings $(\mathbf{m}_i)_{i<n+1}$ such that $\mathbf{m}_i \xrightarrow{\alpha_i t_i} \mathbf{m}_{i+1}$ for all $i < n$. It has been noted in the CPN literature, that the conventional notion of reachability, based on finite sequences, is less 'natural' for CPNs than reachability in the limit, which is also easier to verify [14]. Let thus an infinite firing sequence be an infinite word $\sigma = (\alpha_i t_i)_{n \in \mathbb{N}_0}$ over $\mathbb{R}_0^+ \times \mathcal{T}$ for which there exists an infinite family of markings $(\mathbf{m}_i)_{i \le \omega}$ such that $\mathbf{m}_i \xrightarrow{\alpha_i t_i} \mathbf{m}_{i+1}$ for all $i \in \mathbb{N}_0$ and the limit $\lim_{i \to \infty} \mathbf{m}_i = \mathbf{m}_\omega$ exists.

Denote the set of markings reachable from some marking $\mathbf{m}$ in $\mathcal{N}$ by $\mathbf{RS}_{\mathcal{N}}(\mathbf{m}) = \{\mathbf{m}' \mid \exists \sigma \in (\mathbb{R}_0^+ \times \mathcal{T})^*, \mathbf{m} \xrightarrow{\sigma} \mathbf{m}'\}$. Further, denote the set of markings reachable in the limit (lim-reachable) from some marking $\mathbf{m}$ in $\mathcal{N}$ by $\lim-\mathbf{RS}_{\mathcal{N}}(\mathbf{m}) = \{\mathbf{m}' \mid \exists \sigma \in (\mathbb{R}_0^+ \times \mathcal{T})^\omega, \mathbf{m} \xrightarrow{\sigma} \mathbf{m}'\}$. Since an infinite firing sequence can include null firings ($\alpha = 0$), we have $\mathbf{RS}_{\mathcal{N}}(\mathbf{m}) \subseteq \lim-\mathbf{RS}_{\mathcal{N}}(\mathbf{m})$. We write simply $\mathbf{RS}(\mathbf{m})$ and $\lim-\mathbf{RS}(\mathbf{m})$ where $\mathcal{N}$ is obvious.

A DPN all of whose reachable markings have at most one token per place, $\forall M \in \mathbf{RS}(M_0), \forall \mathbf{p} \in \mathcal{P}, M(\mathbf{p}) \le 1$, is *safe* (also 1-bounded). Similarly, a CPN all of whose reachable markings have token mass at most 1 per place, $\forall \mathbf{m} \in \mathbf{RS}(m_0), \forall \mathbf{p} \in \mathcal{P}, \mathbf{m}(\mathbf{p}) \le 1$, is safe. The notions of safeness and lim-safeness coincide [22]. The PN encoding of BNs utilised in Section 3 produces safe DPNs/CPNs.

**Abstractions.** The ability to fire a transition by varying degree means that there are infinitely many possible firings in any marking at which at least one transition is enabled. We therefore cannot visualise all the possible transition firings of a CPN in the same fashion as Figure 4 does for a DPN. Symbolic analysis methods have therefore been introduced for CPN dynamics, namely abstract reachability graphs (ARG) and symbolic reachability trees (SRT) [15].

The ARG constitutes an abstraction of the state space by collapsing markings that have the same *support*, i.e. the set of places which have non-zero token mass, $[[\mathbf{m}]] \triangleq \{\mathbf{p} \in \mathcal{P} \mid \mathbf{m}(\mathbf{p}) > 0\}$, into equivalence classes. Supports are linked between one another by two types of edges, *anonymous* and *border*, both representing the possibility of the system evolving into a marking with different support. Border edges are of special interest, as they represent occurrences that *permanently disable* one or more transitions, thus shaping the reachability landscape.

The SRT provides a refined view at such a landscape in the form of a directed tree linked by border edges. The nodes of the tree are aggregations of markings by their *mode*, i.e. the set of transitions eventually fireable from the given marking: $T_{\mathbf{m}} \triangleq \{\mathbf{t} \in \mathcal{T} \mid \exists \mathbf{m} \xrightarrow{\sigma}, \mathbf{t} \in [[\sigma]]\}$, where $[[\sigma]]$ is the set of all transitions occurring along $\sigma$ with $\alpha > 0$. The branches of the tree then indicate refinements of those modes, as less and less transitions remain available. The depth of the SRT is naturally bounded by $|\mathcal{T}|$.

We omit the formal definition of ARG and SRT due to space constraints. The reader is instead referred to [15]. Both the ARG and SRT of the example net are illustrated in Figure 5.
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** The ARG (left) and the SRT (right) of the example net from Figure 4. The border edges are given as double line arrows in the ARG. The SRT for this example is trivial, as there is only one border edge.</figcaption></figure>

As mentioned above, $t_2$, which cannot fire in a DPN, can be fired under continuous semantics with the same initial marking $m_0 = M_0$. All reachable markings, under both semantics, have a total token mass (of $p_1$ and $p_2$ combined) contained in (0, 1]. The total token mass can only be reduced, by firing $t_2$, but the empty marking $m = \{(p_1, 0), (p_2, 0)\}$ is not reachable, as after any finite number of $t_2$ firings, there will always be some token mass left. The empty marking, however, is lim-reachable using the infinite firing sequence $\sigma = t_1(2^{-n}t_22^{-n}t_1)_{n \in \mathbb{N}}$. This phenomenon is illustrative, as the two places of the net are a trap, that is $\{p_1, p_2\}^\bullet \subseteq \{p_1, p_2\}$. It is a well known result for DPNs that an initially marked trap cannot be emptied [11], which intuitively extends to finite reachability in CPNs.

## 3 Petri Net Encoding of Boolean Networks

In this section, we introduce the encoding of BNs as safe PNs. We make use of an elegant encoding given in [7]. Due to the focus on concurrency, the original encoding contains so called contextual (or read) arcs. Read arcs can be replaced equivalently with loops, allowing to obtain the same behaviour with an ordinary net structure. We reiterate the definition of [7] without read arcs, but we first require some additional notation for formal reasoning about Boolean functions.

For any variable $i \in \{1, \dots, n\}$ of a BN $f$, $\delta^+(i) = \text{DNF}(\neg x_i \land f_i(x))$ denotes the set of conjunctive clauses of the disjunctive normal form of the function allowing $i$ to increase value. Similarly, $\delta^-(i) = \text{DNF}(x_i \land \neg f_i(x))$ the set of clauses of the function allowing $i$ to decrease value. Finally, $\delta^+(i) = \delta^-(i) \cup \delta^-(i)$ is the set of all clauses pertaining to variable $i$.

We say a configuration $\mathbf{y} \in \mathbb{B}^n$ satisfies a clause $C$, $\mathbf{y} \models C$, if for each positive literal $[x_j] \in C$, $\mathbf{y}_j = 1$ and for each negative literal $[\neg x_j] \in C$, $\mathbf{y}_j = 0$.

**Definition 1 (Petri Net Encoding of Boolean Networks).** Given a BN $f$ of dimension $n$, the Petri net encoding of $f$ is the net $N(f) = (\mathbf{P}, \mathbf{T}, \mathbf{W})$ where
$P \triangleq \{1, \dots, 2n\}$, $T \triangleq \bigcup_{i \in \{1, \dots, n\}} \{t_C \mid C \in \delta(i)\}$ and $W$ is 1 in all the following cases for every $i \in \{1, \dots, n\}$, and $W(x, y) \triangleq 0$ otherwise:

$$ \forall C \in \delta^{+}(i), W(i, t_C) = W(t_C, i + n) \triangleq 1 \quad (1) $$

$$ \forall C \in \delta^{-}(i), W(i + n, t_C) = W(t_C, i) \triangleq 1 \quad (2) $$

$$ \forall C \in \delta(i), \forall [\neg x_j] \in C, j \neq i, W(j, t_C) = W(t_C, j) \triangleq 1 \quad (3) $$

$$ \forall C \in \delta(i), \forall [x_j] \in C, j \neq i, W(j + n, t_C) = W(t_C, j + n) \triangleq 1 \quad (4) $$

Each variable $i \in \{1, \dots, n\}$ is represented by two places, $i, i+n$, which correspond to variable $i$ valued 0 or 1, respectively. The transitions correspond to the clauses of the local functions of the BN. For each variable $i \in \{1, \dots, n\}$, we use $T_i^+ = \{t_C \in T \mid C \in \delta^+(i)\}$ to denote the transitions that increase the value of $i$. Similarly, $T_i^- = \{t_C \in T \mid C \in \delta^-(i)\}$ denotes the transitions decreasing value of $i$, and $T_i = T_i^+ \cup T_i^-$ are all transitions acting on the variable $i$.

Note that $N(f)$ is up to exponentially larger than $f$; however, as the exponent depends only on the maximal in-degree in the interaction graph, rather than the vertex count, the blow-up is manageable for sparse networks.

Finally, the arcs fall into two categories. The first two lines (1,2) describe variables increasing, respectively decreasing, value as an effect of the associated transition. The last two lines (3,4) describe the loops on places which encode the negative and positive interactions with the target variable.

The above structure guarantees two useful properties. For each variable $i \in \{1, \dots, n\}$, only transitions in $T_i$ can modify the marking of places $i, i+n$, and $\{i, i+n\}$ is a P-invariant, thus the sum of the tokens (token mass) in $i$ and $i+n$ remains constant in all reachable markings [1,11].

**As DPNs.** Let $\mathbf{x} \in \mathbb{B}^n$ be a configuration of the BN $f$; define the corresponding discrete marking of $N(f)$ as $\langle \mathbf{x} \rangle = \{i + n\mathbf{x}_i \mid i \in \{1, \dots, n\}\}$. The net encoding of the example BN with initial marking $\langle (0, 0, 0) \rangle = \{1, 2, 3\}$ is depicted in Figure 6.

As a DPN, either $t_1: [\neg x_2]$ to activate 1 or $t_2: [\neg x_1]$ to activate 2 can fire, reaching $\{2, 3, 4\} = \langle (1, 0, 0) \rangle$ or $\{1, 3, 5\} = \langle (0, 1, 0) \rangle$, respectively. The first case is a deadlock, corresponding to the fixed point of the BN. In the second case, $t_3: [\neg x_1], [x_2]$ can fire to reach the second deadlock $\{1, 5, 6\} = \langle (0, 1, 1) \rangle$, perfectly reproducing the fully asynchronous semantics of the BN (Figure 2). This correspondence holds for any BN, Theorem 1 of [7] proves that the DPN $N(f)$ emulates $f$ with fully asynchronous semantics, i.e. any BN update is reflected by an enabled transition between corresponding markings of the DPN and vice-versa, formally:

$$ \forall \mathbf{x}, \mathbf{y} \in \mathbb{B}^n, \mathbf{x} \underset{f}{\stackrel{fa}{\to}} \mathbf{y} \iff \exists \mathbf{t} \in \mathcal{T}, \langle \mathbf{x} \rangle \underset{N(f)}{\stackrel{t}{\to}} \langle \mathbf{y} \rangle $$

This equivalence naturally extends to the reachability relation:

$$ \forall \mathbf{x}, \mathbf{y} \in \mathbb{B}^n, \mathbf{x} \underset{f}{\stackrel{fa}{\to}}^* \mathbf{y} \iff \langle \mathbf{y} \rangle \in \mathbf{RS}_{N(f)}(\langle \mathbf{x} \rangle) $$
<figure><img src="image_7.png" /><figcaption>**Fig. 6.** The PN encoding of the example BN given in Figure 1. Double headed arrows are used to depict loops, in order to avoid clutter. - From the initial marking {1, 2, 3}, markings {3, 4, 5} and {4, 5, 6} are **unreachable** under DPN semantics, and even with finite CPN firing sequences; both are, however, lim-reachable from {1, 2, 3}. This illustrates how lim-reachability is necessary to reflect MP semantics; Theorem 1 shows that it is also sufficient.</figcaption></figure>

Observe that the synchronous update reaching configuration (1, 1, 0) in the asynchronous semantics is not captured by a DPN. This follows from the fact that {1, 2} ⊆ P is an initially marked trap, and therefore cannot be emptied. Synchronous or asynchronous semantics of BNs thus cannot be reproduced by a DPN without further structural modification or special semantics [7].

**As CPNs.** In the context of the example as a CPN, (1, 1, 0) is lim-reachable by $(2^{-n}t_1: [\neg x_2]2^{-n}t_2: [\neg x_1])_{n \in N}$, illustrating that lim-reachability covers synchronous reachability. Furthermore, the configuration (1, 1, 1), reachable in MPBN but neither in BN with asynchronous semantics, nor with finite firing sequences in CPNs, {1, 2, 3} ⊆ P once again being an initially marked trap, is lim-reachable, as witnessed by the sequence $(2^{-n}t_1: [\neg x_2]2^{-n}t_2: [\neg x_1]2^{-n}t_3: [\neg x_1],[x_2])_{n \in N}$. Indeed, we show below that using the PN encoding of Definition 1 instantiated as a CPN, an equivalence can be established between reachability in an MPBN and lim-reachability in its CPN encoding. First, some notation.

The places of the net encoding are an interval of natural numbers, the continuous markings are thus vectors, $\mathbf{m} \in \mathbb{R}_0^{+2n}$. Let $\hat{\mathbf{x}} \in \{0, 1, \uparrow, \downarrow\}^n$ be a configuration of MPBN $f$. The set of all compatible continuous markings is:

$$ \mu(\hat{\mathbf{x}}) \triangleq \{\mathbf{m} \in \mathbb{R}_0^{+2n} \mid \forall i \in \{1, \dots, n\}, \mathbf{m}_i + \mathbf{m}_{i+n} = 1 \\ \qquad \wedge \hat{\mathbf{x}}_i \in \mathbb{B} \implies \mathbf{m}_i = 1 - \hat{\mathbf{x}}_i \\ \qquad \wedge \hat{\mathbf{x}}_i \in \{\uparrow, \downarrow\} \implies 0 < \mathbf{m}_i < 1\} $$
Of special interest is the marking $\langle \hat{\mathbf{x}} \rangle$ defined as follows for all $i \in \{1, \dots, n\}$:

$$ \langle \hat{\mathbf{x}} \rangle_i, \langle \hat{\mathbf{x}} \rangle_{i+n} \triangleq \begin{cases} 1 - \hat{\mathbf{x}}_i, \hat{\mathbf{x}}_i & \text{if } \hat{\mathbf{x}}_i \in \mathbb{B} \\ 0.5, 0.5 & \text{if } \hat{\mathbf{x}}_i \in \{\uparrow, \downarrow\} \end{cases} $$

Clearly, $\langle \hat{\mathbf{x}} \rangle \in \mu(\hat{\mathbf{x}})$; for $\hat{\mathbf{x}} \in \mathbb{B}^n$, the definition coincides with the one for the discrete markings, $\langle \hat{\mathbf{x}} \rangle = \langle \mathbf{x} \rangle$ where $\{\mathbf{x}\} = \beta(\hat{\mathbf{x}})$.

**Theorem 1 (Continuous Petri Nets Simulate MP Boolean Networks).**

Let $f$ be a Boolean network of dimension $n$. Then, for any configurations $\mathbf{x}, \mathbf{y} \in \mathbb{B}^n$, $\mathbf{x} \xrightarrow{f}^* \mathbf{y} \iff \langle \mathbf{y} \rangle = \lim_{\mathbf{x}} \mathbf{R} \mathbf{S}_{N(f)}(\langle \mathbf{x} \rangle)$.

To prove Theorem 1, we first state a few helper lemmas that establish the relationship between a reachable MPBN configuration $\hat{\mathbf{x}}$ and the corresponding marking $\langle \hat{\mathbf{x}} \rangle$.

**Lemma 1.** Given a BN $f$ of dimension $n$, a configuration $\hat{\mathbf{x}} \in \{0, 1, \uparrow, \downarrow\}^n$, a transition $t \in T_i$ and a marking $\mathbf{m} \in \mu(\hat{\mathbf{x}})$ such that $\mathrm{enab}(t, \mathbf{m}) > 0$, then for any other marking $\mathbf{m}' \in \mu(\hat{\mathbf{x}})$, $\mathrm{enab}(t, \mathbf{m}') > 0$.

If $\mathbf{m}' = \langle \hat{\mathbf{x}} \rangle$, additionally $\mathrm{enab}(t, \langle \hat{\mathbf{x}} \rangle) \ge 0.5$.

*Proof.* For any two markings $\mathbf{m}, \mathbf{m}' \in \mu(\hat{\mathbf{x}})$ and for each place $p \in P$, it holds that $\mathbf{m}_p = 0 \iff \mathbf{m}'_p = 0$. Since $p \in \bullet t$ implies $\mathbf{m}_p > 0$, necessarily also $\mathbf{m}'_p > 0$.

For $\langle \hat{\mathbf{x}} \rangle$, we have $\langle \hat{\mathbf{x}} \rangle_p \ne 0 \implies \langle \hat{\mathbf{x}} \rangle_p \ge 0.5$ by definition.

**Lemma 2.** Given a BN $f$ of dimension $n$, a transition $t \in T_i^+$ (respectively $t \in T_i^-$) and a marking $\mathbf{m} \in \mathbb{R}_0^{+2n}$ such that $\mathrm{enab}(t, \mathbf{m}) > 0$, then for any $\hat{\mathbf{x}} \in \{0, 1, \uparrow, \downarrow\}^n$ such that $\mathbf{m} \in \mu(\hat{\mathbf{x}})$ and $\hat{\mathbf{x}}_i \in \{0, \downarrow\}$ (respectively $\hat{\mathbf{x}}_i \in \{1, \uparrow\}$), $\hat{\mathbf{x}} \xrightarrow{\mathrm{mp}}^f \hat{\mathbf{y}}$ where $\hat{\mathbf{y}}_i = \uparrow$ (respectively $\hat{\mathbf{y}}_i = \downarrow$).

*Proof.* Since the cases for $t \in T_i^+$ and $t \in T_i^-$ are symmetrical, we only show the proof for $t \in T_i^+$. Let $C(t) \in \delta^+(i)$ be the clause corresponding to $t$.

Let $[\neg \mathbf{x}_j] \in C(t)$ be an arbitrary negative literal. Since $\mathrm{enab}(t, \mathbf{m}) > 0$, $\mathbf{m}_j > 0$ and by $\mathbf{m} \in \mu(\hat{\mathbf{x}})$, $\hat{\mathbf{x}}_j \in \{0, \uparrow, \downarrow\}$. Similarly, let $[\mathbf{x}_j] \in C(t)$ be an arbitrary positive literal. Again from $\mathrm{enab}(t, \mathbf{m}) > 0$, $\mathbf{m}_{i+n} > 0$ and by $\mathbf{m} \in \mu(\hat{\mathbf{x}})$, $\hat{\mathbf{x}}_j \in \{1, \uparrow, \downarrow\}$.

As such, there must exist a configuration $\mathbf{z} \in \beta(\hat{\mathbf{x}})$ such that $\mathbf{z} \models C(t)$, and thus variable $i$ is allowed to increase value, $\hat{\mathbf{x}} \xrightarrow{\mathrm{mp}}^f \hat{\mathbf{y}}$.

**Lemma 3.** Given a BN $f$ of dimension $n$ and two configurations $\hat{\mathbf{x}}, \hat{\mathbf{y}} \in \{0, 1, \uparrow, \downarrow\}^n$ such that for any $i \in \{1, \dots, n\}$, $\hat{\mathbf{x}}_i \in \mathbb{B} \implies \hat{\mathbf{y}}_i = \hat{\mathbf{x}}_i$, then for any transition $t \in T$, $\mathrm{enab}(t, \langle \hat{\mathbf{y}} \rangle) \ge 0.5 \implies \mathrm{enab}(t, \langle \hat{\mathbf{x}} \rangle) \ge 0.5$.

*Proof.* Let $p \in \bullet t$ be arbitrary and let $j = p - n$ for $p > n$, be the BN variable whose value assignment $p$ represents. We now conduct discussion on the nature of the value of $j$ in $\hat{\mathbf{x}}$.
The case of $\hat{x}_j \in \{\uparrow, \downarrow\}$ is simple as we have $\langle \hat{x} \rangle_p = 0.5$ by definition.

Let thus $\hat{x}_j \in \mathbb{B}$. By assumption, $\hat{x}_j \in \mathbb{B} \implies \hat{x}_j = \hat{y}_j$. Since $\text{enab}(t, \langle \hat{y} \rangle) \ge 0.5$, we necessarily have $\langle \hat{y} \rangle_p = 1 = \langle \hat{x} \rangle_p$.

**Lemma 4.** Given a BN $f$ of dimension $n$ and configurations $\hat{x} \xrightarrow{\hat{m}_p} \hat{y}$ such that $\hat{y}_i = \uparrow$ (respectively $\hat{y}_i = \downarrow$), where $i = \Delta(\hat{x}, \hat{y})$, then there exists a transition $t \in T_i^+$ (respectively $t \in T_i^-$) such that $\text{enab}(t, \langle \hat{x} \rangle) \ge 0.5$.

*Proof.* Similarly to Lemma 2, the cases $\hat{y}_i = \uparrow$ and $\hat{y}_i = \downarrow$ are symmetrical. We thus conduct the proof only for $\hat{y}_i = \uparrow$.

Since $\hat{x} \xrightarrow{\hat{m}_p} \hat{y}$, there must exist a binarisation $z \in \beta(\hat{x})$ such that $f_i(z) = 1$ and therefore a clause $C \in \delta^+(i)$, such that $z \models C$. Let $t_C \in T_i^+$ be the transition corresponding to $C$ as per Definition 1.

We know $\hat{x}_i \in \{0, \downarrow\}$ and thus $\langle \hat{x} \rangle_i \ge 0.5$. Let then $j \in \{1, \dots, n\}, j \ne i$ be an arbitrary variable such that $j \in \text{t}_C$. By Definition 1, $[\neg x_j] \in C$. Then by $z \models C, z_j = 0$ and since $z \in \beta(\hat{x}), \hat{x}_j \in \{0, \uparrow, \downarrow\}$ and $\langle \hat{x} \rangle_j \ge 0.5$.

Similarly, for $j \in \{1, \dots, n\}, j \ne i$ such that $j+n \in \text{t}_C$, we have $[x_j] \in C$. By $z \models C, z_j = 1$ and since $z \in \beta(\hat{x}), \hat{x}_j \in \{1, \uparrow, \downarrow\}$ and $\langle \hat{x} \rangle_{j+n} \ge 0.5$.

**Corollary 1.** Given a BN $f$ of dimension $n$ and configurations $\hat{x} \xrightarrow{\hat{m}_p} \hat{y}$ such that $\hat{x}_i \in \mathbb{B}$, where $\{i\} = \Delta(\hat{x}, \hat{y})$, then there exists $t \in T_i$ such that $\langle \hat{x} \rangle \xrightarrow{0.5t} \langle \hat{y} \rangle$.

Corollary 1 is a direct application of Lemma 4: a value change from Boolean to transient in the MPBN is directly reproducible in the CPN encoding.

We now conduct the proof of Theorem 1 separately for each direction of the equivalence. The proof relies on an MP-reachability result [19]; for any $x \xrightarrow{\hat{m}_p} * y$, there exists a witness $x = \hat{x}_0 \xrightarrow{\hat{m}_p} \hat{x}_1 \xrightarrow{\hat{m}_p} \dots \xrightarrow{\hat{m}_p} \hat{x}_k = y$ that can be split into three phases. The first phase, $x = \hat{x}_0 \xrightarrow{\hat{m}_p} \dots \xrightarrow{\hat{m}_p} \hat{x}_h = \hat{z}$, consists only of variables changing value from Boolean to transient. In the second phase, $\hat{z} = \hat{x}_h \xrightarrow{\hat{m}_p} \dots \xrightarrow{\hat{m}_p} \hat{x}_{h'} = \hat{z}'$, all variables change value only between the two transient values and finally, in the third phase, $\hat{z}' = \hat{x}_{h'} \xrightarrow{\hat{m}_p} \dots \xrightarrow{\hat{m}_p} \hat{x}_k = y$, all variables collapse back into a Boolean value. Additionally, each variable changes value at most once in each of the phases.

As already illustrated on the example in Figure 6, finite reachability is not enough for some configurations. The proof thus constructs a discounted infinite firing sequence to reach the target marking, akin to the ones listed for lim-reachability of $\langle (1, 1, 0) \rangle$ and $\langle (1, 1, 1) \rangle$ for the Figure 6 example.

*Proof (the CPN retains all possible behaviours of the MPBN ("$\implies$" direction of Theorem 1)).* The first phase of the MPBN reachabilty witness, $x \xrightarrow{\hat{m}_p} \dots \xrightarrow{\hat{m}_p} \hat{z}$, fits the conditions of Corollary 1, immediately yielding $\langle x \rangle \rightarrow \dots \rightarrow \langle \hat{z} \rangle$. It remains to show $\langle y \rangle \in \lim \mathbf{RS}_{N(f)}(\langle \hat{z} \rangle)$.
We know that for any variable $i \in \{1, \dots, n\}, \hat{z}_i \in \mathbb{B}$ implies $\hat{z}_i = y_i$, and thus
$\langle \hat{z} \rangle_i = \langle y \rangle_i$ and $\langle \hat{z} \rangle_{i+n} = \langle y \rangle_{i+n}$. There is therefore no need to fire transitions in
$T_i$ and we only concern ourselves with variables having transient values in $\hat{z}$.

We now show that for every such variable $i \in \{1, \dots, n\}, \hat{z}_i \in \{\uparrow, \downarrow\}$, there exists a transition $t \in T_i$ exactly 0.5 enabled in $\hat{z}$, and such that the marking $\langle \hat{z} \rangle \xrightarrow{0.5t} m$ agrees with the target configuration $y$ of the variable $i, m_i = 1 - y_i$.

Let us first assume $\hat{z}_i = \hat{z}'_i$, i.e. the variable $i$ does not change value in the
second phase. Since $\hat{z}_i \in \{\uparrow, \downarrow\}$, we know there exists a unique transition $t \in T_i$
such that $\langle \hat{w} \rangle \xrightarrow{0.5t} \langle \hat{w}' \rangle$ occurs somewhere along the first phase, $\langle \mathbf{x} \rangle \rightarrow \dots \rightarrow \langle \hat{z} \rangle$.
For any variable $j \in \{1, \dots, n\}, \hat{z}_j \in \mathbb{B}$ implies $\hat{z}_j = \hat{w}_j$. We can thus apply
Lemma 3 to obtain $\text{enab}(t, \langle \hat{z} \rangle) \ge 0.5$. Finally, we know that by firing $t$ fully, the
value of $i$ becomes flipped, $\mathbf{x}_i = \mathbf{m}_i$. $\hat{z}_i = \hat{z}'_i$ necessarily means $y_i \ne \mathbf{x}_i$ and thus
$\mathbf{x}_i = \mathbf{m}_i = 1 - y_i$.

Let now $\hat{z}_i \ne \hat{z}'_i$ and let $\hat{v} = \hat{x}_g \xrightarrow{m\bar{p}} \hat{x}_{g+1} = \hat{v}',$ $h \le g < h'$ be the configurations along the second phase, such that $\Delta(\hat{v}, \hat{v}') = \{i\}$. By Lemma 4, there exists $t \in T_i$ such that $\text{enab}(t, \langle \hat{v} \rangle) \ge 0.5$. Since only changes between transient variable values occur in the second phase, we get $\langle \hat{v} \rangle = \langle \hat{z} \rangle$, thus $\text{enab}(t, \langle \hat{z} \rangle) \ge 0.5$. Without loss of generality, assume $\hat{v}'_i = \uparrow$ and thus also $t \in T_i^+$. Then we have $\mathbf{m}_i = 0$ and since the variable $i$ does not change value again in phase two, only collapses to a Boolean value in phase three, $y_i = 1$, or alternatively $1 - y_i = 0 = \mathbf{m}_i$.

We thus have a set of transitions $S \subseteq \mathcal{T}$ such that no two transitions act on
the same variable, $\forall i \in \{1, \dots, n\}, t \ne t' \in T_i \implies \{t, t'\} \not\subseteq S$, and every variable
with transient value in $\hat{z}$ is represented, $\forall i \in \{1, \dots, n\}, \hat{z}_i \in \{\uparrow, \downarrow\} \Longleftrightarrow T_i \cap
S \ne \emptyset$. Moreover, every transition in $S$ is 0.5 enabled in $\langle \hat{z} \rangle, \forall t \in S, \text{enab}(t, \langle \hat{z} \rangle) =
0.5$. Let thus $\sigma = (0.5t)_{t \in S}$ be a sequence of all such transitions firing in arbitrary
order. If $\sigma$ were a valid firing sequence, we would immediately get $\langle \hat{z} \rangle \xrightarrow{\sigma} \langle y \rangle$,
however, 0.5-firing a transition in $S$ might completely disable other transitions,
as it empties a place. Consider thus $\frac{\sigma}{2}$. After 0.25-firing any transition, each
place is guaranteed to remain at least 0.25 marked, thus guaranteeing that all
other transitions are at least 0.25 enabled. $\frac{\sigma}{2}$ is therefore a firing sequence. We
can repeat this reasoning to construct a discounted firing sequence which reaches
$\langle y \rangle$ in the limit, $\langle \hat{z} \rangle \xrightarrow{(2^{-n}\sigma)_{n \in \mathbb{N}}} \langle y \rangle$, concluding this proof direction.

The proof of the opposite direction, that any discrete marking reachable
by the CPN corresponds to a Boolean configuration reachable by the MPBN, is
similarly split into phases of the constructed MPBN trace. First, an MPBN trace
switching all relevant variables to transient values is constructed according to an
order extracted from the CPN witness. Second, we show that all those variables
in transient values whose direction disagrees with the desired target value can
be flipped. And finally, the third phase in which variables collapse to Boolean
values, is for free, as variables may collapse unconstrained in the MPBN.

*Proof (the CPN does not allow any more behaviours than the MPBN (“<=>” direction of Theorem 1)).* Let $\langle \mathbf{x} \rangle \xrightarrow{\sigma} \langle \mathbf{y} \rangle$ be an (infinite) firing sequence
witnessing the reachability of $\langle \mathbf{y} \rangle$ from $\langle \mathbf{x} \rangle$. We can without loss of generality assume $\sigma$ includes no null firings. We define a set of variables

$$I \triangleq \Delta(\mathbf{x}, \mathbf{y}) \cup \{i \in \{1, \dots, n\} \mid \exists \langle \mathbf{x} \rangle \xrightarrow{\sigma_1} \mathbf{m} \xrightarrow{\sigma_2} \langle \mathbf{y} \rangle, \sigma_1 \sigma_2 = \sigma \wedge \mathbf{m}_i \notin \mathbb{B}\}$$

as the variables whose value (marking of the corresponding places) changes at some point along $\sigma$. We further impose a total order on $I$ according to the associated places of which variable have their value modified first, resulting in the vector $\vec{I} = (j_0, \dots, j_k)$. The order is total as every transition modifies only two places $i, i+n$, which are associated to the same variable $i \in \{1, \dots, n\}$.

We now show that the MPBN $f$ can reach a configuration $\hat{\mathbf{z}}$ such that for every $i \in I$, $\hat{\mathbf{z}}_i \in \{\uparrow, \downarrow\}$. We conduct the proof by induction on $k$.

In the base case, we have to show $\mathbf{x} \xrightarrow{\hat{m}_p} \hat{\mathbf{w}}$ where $\hat{\mathbf{w}}_{j_0} \in \{\uparrow, \downarrow\}$ and $\forall i \neq j_0$, $\hat{\mathbf{w}}_i \in \mathbb{B}$. This follows directly from Lemma 2, as $\langle \mathbf{x} \rangle \in \mu(\mathbf{x})$.

Let now $h < k$ be such that $\mathbf{x} \xrightarrow{\hat{m}_p}^* \hat{\mathbf{w}}$ and $\forall i \in \{1, \dots, n\}$, $\hat{\mathbf{x}}_i \in \mathbb{B} \iff i \notin \{j_0, \dots, j_h\}$. Let then $\langle \mathbf{x} \rangle \xrightarrow{\sigma_1} \mathbf{m} \xrightarrow{\alpha t} \mathbf{m}' \xrightarrow{\sigma_2} \langle \mathbf{y} \rangle$ be such that $\sigma_1(\alpha t)\sigma_2 = \sigma$, $[[\sigma_1]] \subseteq \bigcup_{i=0}^h T_i$ and $t \in T_{h+1}$. Such markings and transition have to exist as per definition of $\vec{I}$.

Let further $\hat{\mathbf{v}} \in \{0, 1, \uparrow, \downarrow\}^n$ be arbitrary such that $\mathbf{m} \in \mu(\hat{\mathbf{v}})$. We know such a configuration exists as the P-invariants of $N(f)$ guarantee that $\mathbf{m}_i + \mathbf{m}_{i+n} = 1$ is preserved for any variable $i \in \{1, \dots, n\}$. By Lemma 1, we thus immediately have $\mathrm{enab}(t, \langle \hat{\mathbf{v}} \rangle) \ge 0.5$. $[[\sigma_1]] \subseteq \bigcup_{i=0}^h T_i$ guarantees that for any variable $i \in \{1, \dots, n\}$, $\hat{\mathbf{w}}_i \in \mathbb{B} \implies \hat{\mathbf{v}}_i = \hat{\mathbf{w}}_i$, as all such variables are untouched since the initial configuration, allowing us to apply Lemma 3 to obtain $\mathrm{enab}(t, \langle \hat{\mathbf{w}} \rangle) \ge 0.5$. Finally, by Lemma 2 we get $\hat{\mathbf{w}} \xrightarrow{\hat{m}_p} \hat{\mathbf{w}}'$ with $\hat{\mathbf{w}}'_{j_{h+1}} \in \{\uparrow, \downarrow\}$.

We thus have $\mathbf{x} \xrightarrow{\hat{m}_p}^* \hat{\mathbf{z}}$ such that $\hat{\mathbf{z}}_i \in \{\uparrow, \downarrow\} \iff i \in I$. Additionally, since $\Delta(\mathbf{x}, \mathbf{y}) \subseteq I$, we also know $\hat{\mathbf{z}}_i \in \mathbb{B} \iff \hat{\mathbf{z}}_i = \mathbf{y}_i$. Let us now consider the variables $i \in \{1, \dots, n\}$ such that $\hat{\mathbf{z}}_i = \downarrow$ and $\mathbf{y}_i = 1$, respectively $\hat{\mathbf{z}}_i = \uparrow$ and $\mathbf{y}_i = 0$. As the two cases are symmetrical, we assume $\mathbf{y}_i = 1$ without loss of generality.

Since $i \in I$ we know that there exists $\langle \mathbf{x} \rangle \xrightarrow{\sigma_1} \mathbf{m} \xrightarrow{\alpha t} \mathbf{m}' \xrightarrow{\sigma_2} \langle \mathbf{y} \rangle$ such that $\sigma_1(\alpha t)\sigma_2 = \sigma$ and $\mathbf{m}_i > \mathbf{m}'_i$. We apply the same reasoning as in the above induction step. Let thus $\hat{\mathbf{v}} \in \{0, 1, \uparrow, \downarrow\}^n$ be arbitrary such that $\mathbf{m} \in \mu(\hat{\mathbf{v}})$. By Lemma 1, $\mathrm{enab}(t, \langle \hat{\mathbf{v}} \rangle) \ge 0.5$. $\forall i \in I$, $\hat{\mathbf{z}}_i \in \{\uparrow, \downarrow\}$ gives us for any $j \in \{1, \dots, n\}$, $\hat{\mathbf{z}}_j \in \mathbb{B} \implies \hat{\mathbf{z}}_j = \hat{\mathbf{v}}_j$, allowing us to apply Lemma 3 to get $\mathrm{enab}(t, \langle \hat{\mathbf{z}} \rangle) \ge 0.5$. And finally, by Lemma 2, $\hat{\mathbf{z}} \xrightarrow{\hat{m}_p} \hat{\mathbf{w}}$ where $\hat{\mathbf{w}}_i = \uparrow$.

Since $\langle \hat{\mathbf{z}} \rangle = \langle \hat{\mathbf{w}} \rangle$, we can repeat the above for every such variable until we reach $\hat{\mathbf{z}}'$ such that for each variable $i \in \{1, \dots, n\}$, either $\hat{\mathbf{z}}'_i \in \mathbb{B}$ and $\hat{\mathbf{z}}'_i = \mathbf{y}_i$ or $\hat{\mathbf{z}}'_i \in \{\uparrow, \downarrow\}$ and $\hat{\mathbf{z}}'_i = \uparrow \iff \mathbf{y}_i = 1$. It remains to collapse all variables into the corresponding Boolean values, yielding $\mathbf{x} \xrightarrow{\hat{m}_p}^* \hat{\mathbf{z}} \xrightarrow{\hat{m}_p}^* \hat{\mathbf{z}}' \xrightarrow{\hat{m}_p}^* \mathbf{y}$.

By Theorem 1, the net from Figure 6 instantiated as a CPN with the initial marking $\mathbf{m}_0 = (1, 1, 1, 0, 0, 0) = \langle (0, 0, 0) \rangle$ recovers exactly the reachability graph
given in Figure 3. To see this, we omit the ARG due to scale (the graph has 27 vertices) and instead show an excerpt of the SRT in Figure 7.

<figure><img src="image_8.png" /><figcaption>**Fig. 7.** An excerpt of the SRT for the CPN encoding of the example BN (Fig. 6). The remaining 14 branches, each isomorphic to one of the listed branches w.r.t. vertex labels but with smaller supports, have been pruned for readability.</figcaption></figure>

The SRT is a symbolic representation of the reachable configurations in Figure 3. All configurations $\mathbf{x} \in \mathbb{B}^3$ such that $\mathbf{x}_1 = \mathbf{x}_2$ can update to any other configuration and their associated markings, $\langle \mathbf{x} \rangle$, belong to the root of the SRT.

The leaves of the SRT are the fixed points of the MPBN. The same fixed point appears in multiple leaves due to different ways the system can reach it. The two arrows in the middle reach the attractors directly, in case the variable 3 already has the “correct” value. The branches on the far left and far right then cross over an intermediate vertex. On the left, this vertex represents the configuration (1, 0, 1) and on the right (0, 1, 0).

As seen in Figure 3, the configurations (1, 0, 1) and (0, 1, 0) constitute the strong basins of attraction of the respective fixed points. The SRT thus captures not only the attractors themselves, but also the system “deciding” on the long-term behaviour by leaving the weak basin of attraction of some attractor.

# 4 Conclusion and Outlook

We have demonstrated that the PN encoding of BNs, previously introduced to simulate fully asynchronous semantics as a DPN, can equally be used to simulate MP semantics as a CPN. Finite CPN reachability is not enough to capture simultaneous variable updates; lim-reachability is required to reproduce all behaviours exhibited by the MPBN. The encoding allows MPBNs to benefit from all results available for CPNs. Similarly to MPBNs, CPN reachability is polynomial. Further, we have exhibited that tools for symbolic analysis of CPNs recapitulate the reachable configurations of MPBNs, with special focus on “key events” which shape the attractor landscape.

We believe that the above results serve both to open up new avenues for studying and understanding MPBNs, and motivate further study of the “abstraction scale” of dynamical models of interaction. In particular, the passage to real-time models is well-studied for CPNs, see [9]. Future work may include the study of the semantic link between CPNs and Chemical Reaction Networks [13], on which no results exist so far, to the best of our knowledge.
References

1. Petri nets: Properties, analysis and applications. Proc. of the IEEE, 77(4):541-580, 1989. URL: http://dx.doi.org/10.1109/5.24143.

2. Michael Blondin, Alain Finkel, Christoph Haase, and Serge Haddad. The logical view on continuous Petri nets. *ACM Transactions on Computational Logic*, 18(3):24:1–24:28, 2017.

3. Roberto Bruni, Roberta Gori, Paolo Milazzo, and Hélène Siboulet. Melding boolean networks and reaction systems under synchronous, asynchronous and most permissive semantics. *Nat. Comput.*, 23:235–267, 2024. URL: https://api.semanticscholar.org/CorpusID:271287338.

4. C. Chaouiya, A. Naldi, E. Remy, and D. Thieffry. Petri net representation of multi-valued logical regulatory graphs. *Natural Computing*, 10(2):727–750, 2011. doi:10.1007/s11047-010-9178-0.

5. Claudine Chaouiya, Elisabeth Remy, and Denis Thieffry. Qualitative petri net modelling of genetic networks. In Corrado Priami and Gordon Plotkin, editors, *Transactions on Computational Systems Biology VI*, pages 95–112, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. doi:10.1007/11880646_5.

6. Thomas Chatain, Stefan Haar, Loïg Jezequel, Loïc Paulevé, and Stefan Schwoon. Characterization of reachable attractors using Petri net unfoldings. *Computational Methods in Systems Biology*, 8859:129–142, 2014.

7. Thomas Chatain, Stefan Haar, Juri Kolčák, Loïc Paulevé, and Aalok Thakkar. Concurrency in boolean networks. *Natural Computing*, 19:91–109, 2020.

8. Thomas Chatain, Stefan Haar, and Loïc Paulevé. Boolean Networks: Beyond Generalized Asynchronicity. In *AUTOMATA'18*, volume 10875 of LNCS, pages 29–42, Ghent, Belgium, June 2018.

9. René David and Hassane Alla. *Discrete, Continuous, and Hybrid Petri Nets*, volume 28. Springer, 2008. doi:10.1109/MCS.2008.920445.

10. Hidde de Jong. Modeling and simulation of genetic regulatory systems: A literature review. *Journal of Computational Biology*, 9(1):67–103, 2002. doi:10.1089/10665270252833208.

11. J. Desel and J. Esparza. *Free Choice Petri Nets*. Cambridge University Press, 1995.

12. A. Faure, A. Naldi, C. Chaouiya, and D. Thieffry. Dynamical analysis of a generic Boolean model for the control of the mammalian cell cycle. *Bioinformatics*, 22(14):124–131, 2006. doi:10.1093/bioinformatics/btl210.

13. M. Feinberg. *Foundations of Chemical Reaction Network Theory*. Applied Mathematical Sciences. Springer International Publishing, 2019. URL: https://books.google.fr/books?id=IBOGDwAAQBAJ.

14. Estíbaliz Fraca and Serge Haddad. Complexity analysis of continuous Petri nets. *Fundamenta Informaticae*, 137(1):1–28, 2015.

15. Stefan Haar and Serge Haddad. On the expressive power of transfinite sequences for continuous petri nets. In Lars Michael Kristensen and Jan Martijn E. M. van der Werf, editors, *Application and Theory of Petri Nets and Concurrency - 45th International Conference, PETRI NETS 2024, Geneva, Switzerland, June 26-28, 2024, Proceedings*, volume 14628 of Lecture Notes in Computer Science, pages 109–131. Springer, 2024. doi:10.1007/978-3-031-61433-0_6.

16. Jorge Júlvez, Laura Recalde, and Manuel Silva. On reachability in autonomous continuous Petri net systems. In *ICATPN 2003*, volume 2679 of LNCS, pages 221–240, 2003.
17. S. Mangan and U. Alon. Structure and function of the feed-forward loop network motif. *Proceedings of the National Academy of Sciences*, 100(21):11980-11985, 2003. doi:10.1073/pnas.2133841100.

18. Pablo Martínez-Sosa and Luis Mendoza. The regulatory network that controls the differentiation of t lymphocytes. *Biosystems*, 113(2):96 – 103, 2013. doi:https://doi.org/10.1016/j.biosystems.2013.05.007.

19. Loïc Paulevé, Juri Kolčák, Thomas Chatain, and Stefan Haar. Reconciling qualitative, abstract, and scalable modeling of biological networks. *Nature Communications*, 11(4256), August 2020.

20. Loïc Paulevé and Sylvain Sené. Non-Deterministic Updates of Boolean Networks. In Alonso Castillo-Ramirez, Pierre Guillon, and Kévin Perrot, editors, *27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)*, volume 90 of *Open Access Series in Informatics (OASICS)*, pages 10:1–10:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/OASICS.AUTOMATA.2021.10.

21. Laura Recalde, Serge Haddad, and Manuel Silva Suárez. Continuous petri nets: Expressive power and decidability issues. *Int. J. Found. Comput. Sci.*, 21(2):235–256, 2010. doi:10.1142/S0129054110007222.

22. Laura Recalde, Enrique Teruel, and Manuel Silva. Autonomous continuous p/t systems. In Susanna Donatelli and Jetty Kleijn, editors, *Application and Theory of Petri Nets 1999*, pages 107–126, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. doi:10.1007/3-540-48745-X_8.

23. Carlos Renato Vázquez and Manuel Silva Suárez. Timing and liveness in continuous petri nets. *Autom.*, 47(2):283–290, 2011. URL: https://doi.org/10.1016/j.automatica.2010.10.047, doi:10.1016/J.AUTOMATICA.2010.10.047.

24. Rui-Sheng Wang, Assieh Saadatpour, and Réka Albert. Boolean modeling in systems biology: an overview of methodology and applications. *Physical Biology*, 9(5):055001, sep 2012. doi:10.1088/1478-3975/9/5/055001.