Polynomial Equivalence of Extended Chemical Reaction Models

Bajaj, Divya; Castellanos, Jose-Luis; Knobel, Ryan; Luchsinger, Austin; Massie, Aiden; Salinas, Adrian; Santos, Pablo; Santos, Ramiro; Schweller, Robert; Wylie, Tim

doi:10.4230/LIPIcs.ISAAC.2025.7

Polynomial Equivalence of Extended Chemical Reaction Models

Divya Bajaj University of Texas Rio Grande Valley, Edinburg, TX, USA Jose-Luis Castellanos University of Texas Rio Grande Valley, Edinburg, TX, USA Ryan Knobel University of Texas Rio Grande Valley, Edinburg, TX, USA Austin Luchsinger University of Texas Rio Grande Valley, Edinburg, TX, USA Aiden Massie University of Texas Rio Grande Valley, Edinburg, TX, USA Adrian Salinas University of Texas Rio Grande Valley, Edinburg, TX, USA Pablo Santos University of Texas Rio Grande Valley, Edinburg, TX, USA Ramiro Santos University of Texas Rio Grande Valley, Edinburg, TX, USA Robert Schweller University of Texas Rio Grande Valley, Edinburg, TX, USA Tim Wylie University of Texas Rio Grande Valley, Edinburg, TX, USA

Abstract

The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models – making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species’ count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero.

Keywords and phrases:

Chemical Reaction Networks, Simulations, Petri-nets, Vector Addition Systems, Bi-simulation, Turing-universality, Inhibitors

Copyright and License:

© Divya Bajaj, Jose-Luis Castellanos, Ryan Knobel, Austin Luchsinger, Aiden Massie, Adrian Salinas, Pablo Santos, Ramiro Santos, Robert Schweller, and Tim Wylie; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Models of computation

Funding:

This research was supported in part by National Science Foundation Grant CCF-2329918.

DOI:

10.4230/LIPIcs.ISAAC.2025.7

Event:

36th International Symposium on Algorithms and Computation (ISAAC 2025)

Editors:

Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Background.

Chemical Reaction Networks [5], Vector Addition Systems [18], and Petri nets [23] are three formalisms that arose in different disciplines to study distributed/concurrent systems. Despite their distinct origins, these models are mathematically equivalent in expressive power [8, 15]. While these models are capable of very complex behavior – e.g., deciding if one configuration is reachable from another via a sequence of transitions was recently shown to be Ackermann-complete [9, 19] – they fall short of Turing-universality.

Even though these base models are not capable of universal computation, they are each right on the cusp of doing so. It is well known that extending the models in any way that allows “checking for zero” immediately results in Turing-universality [1, 16, 22]. This has been shown for model extensions allowing transition inhibition [1, 7, 11, 16], transition prioritization [16, 24, 25], synchronous (parallel) transitions [6, 28], or even continual volume increase [2, 3]. These results are typically established by showing how each extended model can simulate a register (counter) machine [22].

However, Turing equivalence alone is a blunt instrument. It tells us that models can emulate one another, but not how efficiently this can be done. We often care not just that two models are Turing-complete, but if they can be easily transformed into one another. For instance, Hack gave one such transformation between Inhibitory and Priority Petri nets [16], but discussed their equivalence in terms of languages. For this paper, we focus on the concept of simulation to draw comparisons between models.

In the literature, several notions of simulation have been proposed to capture structural or behavioral equivalence between systems. While concepts like strong/weak bisimulation [4, 10, 12, 17, 21] and pathway decomposition [26, 27] have been used to compare the expressiveness of different systems, there is typically a tradeoff between reasonably preserving dynamics and maintaining structural correspondence. Furthermore, efficiency of simulation is often either implicitly included or sometimes omitted altogether. Part of our work aims to introduce a more wieldy definition of simulation that explicitly accounts for efficiency. We give a more detailed discussion on simulation later in the paper.

Our Contributions.

In this work, we make two main contributions:

1.

We define a general-purpose notion of polynomial efficient simulation that is intended to capture a broader notion of simulation while still remaining reasonable. Our definition ensures that the simulation respects a polynomial correspondence in both time (dynamics) and space (structure). This allows us to formally compare the simulation efficiency of different CRN variants.
2.

We introduce a new model, which we call Void Genesis (VG), that makes zero-testing explicit: it creates a designated species whenever a tracked species reaches zero. We use this model as a unifying model that captures the essence of zero-testing in a clean and modular way. We show that the Void Genesis model is polynomially equivalent to other known Turing-universal extensions of CRNs.

Since all of these extended models can be simulated by VG (and vice versa) with only polynomial overhead, our results establish a hub of polynomial simulation equivalence among them. This yields a stronger and more precise understanding of the relationships between these CRN variants and highlights VG simulation as a useful proof technique for adding models to this hub. Figure 1 summarizes the simulation relationships we establish here.

Organization.

Given the number of models and results, we have arranged the paper in a way that systematically builds up understanding and techniques. Section 2 covers the formal definitions of the models and a simulation of one model with another. Section 3 provides minimum working examples in the models. The polynomial equivalence between models is proven through a series of simulations in Section 4. In Section 5, we discuss our results and some open problems.

Figure 1: CRN Model variants and their connections to Void Genesis CRNs. Theorems 1-5 each show a polynomial equivalence between two CRN variants. With the Void Genesis model as a central hub, the implication of these results is a polynomial equivalence between all models.

2 Preliminaries

In Section 2.1, we define the extended chemical reaction network models considered in this paper with examples, and in Section 2.2 we define the concept of inter-model simulation.

2.1 Models

Here, we define the six chemical reaction networks considered in this paper: the basic chemical reaction network model (Section 2.1.1), the Void Genesis model (Section 2.1.2), the Inhibitory CRN model (Section 2.1.3), the Coarse-Rate CRN model (Section 2.1.4), the Step-Cycle CRN model (Section 2.1.5), and the Unique Instruction Parallel model (Section 2.1.6).

2.1.1 Chemical Reaction Networks

A chemical reaction network (CRN) $\mathcal{C}=(\Lambda,\Gamma)$ is defined by a finite set of species $\Lambda$ , and a finite set of reactions $\Gamma$ where each reaction is a pair $(\overrightarrow{R},\overrightarrow{P})\in\mathbb{N}^{\Lambda}\times\mathbb{N}% ^{\Lambda}$ , sometimes written $\overrightarrow{R}\mathop{\longrightarrow}\limits\overrightarrow{P}$ , that denotes the reactant species consumed by the reaction and the product species generated by the reaction. For example, given $\Lambda=\{a,b,c\}$ , the reaction $((2,0,0),(0,1,1))$ represents $2a\mathop{\longrightarrow}\limits b+c$ ; 2 $a$ species are removed, and 1 new $b$ and $c$ species are created.

A configuration $\overrightarrow{C}\in\mathbb{N}^{\Lambda}$ of a CRN assigns integer counts to every species $\lambda\in\Lambda$ , and we use notation $\overrightarrow{C}\,[\lambda]$ to denote that count. For a species $\lambda\in\Lambda$ , we denote the configuration consisting of a single copy of $\lambda$ and no other species as $\vec{\lambda}$ . It is often useful to reference the set of species whose counts are not zero in a given configuration. In such cases, the notation $\{\overrightarrow{C}\}$ is used. Formally, $\{\overrightarrow{C}\}=\{\lambda\in\Lambda\mid\overrightarrow{C}[\lambda]>0\}$ , and when convenient and clear from the context, we further use $\{\overrightarrow{C}\}$ to denote the configuration (vector) representation in which each element has a single copy. Finally, let $|\overrightarrow{C}|=\sum_{\lambda\in\Lambda}C[\lambda]$ denote the total number of copies of all species in a configuration, sometimes referred to as the volume of $\overrightarrow{C}$ .

A reaction $(\overrightarrow{R},\overrightarrow{P})$ is said to be applicable in configuration $\overrightarrow{C}$ if $\overrightarrow{R}\leq\overrightarrow{C}$ ; in other words, a reaction is applicable if $\overrightarrow{C}$ has at least as many copies of each species as $\overrightarrow{R}$ . If the reaction $(\overrightarrow{R},\overrightarrow{P})$ is applicable, it results in configuration $\overrightarrow{C^{\prime}}=\overrightarrow{C}-\overrightarrow{R}+% \overrightarrow{P}$ if it occurs, and we write $\overrightarrow{C}\rightarrow_{crn}^{(\Lambda,\Gamma)}\overrightarrow{C^{% \prime}}$ , or simply $\overrightarrow{C}\mathop{\rightarrow}\limits\overrightarrow{C^{\prime}}$ when the model and CRN are clear from context. We use the same notation as configuration vectors to denote the size ( $\lvert\overrightarrow{R}\rvert$ and $\lvert\overrightarrow{P}\rvert$ ) and explicit content ( $\{\overrightarrow{R}\}$ and $\{\overrightarrow{P}\}$ ) of reactants and products for a reaction.

Definition 1 (Discrete Chemical Reaction Network).

A discrete chemical reaction network (CRN) is an ordered pair $(\Lambda,\Gamma)$ where $\Lambda$ is an ordered alphabet of species, and $\Gamma$ is a set of rules over $\Lambda$ .

Definition 2 (Basic CRN Dynamics).

For a CRN $(\Lambda,\Gamma)$ and configurations $\overrightarrow{A}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{crn}^{(\Lambda,\Gamma)}\overrightarrow{B}$ if there exists a rule $(\overrightarrow{R},\overrightarrow{P})\in\Gamma$ such that $\overrightarrow{R}\leq\overrightarrow{A}$ , and $\overrightarrow{A}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B}$ .

If there exists a finite sequence of configurations such that $\overrightarrow{C}\mathop{\rightarrow}\limits\overrightarrow{C}_{1}\mathop{% \rightarrow}\limits\dots\mathop{\rightarrow}\limits\overrightarrow{C}_{n}% \mathop{\rightarrow}\limits\overrightarrow{D}$ , then we say that $\overrightarrow{D}$ is reachable from $\overrightarrow{C}$ and we write $\overrightarrow{C}\mathop{\leadsto}\limits\overrightarrow{D}$ . A configuration is said to be terminal if no reactions are applicable. We also define an initial configuration for a CRN as its starting configuration. A CRN System $T$ is then defined as a pair of a CRN model and its initial configuration. The following sections define extensions of the basic CRN model by way of defining modified dynamics.

2.1.2 Void Genesis CRNs

A Void Genesis CRN $\mathcal{C_{VG}}=((\Lambda,\Gamma),z)$ is a basic CRN with a zero species $z\in\Lambda$ whose count is incremented whenever the count of any species other than $z$ goes to zero. See Figure 2(d) for an example.

Definition 3 (Void-Genesis Dynamics).

For a Void-Genesis CRN $((\Lambda,\Gamma),z\in\Lambda)$ and configurations $\overrightarrow{A}$ , $\overrightarrow{B_{t}}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{\mathcal{C_{VG}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}$ if there exists a rule $(\overrightarrow{R},\overrightarrow{P})\in\Gamma$ such that $\overrightarrow{R}\leq\overrightarrow{A}$ , $\overrightarrow{A}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B_{t}}$ , and $\overrightarrow{B}=\overrightarrow{B_{t}}+n\cdot\vec{z}$ where n is the cardinality of { $\lambda\in\Lambda\setminus\{z\}$ $|$ $\overrightarrow{A}[\lambda]\not=0$ and $\overrightarrow{B_{t}}[\lambda]=0$ }.

It is straightforward to show that the Void Genesis model is Turing-universal via simulating a register machine, and we do so in Section 4.7.

2.1.3 Inhibitory CRNs

A reaction $\mathcal{\gamma}$ is said to be inhibited by a species $\lambda$ when the reaction $\mathcal{\gamma}$ may only be applied if $\lambda$ is absent in the system. We define an inhibitor mapping $\mathcal{I}:\Gamma\rightarrow\mathbb{P}(\Lambda)$ that maps a reaction to a subset of species that inhibit the reaction. An Inhibitory CRN $\mathcal{C_{IC}}=((\Lambda,\Gamma),\mathcal{I})$ as defined by [7] is then a basic CRN along with the mapping $\mathcal{I}$ . See Figure 2(c) for an example.

Definition 4 (Inhibitory Dynamics).

For a Inhibitory CRN $((\Lambda,\Gamma),\mathcal{I})$ and configurations $\overrightarrow{A}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{\mathcal{C_{IC}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}$ if there exists a rule $\mathcal{\gamma}=(\overrightarrow{R},\overrightarrow{P})\in\Gamma$ such that $\overrightarrow{R}\leq\overrightarrow{A}$ , $\overrightarrow{A}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B}$ , and $A[\lambda]=0,\forall\lambda\in\mathcal{I}(\mathcal{\gamma})$ .

2.1.4 Coarse-Rate CRNs

A Coarse-Rate CRN $\mathcal{C}_{CR}=((\Lambda,\Gamma),rank)$ as introduced by [25] is a basic CRN along with a function $rank:\Gamma\rightarrow\mathbb{N}$ . We define a set of reactions $\Gamma^{l}$ as the set of all reactions $\mathcal{\gamma}$ where $rank(\mathcal{\gamma})=l$ . The set of reactions $\Gamma$ is then defined as an ordered partition set given by $\{\Gamma^{1},\Gamma^{2},\ldots,\Gamma^{n}\}$ . Any applicable reaction $\mathcal{\gamma}_{i}^{\ell}$ may only be applied if no reaction $\mathcal{\gamma}_{j}^{k}\in\Gamma^{k},\forall k\in[\ell+1,n]$ is applicable. We use $(\overrightarrow{R},\overrightarrow{P})^{\ell}$ to denote a reaction $\mathcal{\gamma}^{\ell}\in\Gamma^{\ell}$ . In the context of this paper we focus on models with rank at most $2$ . For clarity, we will refer to reactions with rank $2$ as fast reactions, and the ones with rank $1$ as slow reactions. See Figure 2(b) for an example.

Definition 5 (Coarse-Rate Dynamics).

For a Coarse-Rate CRN $((\Lambda,\Gamma),rank)$ and configurations $\overrightarrow{A}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{\mathcal{C_{CR}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}$ if there exists a rule $(\overrightarrow{R},\overrightarrow{P})^{\ell}\in\Gamma$ such that $\overrightarrow{R}\leq\overrightarrow{A}$ , $\overrightarrow{A}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B}$ , and $\not\exists$ an applicable reaction $\mathcal{\gamma}^{k>\ell}$ .

2.1.5 Step-Cycle CRNs

A step-cycle CRN is a step CRN [2] that infinitely repeats steps 0 through $k-1$ : that is, once $\overrightarrow{S}_{k-1}$ is added to the terminal configuration in the ${(k-1)}^{th}$ step, the resulting configuration is treated as the new initial configuration for the step CRN. More formally, a step-cycle CRN of $k$ steps is an ordered pair $((\Lambda,\Gamma),(\overrightarrow{S}_{0},\overrightarrow{S}_{1},\ldots,% \overrightarrow{S}_{k-1}))$ , where the first element is a normal CRN $(\Lambda,\Gamma)$ and the second is a sequence of length- $|\Lambda|$ vectors of non-negative integers denoting how many copies of each species type to add after each step. We define a step-configuration $\overrightarrow{C}_{i}$ for a step-cycle CRN as a valid configuration $\overrightarrow{C}$ over $(\Lambda,\Gamma)$ along with an integer $i\in\{0,\ldots,k-1\}$ that denotes the configuration’s step.

Definition 6 (Step-Cycle Dynamics).

For a step-cycle CRN $((\Lambda,\Gamma),(\overrightarrow{S}_{0},\overrightarrow{S}_{1},\ldots,% \overrightarrow{S}_{k-1}))$ and step-configurations $\overrightarrow{A}_{i}$ and $\overrightarrow{B}_{j}$ , we say that $\overrightarrow{A}_{i}\rightarrow_{\mathcal{C_{SC}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}_{j}$ if either

1.

$i=j$ , there exists a rule $(\overrightarrow{R},\overrightarrow{P})\in\Gamma$ s.t. $\overrightarrow{R}\leq\overrightarrow{A}_{i}$ , and $\overrightarrow{A}_{i}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B% }_{j}$ , or
2.

$(i+1)\mod k=j$ , $\overrightarrow{A}_{i}$ is terminal, and $\overrightarrow{A}_{i}+\overrightarrow{S}_{i}=\overrightarrow{B}_{j}$ .

2.1.6 Unique Instruction Parallel CRNs

The Unique Instruction Parallel model modifies the dynamics of a normal CRN $(\Lambda,\Gamma)$ by applying a maximal set of compatible rules as a single transition. In this paper, we restrict this maximal set to contain only one application of any given rule, leaving the study of more relaxed parallel models for future work.

Definition 7 (Plausibly Parallel Rules).

A multiset of $n$ (not necessarily distinct) rules $\{(\overrightarrow{R}_{1},\overrightarrow{P}_{1}),\ldots,(\overrightarrow{R}_{% n},\overrightarrow{P}_{n})\}$ are plausibly parallel for a configuration $\overrightarrow{C}$ over $\Lambda$ if the vector $\overrightarrow{R}=\sum_{i=1}^{n}\overrightarrow{R}_{i}$ is such that $\overrightarrow{R}\leq\overrightarrow{C}$ .

Definition 8 (Unique-Instruction Plausibly Parallel).

A plausibly parallel multiset is said to be Unique-Instruction if it contains at most one copy of any given rule (i.e., it is a set). It is considered unique-instruction maximal if it is not a proper subset of any other unique-instruction plausibly parallel set.

Definition 9 (Unique-Instruction Parallel Dynamics).

For a CRN $(\Lambda,\Gamma)$ and configurations $\overrightarrow{A}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{\mathcal{C_{UI}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}$ if there exists a unique-instruction maximal plausibly parallel set $\{(\overrightarrow{R}_{1},\overrightarrow{P}_{1}),\ldots,(\overrightarrow{R}_{% k},\overrightarrow{P}_{k})\}$ for configuration $\overrightarrow{A}$ and rule set $\Gamma$ such that $\overrightarrow{B}=\overrightarrow{A}-\sum_{i=1}^{k}\overrightarrow{R}_{i}+% \sum_{i=1}^{k}\overrightarrow{P}_{i}$ .

(a) Step-Cycle Example.

(b) Coarse-Rate Example.

(c) iCRN Example.

(d) Void Genesis Example.

(e) Unique Instruction Parallel Example.

Figure 2: Example systems for the 5 CRN models. The blurred portions of the figure represent invalid reaction sequences. (a) Step-cycle with

2

steps. Species are added when configurations reach a terminal state. (b) Coarse-rate. The numbers next to each reaction denote the rank. The bottom reaction sequence is invalid as the reaction with rank

2

must occur first. (c) Inhibitory. The top reaction sequence is invalid as there exists a

b

in the initial configuration, which is an inhibitor for the rule

a\rightarrow\emptyset

. (d) Void Genesis. Once the

a

species reaches a count of 0, the

z

species is created. In the bottom reaction sequence, the

z

species reacts with the

b

species, and another

z

species is created. (e) Unique-Instruction Parallel. The bottom reaction sequence is invalid as the rule

a+b\rightarrow\emptyset

is not a maximal set.

2.2 Simulation

By way of Petri nets, discrete CRNs have seen various model extensions. To meaningfully compare the computational capabilities of these variants, we turn to the notion of simulation, which serves as a tool to compare the relative expressive power of each model. However, existing definitions in the literature vary in scope and applicability. Some emphasize strict structural correspondence while others focus purely on dynamic behavior. Thus, it is worthwhile to discuss why we formulate our own definition of simulation and equivalence.

Borrowed from classical process theory, (strong) bisimulation [21, 12, 4] is perhaps the most stringent form of equivalence. It requires that for every state and transition in one system, there exists a matching state and transition in the other, and vice versa. This strong bidirectional constraint means bisimulation ensures both behavioral and structural fidelity, and notably also implicitly guarantees efficiency.

Weak bisimulation [10, 17], on the other hand, relaxes the strict step-by-step matching of bisimulation. Instead, a transition in one system may correspond to a macrotransition in the other: a sequence of transitions possibly allowing “hidden” or “silent” intermediate steps. This makes bisimulation more flexible and applicable to realistic implementations, but it is not without its own limitations. Pathway decomposition, as presented in [26, 27], takes a different approach. Rather than comparing reactions directly, they identify a CRN’s formal basis – a set of “indivisible” formal pathways that collectively define its behavior. This allows pathway decomposition to capture phenomena such as delayed choice, in which nondeterministic behavior is distributed across multiple steps.

Our framework seeks to strike a middle ground. We define simulation in terms of a configuration map and macrotransitions, retaining the core idea of weak bisimulation but allowing for a more general structural correspondence between systems. Since this correspondence is so general, we explicitly include a measure of efficiency with our definition. We define polynomial efficient simulation that permits abstraction and internal nondeterminism, like weak bisimulation and pathway decomposition, but captures both dynamic behavior and bounded structural transformation. We say two systems are polynomially equivalent if they can each simulate each other via our definition. This is analogous to bisimilarity [21], but in the context of efficient, weak simulation.

Simulation Definition.

To define the concept of one CRN system $T^{\prime}$ simulating another CRN system $T$ we introduce configuration maps and representative configurations. A configuration map is a polynomial-time computable function $M:\textrm{configs}_{T^{\prime}}\rightarrow\textrm{configs}_{T}\bigcup\{\bot\}$ mapping at least one element in $\textrm{configs}_{T^{\prime}}$ to each element in $\textrm{configs}_{T}$ , and the representative configurations for a configuration $\overrightarrow{C}\in\textrm{configs}_{T}$ are $[\![\overrightarrow{C}\,]\!]=\{\overrightarrow{C^{\prime}}\mid\overrightarrow{% C}=M(\overrightarrow{C^{\prime}})\}$ , also computable in polynomial time.¹¹1We write $M(\overrightarrow{C^{\prime}})=\bot$ to mean that the mapping is undefined, which is not the same as $M(\overrightarrow{C^{\prime}})=\overrightarrow{0}$ . Finally, we define the concept of single-step transition, $\overrightarrow{A}\rightarrow_{T}\overrightarrow{B}$ , to mean that $\overrightarrow{A}$ transitions to $\overrightarrow{B}$ in system $T$ . And, the concept of macro transitionable, $\overrightarrow{A^{\prime}}\Rightarrow_{T^{\prime}}\overrightarrow{B^{\prime}}$ , to mean that $\overrightarrow{B^{\prime}}$ is reachable from $\overrightarrow{A^{\prime}}$ in system $T^{\prime}$ through a sequence of $k$ intermediate configurations $\langle\overrightarrow{A^{\prime}},\overrightarrow{X_{1}^{\prime}},\ldots,% \overrightarrow{X_{k}^{\prime}},\overrightarrow{B^{\prime}}\rangle$ such that $M(\overrightarrow{A^{\prime}})\neq\bot$ , $M(\overrightarrow{B^{\prime}})\neq\bot$ , and each $M(\overrightarrow{X_{i}^{\prime}})\in\{M(\overrightarrow{A^{\prime}}),\bot\}$ . Note that $k$ can be zero, resulting in the sequence $\langle\overrightarrow{A^{\prime}},\overrightarrow{B^{\prime}}\rangle$ .

Intuition.

Each representative configuration set $[\![\overrightarrow{C}\,]\!]$ is a particular collection (of at least 1 configuration) that adheres to the strictest modeling of system $T$ within system $T^{\prime}$ . That is, any $\overrightarrow{C^{\prime}}\in[\![\overrightarrow{C}\,]\!]$ must be able to grow into anything that $\overrightarrow{C}=M(\overrightarrow{C^{\prime}})$ can grow into, and no $\overrightarrow{C^{\prime}}\in[\![\overrightarrow{C}\,]\!]$ may grow into something that $\overrightarrow{C}=M(\overrightarrow{C^{\prime}})$ cannot grow into.

For a given configuration map and collection of representative configurations, we define the concepts of following and modeling, followed by our definition of simulation.

Definition 10 (It Follows).

We say system $T$ follows system $T^{\prime}$ if whenever $\overrightarrow{A^{\prime}}\Rightarrow_{T^{\prime}}\overrightarrow{B^{\prime}}$ and $M(\overrightarrow{A^{\prime}})\neq M(\overrightarrow{B^{\prime}})$ , then $M(\overrightarrow{A^{\prime}})\rightarrow_{T}M(\overrightarrow{B^{\prime}})$ .

Definition 11 (Models).

We say system $T^{\prime}$ models system $T$ if $\overrightarrow{A}\rightarrow_{T}\overrightarrow{B}$ implies that $\forall\overrightarrow{A^{\prime}}\in[\![\overrightarrow{A}\,]\!]$ , $\exists\overrightarrow{B^{\prime}}\in[\![\overrightarrow{B}\,]\!]$ such that $\overrightarrow{A^{\prime}}\Rightarrow_{T^{\prime}}\overrightarrow{B^{\prime}}$ .

Definition 12 (Simulation).

A system $T^{\prime}$ simulates a system $T$ if there exists a polynomial time computable function $M:\textrm{configs}_{T^{\prime}}\rightarrow\textrm{configs}_{T}$ and polynomial time computable set $[\![\overrightarrow{C}\,]\!]=\{\overrightarrow{C^{\prime}}\mid M(% \overrightarrow{C^{\prime}})=\overrightarrow{C}\}$ for each $\overrightarrow{C}\in\textrm{configs}_{T}$ , such that:

1.

$T$ follows $T^{\prime}$ .
2.

$T^{\prime}$ models $T$ .

Figure 3: (Left) A system

T

with states

\overrightarrow{A}

and

\overrightarrow{B}

, and transition

\overrightarrow{A}\rightarrow_{T}\overrightarrow{B}

. (Right) A state-space diagram for system

T^{\prime}

that simulates

T

. Here, each arrow represents some transition

\overrightarrow{X}\rightarrow_{T^{\prime}}\overrightarrow{Y}

under the dynamics of

T^{\prime}

. Observe how

T

follows

T^{\prime}

and

T^{\prime}

models

T

.

Polynomial Simulation.

We say a simulation is polynomial efficient if the simulating system adheres to the following:

polynomial species and rules.: The number of species and rules is at most polynomial in the number of species and rules of the simulated system.
polynomial rule size.: The maximum rule size (number of products plus number of reactants) is polynomial in the maximum rule size of the simulated system.
polynomial transition sequences.: For all $B$ such that $A\rightarrow_{T}B$ , the expected number of transitions taken to perform a macro transition from $M(A)\Rightarrow_{T^{\prime}}M(B)$ , conditioned that $M(A)$ does macro transition to $M(B)$ , has expected number of transitions polynomial in the number of rules and species of the simulated system based on a uniform sampling of applicable rules.
polynomial volume.: Each $\overrightarrow{C^{\prime}}\in[\![\overrightarrow{C}\,]\!]$ has a volume that is polynomially bounded by the volume of $C$ , and for any macro transition $A^{\prime}\Rightarrow_{T^{\prime}}B^{\prime}$ , any intermediate configuration within this macrotransition has volume polynomially bounded in the volume of $M(A^{\prime})$ and $M(B^{\prime})$ .

Theorem 13 (Transitivity).

Given three CRN systems $T_{1},T_{2}$ and $T_{3}$ such that $T_{2}$ simulates $T_{1}$ under polynomial simulation, and $T_{3}$ simulates $T_{2}$ under polynomial simulation, then $T_{3}$ simulates $T_{1}$ under polynomial simulation.

Proof.

Given three CRN systems $T_{1}$ , $T_{2}$ and $T_{3}$ such that $T_{2}$ simulates $T_{1}$ under polynomial simulation, and $T_{3}$ simulates $T_{2}$ under polynomial simulation. Let $M_{21}:\textrm{configs}_{T_{2}}\rightarrow\textrm{configs}_{T_{1}}$ and $M_{32}:\textrm{configs}_{T_{3}}\rightarrow\textrm{configs}_{T_{2}}$ be the polynomial-time computable configuration mappings. We define a configuration mapping function $M_{31}:\textrm{configs}_{T_{3}}\rightarrow\textrm{configs}_{T_{1}}$ by composing functions $M_{21}$ and $M_{32}$ as follows.

M_{31}(\overrightarrow{C_{3}})=\begin{cases}(M_{21}\circ M_{32})(% \overrightarrow{C_{3}})&\text{if}\;M_{32}(\overrightarrow{C_{3}})\not=\bot% \wedge M_{21}(M_{32}(\overrightarrow{C_{3}}))\not=\bot\\ \bot&\text{otherwise}\end{cases}

And the set of representative configurations for a configuration $\overrightarrow{C_{1}}\in\textrm{configs}_{T_{1}}$ as $[\![\overrightarrow{C_{1}}\,]\!]=\{\overrightarrow{C_{3}}\mid\overrightarrow{C% _{1}}=M_{31}(\overrightarrow{C_{3}})\}$ . If the configuration $\overrightarrow{C_{1}}$ has a non-empty set of representative configurations in $T_{2}$ , and each of those configurations have representative configurations in $T_{3}$ , then this set will contain all such configurations. Therefore, if both $M_{21}$ and subsequently $M_{32}$ are defined, this set will be non-empty.

We now show that $T_{3}$ simulates $T_{1}$ by proving that $T_{1}$ follows $T_{3}$ and $T_{3}$ models $T_{1}$ for the configuration mapping and representative configurations defined above. We then show that the simulation is polynomial efficient.

$T_{1}$ follows $T_{3}$ .

$T_{1}$ follows $T_{3}$ if for any two configurations $\overrightarrow{A_{3}}$ and $\overrightarrow{B_{3}}$ in $T_{3}$ where $M_{31}(\overrightarrow{A_{3}})$ and $M_{31}(\overrightarrow{B_{3}})$ are defined, such that $\overrightarrow{A_{3}}\Rightarrow_{T_{3}}\overrightarrow{B_{3}}$ , and $M_{31}(\overrightarrow{A_{3}})\not=M_{31}(\overrightarrow{B_{3}})$ , then $M_{31}(\overrightarrow{A_{3}})\rightarrow_{T_{1}}M_{31}(\overrightarrow{B_{3}})$ . For these configurations if $M_{32}(\overrightarrow{A_{3}})\not=M_{32}(\overrightarrow{B_{3}})$ then $M_{32}(\overrightarrow{A_{3}})\rightarrow_{T_{2}}M_{32}(\overrightarrow{B_{3}})$ . This is true because $T_{2}$ follows $T_{3}$ .
Because $T_{1}$ follows $T_{2}$ , for any two configurations $\overrightarrow{A_{2}}$ and $\overrightarrow{B_{2}}$ in $T_{2}$ , if $\overrightarrow{A_{2}}\Rightarrow_{T_{2}}\overrightarrow{B_{2}}$ , and $M_{21}(\overrightarrow{A_{2}})\not=M_{21}(\overrightarrow{B_{2}})$ , then $M_{21}(\overrightarrow{A_{2}})\rightarrow_{T_{1}}M_{21}(\overrightarrow{B_{2}})$ . A single-step transition is simply a macro-transition with one step. Therefore, if $M_{21}(M_{32}(\overrightarrow{A_{3}}))\not=M_{21}(M_{32}(\overrightarrow{B_{3}% }))$ , then $M_{21}(M_{32}(\overrightarrow{A_{3}}))\rightarrow_{T_{1}}M_{21}(M_{32}(% \overrightarrow{B_{2}}))$ . When $M_{31}$ is defined we can infer based on the definition of $M_{31}$ that, if $M_{31}(\overrightarrow{A_{3}})\not=M_{31}(\overrightarrow{B_{3}})$ then $M_{31}(\overrightarrow{A_{3}})\rightarrow_{T_{1}}M_{31}(\overrightarrow{B_{3}})$ . Therefore, $T_{1}$ follows $T_{3}$ .

$T_{3}$ models $T_{1}$ .

$T_{3}$ models $T_{1}$ if for any two configurations $\overrightarrow{A_{1}}$ and $\overrightarrow{B_{1}}$ in $T_{1}$ such that $\overrightarrow{A_{1}}\rightarrow_{T_{1}}\overrightarrow{B_{1}}$ , $\forall\overrightarrow{A_{3}}\in[\![\overrightarrow{A_{1}}\,]\!]$ , $\exists\overrightarrow{B_{3}}\in[\![\overrightarrow{B_{1}}\,]\!]$ under $M_{31}$ such that $\overrightarrow{A_{3}}\Rightarrow_{T_{3}}\overrightarrow{B_{3}}$ . For all such configurations $\overrightarrow{A_{1}}$ and $\overrightarrow{B_{1}}$ in $T_{1}$ , $\forall\overrightarrow{A_{2}}\in[\![\overrightarrow{A_{1}}\,]\!],\exists% \overrightarrow{B_{2}}\in[\![\overrightarrow{B_{1}}\,]\!]$ under $M_{21}$ such that $\overrightarrow{A_{2}}\Rightarrow_{T_{2}}\overrightarrow{B_{2}}$ because $T_{2}$ models $T_{1}$ . This macro transition $\overrightarrow{A_{2}}\Rightarrow_{T_{2}}\overrightarrow{B_{2}}$ is represented as a sequence of single-step transitions $\overrightarrow{X_{2}}^{i}\rightarrow_{T_{2}}\overrightarrow{X_{2}}^{i+1}$ where $M_{21}(\overrightarrow{X_{2}}^{i}),\,M_{21}(\overrightarrow{X_{2}}^{i+1})\in\{% \overrightarrow{A_{1}},\bot\}$ for $0\leq i<k$ as shown in Figure 4. Furthermore, $\forall\overrightarrow{X_{3}^{j}}\in[\![\overrightarrow{X_{2}}^{i}\,]\!]$ , $\exists\overrightarrow{X_{3}}^{\ell}\in[\![\overrightarrow{X_{2}}^{i+1}\,]\!]$ under $M_{32}$ such that $\overrightarrow{X_{3}}^{j}\Rightarrow_{T_{3}}\overrightarrow{X_{3}}^{\ell}$ because $T_{3}$ models $T_{2}$ .

Because $M_{32}(\overrightarrow{X_{3}}^{j})=\overrightarrow{X_{2}}^{i}$ and $M_{32}(\overrightarrow{X_{3}}^{\ell})=\overrightarrow{X_{2}}^{i+1}$ and $M_{21}(\overrightarrow{X_{2}}^{i}),\,M_{21}(\overrightarrow{X_{2}}^{i+1})\in\{% \overrightarrow{A_{1}},\bot\}$ , therefore, $M_{31}(\overrightarrow{X_{3}}^{j}),\,M_{31}(\overrightarrow{X_{3}}^{\ell})\in% \{\overrightarrow{A_{1}},\bot\}$ for $0\leq j<k$ and $j<\ell\leq k$ . As shown in Figure 4, the sequence of macro-transitions $\overrightarrow{X_{3}}^{j}\Rightarrow_{T_{3}}\overrightarrow{X_{3}}^{\ell}$ can be represented as a single macro-transition $\langle\overrightarrow{A_{3}},\overrightarrow{X_{3}}^{1},\ldots,% \overrightarrow{X_{3}}^{k},\overrightarrow{B_{3}}\rangle$ , where $M_{31}(\overrightarrow{X_{3}}^{j})\in\{\overrightarrow{A_{1}},\bot\}$ for $0\leq j\leq k$ . Also, $M_{32}(\overrightarrow{A_{3}})=\overrightarrow{A_{2}}$ and $M_{32}(\overrightarrow{B_{3}})=\overrightarrow{B_{2}}$ . We know that $M_{21}(\overrightarrow{A_{2}})=\overrightarrow{A_{1}}$ and $M_{21}(\overrightarrow{B_{2}})=\overrightarrow{B_{1}}$ , therefore, $M_{31}(\overrightarrow{A_{3}})=\overrightarrow{A_{1}}$ and $M_{31}(\overrightarrow{B_{3}})=\overrightarrow{B_{1}}$ when both $M_{21}$ and $M_{32}$ are defined. Hence, such a macro-transition $\overrightarrow{A_{3}}\Rightarrow_{T_{3}}\overrightarrow{B_{3}}$ models the single-step transition $\overrightarrow{A_{1}}\rightarrow_{T_{1}}\overrightarrow{B_{1}}$ when $\overrightarrow{A_{3}}\in[\![\overrightarrow{A_{1}}\,]\!]$ and $\overrightarrow{B_{3}}\in[\![\overrightarrow{B_{1}}\,]\!]$ . Therefore, $T_{3}$ models $T_{1}$ .

Figure 4: A single-step transition

\overrightarrow{A_{1}}\rightarrow_{T_{1}}\overrightarrow{B_{1}}

is simulated using a sequence of transitions starting at

\overrightarrow{A_{2}}

through

\overrightarrow{B_{2}}

in

T_{2}

. Each of these single-step is represented using a sequence of transitions in

T_{3}

.

Polynomial Simulation.

Given that $T_{2}$ simulates $T_{1}$ under polynomial simulation, and $T_{3}$ simulates $T_{2}$ under polynomial simulation, we now show that $T_{3}$ simulates $T_{1}$ under polynomial simulation. Let $\Lambda_{i}$ and $\Gamma_{i}$ be the set of species and reactions for the model $T_{i}$ for $1\leq i\leq 3$ .

1.

polynomial species and rules: We know that $\lvert\Lambda_{2}\rvert=\mathcal{O}(\lvert\Lambda_{1}\rvert)=\lvert\Lambda_{1}% \rvert^{c_{1}}$ and $\lvert\Lambda_{3}\rvert=\mathcal{O}(\lvert\Lambda_{2}\rvert)=\lvert\Lambda_{2}% \rvert^{c_{2}}$ , therefore, $\lvert\Lambda_{3}\rvert=\lvert\Lambda_{1}\rvert^{c_{1}\cdot c_{2}}$ . Similarly, $\lvert\Gamma_{3}\rvert=\lvert\Gamma_{1}\rvert^{c_{1}\cdot c_{2}}$ . Therefore, $\lvert\Lambda_{3}\rvert=\mathcal{O}(\lvert\Lambda_{1}\rvert)$ and $\lvert\Gamma_{3}\rvert=\mathcal{O}(\lvert\Gamma_{1}\rvert)$ .
2.

polynomial rule size: Let $\mathcal{R}_{i}$ be the largest rule in the model $T_{i}$ . We know that $\lvert\mathcal{R}_{2}\rvert=\mathcal{O}(\lvert\mathcal{R}_{1}\rvert)$ and $\lvert\mathcal{R}_{3}\rvert=\mathcal{O}(\lvert\mathcal{R}_{2}\rvert)$ , therefore, $\lvert\mathcal{R}_{3}\rvert=\mathcal{O}(\lvert\mathcal{R}_{1}\rvert)$ .
3.

polynomial transition sequences: The length of the transition sequence for a macro-transition in $T_{3}$ is bounded by $\mathcal{O}(\lvert\Lambda_{2}\rvert+\lvert\Gamma_{2}\rvert)$ . Given that $\lvert\Lambda_{2}\rvert=\lvert\Lambda_{1}\rvert^{c_{1}}$ and $\lvert\Gamma_{2}\rvert=\lvert\Gamma_{1}\rvert^{c_{1}}$ , therefore, each macro-transition in $T_{3}$ simulating a single-step in $T_{1}$ uses $\mathcal{O}(\lvert\Lambda_{1}\rvert+\lvert\Gamma_{1}\rvert)$ single-step transitions.
4.

polynomial volume: For a macro-transition $\overrightarrow{A_{2}}\Rightarrow_{T_{2}}\overrightarrow{B_{2}}$ representing a transition $\overrightarrow{A_{1}}\rightarrow_{T_{1}}\overrightarrow{B_{1}}$ , the volume of representative configurations $\overrightarrow{A_{2}}$ and $\overrightarrow{B_{2}}$ is polynomial in the volume of configurations $\overrightarrow{A_{1}}$ and $\overrightarrow{B_{1}}$ respectively. Similarly, for a macro-transition $\overrightarrow{A_{3}}\Rightarrow_{T_{3}}\overrightarrow{B_{3}}$ as shown in Figure 4, the volume of $\overrightarrow{A_{3}}$ and $\overrightarrow{B_{3}}$ is polynomial in volume of $\overrightarrow{A_{2}}$ and $\overrightarrow{B_{2}}$ respectively. Therefore, the volume of representative configurations $\overrightarrow{A_{3}}$ and $\overrightarrow{B_{3}}$ is polynomial in the volume of configurations $\overrightarrow{A_{1}}$ and $\overrightarrow{B_{1}}$ , where $\overrightarrow{A_{3}}\Rightarrow_{T_{3}}\overrightarrow{B_{3}}$ models $\overrightarrow{A_{1}}\rightarrow_{T_{1}}\overrightarrow{B_{1}}$ . The volume of all intermediate configurations are bound by $\overrightarrow{A_{3}}$ and $\overrightarrow{B_{3}}$ .

$\hfill\blacktriangleleft$

3 Detecting Zero: Examples in Each Model

The power each extended CRN model has over the basic CRN model stems from the ability to detect when a species has reached a count of zero. Thus, the focus of this section is twofold: to detail how each model is capable of detecting zero and to provide minimum working examples (MWEs) for ease of comprehension. For all examples, we want to check if species $s$ is in the system. The idea is that there is a species $c_{s}$ that turns to $n_{s}$ if there are no $s$ ’s and $y_{s}$ if there are $s$ ’s in the system while nothing else in the system changes.

Void Genesis.

Detecting zero is explicitly done by the model. For the simplest version of the model, we assume we have no $z$ species. To check whether $s$ is zero, simply use either as a catalyst (examples on the left side). For this to work, you must maintain a single $z$ . Thus, when producing any species $s$ , continue to check with $s$ as a catalyst and $z$ as a reactant. As an example, the rule $x\rightarrow s$ would be modified to be implemented with the two rules on the right side.

$c_{s}+s\rightarrow y_{s}+s$	$x+s\rightarrow 2s$
$s_{s}+z\rightarrow n_{s}+z$	$x+z\rightarrow s$

Inhibitory CRNs.

We can use an inhibited rule and a catalyst to detect whether a species $s$ exists or not.

$c_{s}\xrightarrow{s}n_{s}$	runs when $s$ does not exist
$c_{s}+s\rightarrow y_{s}+s$	runs when $s$ does exist

Course-Rate CRNs.

Detecting a species $s$ only requires that there is a fast rule that uses it and a slow rule that does not.

Fast Reaction	$c_{s}+s\rightarrow y_{s}+s$ (will always execute first)
Slow Reaction	$c_{s}\rightarrow n_{s}$ (will only execute if no $s$ exists in the system)

Step-Cycle CRNs.

Detecting zero is simple by using $s$ in a reaction and then going to another step. Since each step reaches a terminal configuration, it must not exist if the reaction did not occur.

Step	Description	Add	Rules
1	Add something that only reacts with $s$	a single $c_{s}$	$s+c_{s}\rightarrow y$
2	Check if it reacted	a single $w$	$w+y\rightarrow y_{s}+s$ ( $s$ exists) $w+c_{s}\rightarrow n_{s}$ ( $s$ not exists)

Unique-Instruction Parallel CRNs.

The parallel model UI takes advantage of how rules are applied to force reactions to run in a specific order depending on whether the count of a certain species is zero or not. Since we are limiting the possible rules that can run by our species selection, detecting zero can be done in this manner. The intuition is to run two independent rules, followed by a rule that uses the output of both. The “Round” indicates that all rules in this round would execute before the next round due to the maximal selection.

Round	Description	Rules
1	Create a timing/clock species ( $t_{i}$ ) and a species to use $s$ with.	$c_{s}\rightarrow r_{c}+t_{1}$
2	Try to use $s$ and use the timer $t$ in another rule.	$r_{c}+s\rightarrow r_{s}$ (can only run if $s$ exists) $t_{1}\rightarrow t_{2}$ (runs even if the other rule can not)
3	Now we use the timer to see if the other rule ran	$t_{2}+r_{s}\rightarrow y_{s}+s$ (there is an $s$ in the system) $t_{2}+r_{c}\rightarrow n_{s}$ (there are no $s$ ’s in the system)

4 Equivalence

This section shows equivalence between the CRN models, represented as the purple bi-directional arrows in Figure 1. We first introduce a more general Void Genesis model, along with some useful notation and techniques, before presenting our equivalence results. A full version of the paper, including construction details and formal proofs, is available on arXiv.

4.1 Equivalence Preliminaries

4.1.1 $𝒌$ -Void Genesis

Due to the complexity of some of the simulations, we first provide a more general version of the VG model that makes simulation easier. We will prove that the standard Void Genesis model can still simulate the more general model with at most a polynomial blow-up in rules, species, and expected rule applications. Essentially, the only difference is that rather than a single zero species $z$ , there can be a different zero species for every species.

Formally, a $k$ -Void Genesis CRN $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ is a CRN with a partial mapping function $Z_{\emptyset}:\Lambda_{1}\rightarrow\Lambda_{2}$ , such that $\Lambda_{1}\cup\Lambda_{2}=\Lambda$ and $\Lambda_{1}\cap\Lambda_{2}=\emptyset$ , that indicates which species is created whenever another species count goes to zero (if mapped). The partition creates a distinction between normal species and the special zero-counting species, which eliminates chaining effects that could arise with zero-species being created from the elimination of other zero-species. For convenience, we use the notation $Z_{\emptyset}(\lambda)\rightarrow z_{\lambda}$ to indicate that if the count of species $\lambda$ in the system goes to zero, a $z_{\lambda}$ species is created.

Definition 14 ( $k$ -Void-Genesis Dynamics).

For a $k$ -Void-Genesis CRN $((\Lambda,\Gamma),Z_{\emptyset})$ and configurations $\overrightarrow{A}$ , $\overrightarrow{B_{t}}$ and $\overrightarrow{B}$ , we say that $\overrightarrow{A}\rightarrow_{\mathcal{C_{KVG}}}^{(\Lambda,\Gamma)}% \overrightarrow{B}$ if there exists a rule $(\overrightarrow{R},\overrightarrow{P})\in\Gamma$ such that $\overrightarrow{R}\leq\overrightarrow{A}$ , $\overrightarrow{A}-\overrightarrow{R}+\overrightarrow{P}=\overrightarrow{B_{t}}$ , and $\overrightarrow{B}=\overrightarrow{B_{t}}+\overrightarrow{Z}$ where $\overrightarrow{Z}=\sum_{\lambda\in C}\vec{z}_{\lambda}$ , and $C=\{\lambda\in\Lambda|\overrightarrow{A}[\lambda]\not=0$ and $\overrightarrow{B_{t}}[\lambda]=0\}$ .

4.1.2 Notation and Techniques

Notation.

To simplify the proofs and for consistency, we use the following notation for rules. For rule $i$ , we have $\mathcal{G}_{i}=(\overrightarrow{\mathcal{R}_{i}},\overrightarrow{\mathcal{P}_% {i}})$ . We make use of the $\{\mathcal{R}\}$ and $|\mathcal{R}|$ notation defined in the preliminaries, as well the difference between a configuration with many species $\overrightarrow{X}$ versus a configuration with only a single species $\vec{X}$ by the over arrow used.

One technique that is used in our simulations is to maintain a single global leader species $G$ that selects which rule $\mathcal{G}_{i}$ to execute, and then a sequence of rules to either sequentially consume the reactants or sequentially break down the product of the other models’ rules to execute zero-checking before managing zero species.

Sequential Reactants.

Some of the results also benefit from processing the reactants of a rule one at a time as well. This is needed when consuming a species might result in its count as zero and some action needs to be taken. In order to verify that all reactants exists (and thus the rule could be executed), we use all reactants as a catalyst with a global leader species $G$ . Table 1(a) describes the necessary rules for consuming reactants sequentially. For rule $i$ , this creates $R_{i}^{1}$ that will begin the chain of consuming one species at a time. We create a $C_{i}^{j}$ species in order to check whether $r_{j}$ is now zero or not. This step can be skipped if no check is needed. We create the species $R_{i}^{j}$ sequentially, which is then consumed if $r_{j}$ is in the system. Systems that use this technique will have one copy of $G$ in the initial configuration and no $R$ or $C$ species. For shorthand, we will represent this series of rules as $\vec{G}+\overrightarrow{\mathcal{R}_{i}}\dashrightarrow\vec{G}+\overrightarrow% {\mathcal{P}_{i}}$ .

Sequential Products.

This technique only allows a single $G$ species to exist in the system at a time. Table 1(b) describes the necessary rules where a rule $\mathcal{G}_{i}=(\overrightarrow{\mathcal{R}_{i}},\overrightarrow{\mathcal{P}_% {i}})$ is chosen if the reactants exist in the system. If this is the case, then each product is created sequentially by having the species $P_{i}^{1},\ldots,P_{i}^{|\mathcal{P}_{i}|}$ in the system (one at a time, starting from $P_{i}^{1}$ ), then consuming each species $P_{i}^{j}$ to create the product $p_{j}$ and the next $P_{i}^{j+1}$ until all products have been produced. If species $P_{i}^{j}$ exists in the system, it means that for rule $\mathcal{G}_{i}$ , the first $j-1$ products have been created, and either the next $p_{j}$ will be created or the process will end (return $G$ ) if there are no more products.

In a simulating system, this requires an additional number of rules and species on the order of the largest number of products in any rule. The final rule returns the single leader species. Note that we make use of a zero species $z_{p_{j}}$ for every product species $p_{j}$ , i.e., $Z_{\emptyset}(p_{j})=z_{p_{j}}$ . For shorthand, we will represent this set of rules for rule $i$ as $\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p007-Bajaj.latexml-figure0.pdf}}}}}\overrightarrow{\mathcal{P}_{i}}$ . Thus, the entire set of rules and species from Table 1(b), that initiate with a global leader $G$ , would be given in shorthand as $\vec{G}+\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p007-Bajaj.latexml-figure1.pdf}}}}}\vec{G}+\overrightarrow{% \mathcal{P}_{i}}$ .

Table 1: An overview of two techniques. (a) A procedure to consume the reactants of some rule sequentially in order to test whether a rule can be applied and whether zero species are (or need to be) created. This is abbreviated for rule

i

as

\overrightarrow{\mathcal{R}_{i}}\dashrightarrow\overrightarrow{\mathcal{P}_{i}}

. (b) Creating products sequentially by consuming all reactants and then using counter species to create each product with a different rule until all have been created. This may be needed to decrease the number of rule combinations while handling zero species. Note that the zero species

z_{p_{j}}

is consumed when

p_{j}

is created. If

p_{j}

still exists, then it is used as a catalyst. This process is denoted for some rule

i

as

\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p007-Bajaj.latexml-figure3.pdf}}}}}\overrightarrow{\mathcal{P}_{i}}

.

	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{R}_{i}^{1}+% \overrightarrow{\mathcal{R}_{i}}$
	$\vec{R}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{C}_{i}^{j}$ (check for zero)
$\forall r_{j}\in\mathcal{R}_{i}:$	$\vec{C}_{i}^{j}+\vec{z}_{r_{j}}\rightarrow\vec{R}_{i}^{j+1}+\vec{z}_{r_{j}}$ ( $r_{j}$ is zero)
$\forall r_{j}\in\mathcal{R}_{i}:$	$\vec{C}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{R}_{i}^{j+1}+\vec{r}_{j}$ ( $r_{j}$ is not zero)
	$\vec{R}_{i}^{\|\mathcal{R}_{i}\|+1}\rightarrow\vec{G}+\overrightarrow{\mathcal{P% }_{i}}$

(a) Using reactants sequentially

\overrightarrow{\mathcal{R}_{i}}\dashrightarrow\overrightarrow{\mathcal{P}_{i}}

.

	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{P}_{i}^{1}$
$\forall p_{j}\in\mathcal{P}_{i}:$	$\vec{z}_{p_{j}}+\vec{P}_{i}^{j}\rightarrow\vec{p}_{j}+\vec{P}_{i}^{j+1}$ (remove zero)
$\forall p_{j}\in\mathcal{P}_{i}:$	$\vec{p}_{j}+\vec{P}_{i}^{j}\rightarrow\vec{p}_{j}+\vec{p}_{j}+\vec{P}_{i}^{j+1}$ (no zero)
	$\vec{P}_{i}^{\|\mathcal{P}_{i}\|+1}\rightarrow\vec{G}$

(b) Creating products sequentially

\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p007-Bajaj.latexml-figure5.pdf}}}}}\overrightarrow{\mathcal{P}_{i}}

.

4.2 $𝒌$ -Void Genesis equivalence with Void Genesis

Lemma 15.

The $k$ -Void Genesis model can simulate the Void Genesis model.

Construction.

Given a Void Genesis model $\mathcal{C_{VG}}=((\Lambda,\Gamma),z)$ , let $Z_{\emptyset}(\lambda)=z$ , $\forall\lambda\in\Lambda\setminus\{z\}$ . Then the $k$ -Void Genesis model $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ is equivalent.

Lemma 16.

The Void Genesis model can simulate the $k$ -Void Genesis model.

Construction.

This result is straightforward using the methods to sequentially consume reactants as previously defined. We slightly modify them with specifics as shown in Table 2. Whenever we consume a reactant $r_{j}$ , we check if the single $z$ species exists and if it does, create the specific $z_{r_{j}}$ species if $r_{j}$ is mapped in $Z_{\emptyset}$ .

Given a $k$ -Void Genesis model $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ , we create a VG CRN $\mathcal{C_{VG}}=((\Lambda^{\prime},\Gamma^{\prime}),z)$ . We let $\Lambda^{\prime}=\Lambda\cup\{G\}\cup\{z_{\lambda}:\lambda\in\Lambda\setminus% \{z\}\}\cup S_{R}$ where $S_{R}=\{R_{i}^{j}:1\leq i\leq|\Gamma|,1\leq j\leq|\mathcal{R}_{i}|+1\}$ . We can simulate having specific $z_{j}$ species for all $j$ species by keeping the $z$ species count at 0, and checking whether we consumed the last $j$ .

Table 2: (a) The rules for the simulation of

k

-Void Genesis by Void Genesis. For each applicable rule, we create a set of rules that sequentially consume each reactant

r_{j}

, and if its count is now zero, it creates the

z_{r_{j}}

species (unless it is unmapped, then

z

is simply consumed). Only one of the zero check rules is added based on the mapping, which is why they are grouped. (b) The reactions that simulate the rule

\vec{a}+2\vec{b}\rightarrow 2\vec{a}+\vec{c}

from the

k

-VG model within the VG model.

	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{R}_{i}^{1}+% \overrightarrow{\mathcal{R}_{i}}$	$\vec{G}+\vec{a}+2\vec{b}\rightarrow\vec{R}_{1}^{1}+\vec{a}+2\vec{b}$
$\forall r_{j}\in\mathcal{R}_{i}:$	$\vec{R}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{C}_{i}^{j}$ (check for zero)	$\vec{R}_{1}^{1}+\vec{a}\rightarrow\vec{C}_{1}^{1}$	$\vec{C}_{1}^{2}+\vec{b}\rightarrow\vec{R}_{1}^{3}+\vec{b}$
	$\begin{cases}\vec{C}_{i}^{j}+\vec{z}\rightarrow\vec{R}_{i}^{j+1}\text{(% unmapped species)}\\ \vec{C}_{i}^{j}+\vec{z}\rightarrow\vec{R}_{i}^{j+1}+\vec{z}_{r_{j}}\text{(zero% species)}\end{cases}$	$\vec{C}_{1}^{1}+\vec{z}\rightarrow\vec{R}_{1}^{2}+\vec{z}_{a}$	$\vec{R}_{1}^{3}+\vec{b}\rightarrow\vec{C}_{1}^{3}$
		$\vec{C}_{1}^{1}+\vec{a}\rightarrow\vec{R}_{1}^{2}+\vec{a}$	$\vec{C}_{1}^{3}+\vec{z}\rightarrow\vec{R}_{1}^{4}+\vec{z}_{b}$
	$\vec{C}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{R}_{i}^{j+1}+\vec{r}_{j}$ (count not zero)	$\vec{R}_{1}^{2}+\vec{b}\rightarrow\vec{C}_{1}^{2}$	$\vec{C}_{1}^{3}+\vec{b}\rightarrow\vec{R}_{1}^{4}+\vec{b}$
	$\vec{R}_{i}^{\|\mathcal{R}_{i}\|+1}\rightarrow\vec{G}+\overrightarrow{\mathcal{P% }_{i}}$	$\vec{C}_{1}^{2}+\vec{z}\rightarrow\vec{R}_{1}^{3}+\vec{z}_{b}$	$\vec{R}_{1}^{4}\rightarrow\vec{G}+2\vec{a}+\vec{c}$
(a) Zero checking reactants $\overrightarrow{\mathcal{R}_{i}}\dashrightarrow\overrightarrow{\mathcal{P}_{i}}$ .		(b) Example reaction set.

Theorem 17.

The Void Genesis model is equivalent under polynomial simulation to the $k$ -Void Genesis model.

4.3 Inhibitory CRNs

Lemma 18.

Inhibitory CRNs can simulate any given $k$ -VG CRN under polynomial simulation.

Construction.

Given a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ , we construct an Inhibitory CRN $\mathcal{C_{IC}}=((\Lambda^{\prime},\Gamma^{\prime}),\mathcal{I})$ . We let $\Lambda^{\prime}=\Lambda\cup\{I,e_{\lambda_{1}},\cdots,e_{\lambda_{\lvert% \Lambda_{1}\rvert}}\}$ where $I$ and $e_{\lambda_{1}},\ldots,e_{\lambda_{\lvert\Lambda_{1}\rvert}}$ check if any species of $\Lambda_{1}$ used in a simulated reaction have a resulting count of zero. Recall that $\Lambda_{1}$ is the set of non-zero species in $\Lambda$ . Each reaction in $\Gamma$ $\mathcal{\gamma}_{i}$ is simulated using Reaction 1 from Table 3 $a$ . Reactions 2 and 3 check if any reactants of $\mathcal{\gamma}_{i}$ reached a count of zero following $\mathcal{\gamma}_{i}$ ’s simulation. If so, then a corresponding zero species is produced. Figure 5(a) shows an example of an Inhibitory CRN simulating a $k$ -VG CRN with $\Lambda=\{a,b\}$ and a reaction that consumes the species $a$ .

Table 3: (a) Reactions for an Inhibitory CRN to simulate any given

k

-VG CRN. (b) Reactions for a

k

-VG CRN to simulate any given Inhibitory CRN.

$\forall\mathcal{\gamma}_{i}\in\Gamma:$	$1 .$	$\overrightarrow{\mathcal{R}}_{i}\xrightarrow{I}\overrightarrow{e}_{\{\mathcal{% R}_{i}\}}+\overrightarrow{\mathcal{P}}_{i}+\lvert\{\mathcal{R}_{i}\}\rvert% \cdot\vec{I}$	$\forall\mathcal{\gamma}_{i}\in\Gamma:$	$1 .$	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}+\overrightarrow{Z_{i}}\rightarrow\vec% {G}_{i}+\overrightarrow{\mathcal{R}_{i}}+\overrightarrow{Z_{i}}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$2 .$	$\vec{e}_{\lambda_{i}}+\vec{I}+\vec{\lambda}_{i}\rightarrow\vec{\lambda}_{i}$	$\forall\mathcal{\gamma}_{i}\in\Gamma:$	$2 .$	$\vec{G}_{i}+\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{% }{dagpub-tikzpictures/p007-Bajaj.latexml-figure6.pdf}}}}}\vec{G}+% \overrightarrow{\mathcal{P}_{i}}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$3 .$	$\vec{e}_{\lambda_{i}}+\vec{I}\xrightarrow{\lambda_{i}}\vec{z}_{\lambda_{i}}$
(a) iCRN simulating $k$ -VG.			(b) $k$ -VG simulating iCRN.

(a)

\mathcal{C_{IC}}\rightarrow\mathcal{C_{KVG}}

(b)

\mathcal{C_{KVG}}\rightarrow\mathcal{C_{IC}}

Figure 5: (a) A rule application in the simulated

k

-void genesis CRN

\mathcal{C_{KVG}}

and the equivalent rule application sequence in the simulating inhibitory CRN

\mathcal{C_{IC}}

. The dashed arrows represent mapping a configuration of

\mathcal{C_{IC}}

to a configuration of

\mathcal{C_{KVG}}

. (b) The other direction.

Lemma 19.

k-VG CRNs can simulate any Inhibitory CRN under polynomial simulation.

Construction.

Given an Inhibitory CRN $\mathcal{C_{IC}}=((\Lambda,\Gamma),\mathcal{I})$ , we construct a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda^{\prime},\Gamma^{\prime}),Z_{\emptyset})$ . We let $\Lambda^{\prime}=\Lambda\cup\{G,G_{1},\ldots,G_{\lvert\Gamma\rvert},P_{i}^{1},% \ldots,P_{\lvert\Gamma\rvert}^{\lvert\mathcal{P}_{\lvert\Gamma\rvert}\rvert+1}% ,z_{\lambda_{1}},\ldots,z_{\lambda_{\lvert\Lambda\rvert}}\}$ where the global species $G$ is consumed to produce $G_{i}$ when selecting a reaction $\mathcal{\gamma}_{i}\in\Gamma$ . The $z$ species are the zero-species, and the species $P_{i}^{1}\ldots P_{i}^{\lvert\mathcal{P}_{i}\rvert+1}$ are produced for the sequential product generation as described in Table 1(b). Let $Z_{i}$ represent the set of $z$ species corresponding to inhibitors of $\mathcal{\gamma}_{i}$ . Each reaction $\mathcal{\gamma}_{i}$ in $\Gamma$ is represented by the two reactions given in Table 3 $b$ , where Reaction 1 checks if $\mathcal{\gamma}_{i}$ is applicable (indicated by the presence of reactants of $\mathcal{\gamma}_{i}$ and $Z_{i}$ ) and Reaction 2 applies the reaction by generating products sequentially. Figure 5(b) shows an example of a $k$ -VG CRN simulating an Inhibitory CRN with $\Lambda=\{a,b\}$ and a reaction that consumes $b$ if $a$ is absent.

Theorem 20.

The Void Genesis model is equivalent under polynomial simulation to the Inhibitory model.

4.4 Coarse-Rate CRNs

Lemma 21.

Coarse-Rate CRNs can simulate any given k-VG CRN under polynomial simulation.

Construction.

Given a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ , we construct a Course-Rate CRN $\mathcal{C_{CR}}=((\Lambda^{\prime},\Gamma^{\prime}),rank)$ . Let $\Lambda^{\prime}=\Lambda\cup\{x,y,G,e_{\lambda_{1}},\cdots,e_{\lambda_{\lvert% \Lambda_{1}\rvert}}\}$ where $G$ is used to select a reaction and species $x$ and $y$ check if any non-zero species in $\Lambda$ have a count of zero. Additionally, $e_{\lambda_{1}},\cdots,e_{\lambda_{\lvert\Lambda_{1}\rvert}}$ are used to check the counts of the $\lambda_{i}\in\Lambda_{1}$ that are relevant to the simulated reaction, where $\Lambda_{1}$ is the set of non-zero species in $\Lambda$ . As shown in Table 4 $a$ , each reaction $\mathcal{\gamma}_{i}\in\Gamma$ is simulated using $3$ fast reactions which check if any involved reactant reached a count of zero and generates the corresponding zero species if so, along with applying the original reaction. Finally the $2$ slow reactions use up any $x$ or $y$ species in the system to produce $G$ . This allows the system to apply another reaction in $\Gamma$ . Figure 6 shows an example of a Coarse-Rate CRN simulating a $k$ -VG CRN with $\Lambda=\{a,b\}$ and a reaction that consumes $a$ , hence, producing $z_{a}$ .

Table 4: (a) Reactions for a Coarse-Rate CRN to simulate any given

k

-VG CRN. (b) Reactions for a

k

-VG CRN to simulate any given Coarse-Rate CRN.

				$1 .$	$\vec{G}+\vec{g}_{i}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{r}_{1}+% \overrightarrow{\mathcal{P}_{i}}$
Fast Reactions (Rank 2)			$\forall\mathcal{\gamma}_{i}^{2}\in\Gamma^{2}$ ,	$1b.$	$\vec{G}+\vec{g}_{i}+\vec{z}_{k}\rightarrow\vec{G}+\vec{z}_{k}$
$\forall$ $\mathcal{\gamma}_{i}\in\Gamma:$	$1 .$	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{x}+\overrightarrow{e}_% {\{\mathcal{R}_{i}\}}+\overrightarrow{\mathcal{P}_{i}}$	$z_{k}\in\{\mathcal{R}_{i}\}$ :	$2 .$	$\vec{r}_{j}+\vec{g}_{j}\rightarrow\vec{r}_{j+1}+\vec{g}_{j}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$2 .$	$\vec{x}+\vec{e}_{\lambda_{i}}+\vec{\lambda}_{i}\rightarrow\vec{x}+\vec{\lambda% }_{i}$		$3 .$	$\vec{r}_{j}+\vec{z}_{g_{j}}\rightarrow\vec{r}_{j+1}+\vec{g}_{j}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$3 .$	$\vec{y}+\vec{e}_{\lambda_{i}}\rightarrow\vec{y}+\vec{z}_{\lambda_{i}}$		$4 .$	$\vec{r}_{\|\Gamma^{2}\|+1}\rightarrow\vec{G}$
Slow Reactions (Rank 1)				$5 .$	$\vec{G}+\vec{z}_{g_{1}}+\ldots+\vec{z}_{g_{\|\Gamma^{2}\|}}\rightarrow\vec{s}$
	$4 .$	$\vec{x}\rightarrow\vec{y}$		$6 .$	$\vec{t}\rightarrow\vec{G}+\vec{g}_{1}+\ldots+\vec{g}_{\|\Gamma^{2}\|}$
	$5 .$	$\vec{y}\rightarrow\vec{G}$	$\forall\mathcal{\gamma}_{i}^{1}\in\Gamma^{1}$ :	$7 .$	$\vec{s}+\overrightarrow{\mathcal{R}_{i}}\raisebox{2.5pt}{\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p007-Bajaj.latexml-figure7.pdf}}}}}\vec{t}+\overrightarrow{% \mathcal{P}_{i}}$
(a) Coarse-Rate CRN simulating $k$ -VG CRN.			(b) $k$ -VG CRN simulating Coarse-Rate CRN.

Figure 6: A rule application in the simulated

k

-void genesis CRN

\mathcal{C_{KVG}}

and the equivalent rule application sequence in the simulating Coarse-Rate CRN

\mathcal{C_{CR}}

.

Lemma 22.

k-VG CRNs can simulate any given Coarse-Rate CRN under polynomial simulation.

Construction.

Given a Coarse-Rate CRN $\mathcal{C_{CR}}=((\Lambda,\Gamma),rank)$ , we construct a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda^{\prime},\Gamma^{\prime}),Z_{\emptyset})$ . Let $\Lambda^{\prime}=\Lambda\cup\{G,g_{1},\cdots,g_{\lvert\Gamma^{2}\rvert},z_{g_{% 1}},\cdots,z_{g_{\lvert\Gamma^{2}\rvert}},z_{\lambda_{1}},\cdots,z_{\lambda_{% \lvert\Lambda\rvert}},P_{1}^{1},\cdots$ , $P_{\lvert\Gamma^{1}\rvert}^{\lvert\mathcal{P}_{\lvert\Gamma^{1}\rvert}\rvert+1% },s,t\}$ as follows. $G$ and a random $g_{i}$ species is consumed to select a random fast reaction $\mathcal{\gamma}_{i}^{2}\in\Gamma^{2}$ as illustrated in Table 4 $b$ . We additionally add $P_{1}^{1},\cdots,P_{\lvert\Lambda\rvert}^{\lvert\mathcal{P}_{\lvert\Lambda% \rvert}\rvert+1}$ for generating the products of any slow reaction. We add species $s$ to signify that no fast reactions are applicable and species $t$ to signify that a slow reaction has been applied. Finally, we add a zero species for all $g_{i}$ species. Figure 7 shows an example of a $k$ -VG CRN simulating a Course-Rate CRN with $\Lambda=\{a,b\}$ and a fast reaction that deletes $a$ and a slow reaction that deletes $b$ .

Figure 7: A rule application in the simulated Coarse-Rate CRN

\mathcal{C_{CR}}

and the equivalent rule application sequence in the simulating

k

-void genesis CRN

\mathcal{C_{KVG}}

.

Theorem 23.

The Void Genesis model is equivalent under polynomial simulation to the Course-Rate model.

4.5 Step-Cycle CRNs

Lemma 24.

Step-Cycle CRNs can simulate any given k-VG CRN under polynomial simulation.

Construction.

Given a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda,\Gamma),Z_{\emptyset})$ , we construct a Step-Cycle CRN $\mathcal{C_{SC}}=((\Lambda^{\prime},\Gamma^{\prime}),\overrightarrow{S}_{0})$ . We let $\Lambda^{\prime}=\Lambda\cup\{G,y,x,w,e_{\lambda_{1}},\ldots,e_{\lambda_{% \lvert\Lambda_{1}\rvert}},z_{\lambda_{1}},\ldots,z_{\lambda_{|\Lambda_{2}|}}\}$ and $\overrightarrow{S}_{0}=\vec{y}$ . The $G$ species is used to select a reaction, and $y$ is used to check if any non-zero species in $\Lambda$ have a count of zero. Finally, $e_{\lambda_{1}},\cdots,e_{\lambda_{\lvert\Lambda_{1}\rvert}}$ are used to check the counts of the $\lambda_{i}\in\Lambda_{1}$ that are relevant to the simulated reaction, where $\Lambda_{1}$ is the set of non-zero species in $\Lambda$ . Each reaction $\mathcal{\gamma}_{i}\in\Gamma$ is simulated by Reaction 1 as given in Table 5a. Reactions 2 consumes $e$ species for any reactant whose count does not reach zero. Once the system is terminal, a $y$ is added so as to generate $z$ species corresponding to the remaining reactants using Reaction 3. Another $y$ is added to enable Reaction 4. Once no reaction is applicable in $\Gamma$ , another $y$ is added to enable Reaction 5, which allows Reaction 6 to execute infinitely. Finally, the system reaches a terminal configuration and prevents the volume from growing infinitely. Figure 8 shows an example of a Step-Cycle CRN simulating a $k$ -VG CRN with $\Lambda=\{a,b\}$ and a reaction that consumes the species $a$ .

Table 5: (a) Reactions for a Step-Cycle CRN to simulate any given k-VG CRN. (b) Reactions for a k-VG CRN to simulate any given Step-Cycle CRN.

				$1 .$	$\vec{G}+\vec{g}_{i}\dashrightarrow\vec{r}_{1}+\overrightarrow{\mathcal{P}_{i}}$
			$\forall\mathcal{\gamma}_{i}\in\Gamma$ , $z_{k}\in\{\mathcal{R}_{i}\}$ :	$2 .$	$\vec{r}_{j}+\vec{g}_{j}\rightarrow\vec{r}_{j+1}+\vec{g}_{j}$
$\forall\mathcal{\gamma}_{i}\in\Gamma:$	$1 .$	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\overrightarrow{e}_{\{% \mathcal{R}_{i}\}}+\overrightarrow{\mathcal{P}_{i}}$		$3 .$	$\vec{r}_{j}+\vec{z}_{g_{j}}\rightarrow\vec{r}_{j+1}+\vec{g}_{j}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$2 .$	$\vec{\lambda}_{i}+\vec{e}_{\lambda_{i}}\rightarrow\vec{\lambda}_{i}$		$4 .$	$\vec{r}_{\|\Gamma\|+1}\rightarrow\vec{G}$
$\forall\lambda_{i}\in\Lambda_{1}:$	$3 .$	$\vec{y}+\vec{e}_{\lambda_{i}}\rightarrow\vec{y}+\vec{z}_{\lambda_{i}}$		$5 .$	$\vec{G}+\vec{z}_{g_{1}}+\ldots+\vec{z}_{g_{\|\Gamma\|}}\rightarrow\vec{s}$
	$4 .$	$\vec{y}+\vec{y}\rightarrow\vec{G}$		$6 .$	$\vec{t}\rightarrow\vec{G}+\vec{g}_{1}+\ldots+\vec{g}_{\|\Gamma\|}$
	$5 .$	$\vec{G}+\vec{y}\leftrightarrow\vec{G}+\vec{w}$	$\forall S_{i}\in S\setminus\{S_{k-1}\}:$	$7 .$	$\vec{s}+\vec{s}_{i}\raisebox{2.5pt}{\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate\hbox{% \lower 2.59998pt\hbox{{\includegraphics{}{}{dagpub-tikzpictures/p007-Bajaj.lat% exml-figure8.pdf}}}}}\vec{t}+\vec{s}_{i+1}+\overrightarrow{S}_{i}$
	$6 .$	$\vec{w}\leftrightarrow x$		$8 .$	$\vec{s}+\vec{s}_{k-1}\raisebox{2.5pt}{\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate{} \hbox to17.47pt{\vbox to5.2pt{% \pgfpicture\makeatletter\hbox{\thinspace\lower-2.59998pt\hbox to0.0pt{% \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}% \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}% {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }% \nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{} {}{}{}{{ {\pgfsys@beginscope \pgfsys@setdash{\pgf@temp}{\the\pgf@x}\pgfsys@roundcap\pgfsys@roundjoin{} {}{}{} {}{}{} \pgfsys@moveto{-2.07999pt}{2.39998pt}\pgfsys@curveto{-1.69998pt}{0.95998pt}{-0% .85318pt}{0.28pt}{0.0pt}{0.0pt}\pgfsys@curveto{-0.85318pt}{-0.28pt}{-1.69998pt% }{-0.95998pt}{-2.07999pt}{-2.39998pt}\pgfsys@stroke\pgfsys@endscope}} }{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{5.29047pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.49046pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} {}{{}}{} {}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{10.98093pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{11.18092pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} {}{{}}{} {}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{16.67183pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{16.87183pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}}\vec{t}+\vec{s}_{0}+\overrightarrow{S% }_{k-1}$
(a) Step-Cycle CRN sim. $k$ -VG CRN.			(b) $k$ -VG CRN simulating a Step-Cycle CRN.

Table 6: (a) Checking reactants sequentially

\overrightarrow{\mathcal{R}_{i}}\dashrightarrow\overrightarrow{\mathcal{P}_{i}}

(b) Undoing reaction selection if not enough reactants exist for rule

i

.

			$\vec{R}_{i}^{k}+\vec{z}_{\lambda_{j}}\rightarrow\vec{R}_{i}^{k^{-}}+\vec{z}_{% \lambda_{j}}$
	$\vec{G}+\vec{g}_{i}\rightarrow\vec{R}_{1}^{1}$ + $\vec{z}_{g_{i}}$	$\forall\lambda_{j}\in\mathcal{R}_{i}:$	$\vec{R}_{i}^{k^{-}}+\vec{z}_{\lambda_{j}}\rightarrow\vec{R}_{i}^{k-1^{-}}+\vec% {\lambda}_{j}$
$\forall\lambda_{j}\in\mathcal{R}_{i}:$	$\vec{R}_{i}^{k}+\vec{\lambda}_{j}\rightarrow\vec{R}_{i}^{k+1}+\vec{\lambda}_{j% }^{\prime}$	$\forall\lambda_{j}\in\mathcal{R}_{i}:$	$\vec{R}_{i}^{k^{-}}+\vec{\lambda}_{j}^{\prime}\rightarrow\vec{R}_{i}^{k^{-}}+% \vec{\lambda}_{j}$
$\forall\lambda_{j}\in\mathcal{R}_{i}:$	$\vec{R}_{i}^{\|\mathcal{R}_{i}\|+1}+\overrightarrow{\mathcal{R}_{i}}^{\prime}% \raisebox{2.5pt}{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate{} \hbox to17.47pt{\vbox to5.2pt{\pgfpicture\makeatletter% \hbox{\thinspace\lower-2.59998pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke% { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}% \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }% \pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt% {\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}{} {}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{5.29047pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.49046pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} {}{{}}{} {}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{10.98093pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{11.18092pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} {}{{}}{} {}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{16.67183pt}{0.0pt}% \pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope% \pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{16.87183pt}{0.0pt}% \pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}% }}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{% }\pgfsys@endscope\hss}}\endpgfpicture}}}\vec{r}_{1}+\overrightarrow{\mathcal{% P}}_{i}$		$\vec{R}_{1}^{1^{-}}\rightarrow\vec{G}$
(a) Check reactants.		(b) Undo reactants.

Figure 8: A rule application in the simulated

k

-VG CRN

\mathcal{C_{KVG}}

and the equivalent rule application sequence in the simulating Step-Cycle CRN

\mathcal{C_{SC}}

.

Lemma 25.

k-VG CRNs can simulate any given Step-Cycle CRN under polynomial simulation.

Construction.

Given a Step-Cycle CRN $\mathcal{C_{SC}}=((\Lambda,\Gamma),(\overrightarrow{S}_{0},\overrightarrow{S}_% {1},\ldots,\overrightarrow{S}_{k-1})$ , we construct a $k$ -VG CRN $\mathcal{C_{KVG}}=((\Lambda^{\prime},\Gamma^{\prime}),Z_{\emptyset})$ . We let $\Lambda^{\prime}=\Lambda\cup\{G,\lambda_{1}^{\prime},\ldots,\lambda_{|\Lambda|% }^{\prime},z_{\lambda_{1}},\ldots,z_{\lambda_{|\Lambda|}},r_{1},\ldots,r_{% \lvert\Gamma\rvert+1}$ , $s,s_{0},\ldots,s_{k-1},t\}\cup\{g_{i},z_{g_{i}},R_{i}^{j},R_{i}^{j^{-}},P_{i}^% {l}:1\leq i\leq|\Gamma|,1\leq j\leq|\mathcal{R}_{i}|+1,1\leq l\leq|\mathcal{P}% _{i}|+1\}$ . The $G$ species is used to select a reaction represented by $g_{i}$ . The reactants are checked sequentially, converting each reactant into $\lambda_{i}^{\prime}$ . Species $r_{i}$ reintroduce each consumed $g_{i}$ into the system. Species $s_{i}$ represent step $i$ , with species $s$ and $t$ used to transition between steps. Reaction $1$ in Table 5b attempts to apply $\mathcal{\gamma}_{i}$ by checking if enough of each reactant exists, as shown in Table 6. If it is successful, then it simulates the reaction and begins the process of adding $g_{1},\ldots,g_{\lvert\Gamma\rvert}$ back into the system (which is carried out in reactions $2$ , $3$ , and $4$ ). If a species in $\mathcal{\gamma}_{i}$ does not exist in the system, then the reactants are reintroduced into the system as shown in Table 6, which also removes $g_{i}$ from the system, producing $z_{g_{i}}$ . If there are no executable reactions, then reaction $5$ is executed to produce an $s$ species. This $s$ species then reacts with the current “step” of the system, denoted by species $s_{i}$ . Reaction 7 or 8 then runs, introducing the species corresponding to the step. These reactions also introduce the species $t$ , which then reintroduces $G$ along with each $g_{i}$ through reaction $6$ . Figure 9 shows an example of a $k$ -VG CRN simulating a Step-Cycle CRN with $\Lambda=\{a,b\}$ and reaction $a+b\rightarrow b$ .

Figure 9: A rule application in the simulated Step-Cycle CRN

\mathcal{C_{SC}}

and the equivalent rule application sequence in the simulating

k

-VG CRN

\mathcal{C_{KVG}}

.

Theorem 26.

The Void Genesis model is equivalent under polynomial simulation to the Step-Cycle model.

Extension to deletion-only rules.

Given the recent result in [20], these results extend to give the following corollary.

Corollary 27.

Even when restricted to at most $(3,1)$ void rules, the Step-Cycle model is equivalent under polynomial simulation to the Void Genesis model.

4.6 Unique-Instruction Parallel Model

Lemma 28.

UI parallel CRNs can simulate any given VG CRN.

Construction.

Given a Void-Genesis CRN $\mathcal{C_{VG}}=((\Lambda,\Gamma),z)$ , we construct the UI parallel CRN $\mathcal{C_{UI}}=(\Lambda^{\prime},\Gamma^{\prime})$ . We create $\Lambda^{\prime}=\Lambda\cup\{G,E,t^{2}\}\cup\{e_{\lambda_{j}},t_{j}^{1},r_{j}% ^{1},r_{j}^{2},G_{i}:i\in\{1,\dots,|\Gamma|\},j\in\{1,\dots,|\{\mathcal{R}_{i}% \}|\}\}$ . The global species $G$ selects a rule $\mathcal{\gamma}_{i}\in\Gamma$ non-deterministically, and produces $G_{i}$ to disallow Reaction 1 from running again prematurely, a set of species $e_{\lambda}$ , and the products of $\mathcal{\gamma}_{i}$ , as shown in Table 7 $a$ . The $e_{\lambda}$ species then creates a timer species $t^{i}_{j}$ , and a checker species $r^{1}_{j}$ , which is used to check if a species exists in the system. In Reaction 3, the rules run in parallel, so the timer species goes down, and at the same time, we check if any checker species have incremented. Reaction 4 either reintroduces the consumed species or creates the zero species $z$ , based on the checker species. Both reactions produce the species $E$ , which is later used in Reaction 5 to reintroduce the $G$ species, allowing the system to run another reaction. Figure 10 shows an example of a UI CRN simulating a VG CRN with $\Lambda=\{a,b\}$ and the rule $a+b\rightarrow b$ . .

Figure 10: A rule application in the simulated void genesis CRN

\mathcal{C_{VG}}

and the equivalent rule application sequence in the simulating Unique Instruction CRN

\mathcal{C_{UI}}

.

Table 7: (a) Reactions for a UI parallel CRN to simulate any given VG CRN. Here,

\overrightarrow{e_{\{\mathcal{R}_{i}\}}}

is an

e_{\lambda_{j}}

species created for each of the

j

different reactants in

\mathcal{R}_{i}

(only one

e

is created if multiple copies of that species are used). (b) Reactions for a kVG CRN to simulate any given UI parallel CRN.

			$\forall\gamma_{i}\in\Gamma,$	$\vec{G}_{i}+\vec{z}_{r_{j}}\rightarrow\vec{N}_{i}+\vec{X}_{i}+\vec{z}_{r_{j}}$ (can not run)
			$\forall r_{j}\in\mathcal{R}_{i}:$
			seq.	$\vec{G}_{i}+\vec{r}_{1}\rightarrow\vec{R}_{i}^{2}$
$\forall\mathcal{\gamma}_{i}\in\Gamma:$	$1 .$	$\vec{G}+\overrightarrow{\mathcal{R}_{i}}\rightarrow\vec{G_{i}}+\overrightarrow% {e_{\{\mathcal{R}_{i}\}}}+\overrightarrow{\mathcal{P}_{i}}$	reacts.	$\vec{R}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{R}_{i}^{j+1}$
$\forall\lambda_{j}\in\Lambda_{1}:$	$2 .$	$\vec{e}_{\lambda_{j}}\rightarrow\vec{r}^{1}_{j}+\vec{t}^{1}_{j}$		$\vec{R}_{i}^{j}+\vec{z}_{r_{j}}\rightarrow\vec{N}_{i}+\vec{X}_{i}+\vec{r}_{1}+% \ldots+\vec{r}_{j-1}+\vec{z}_{r_{j}}$
	$3 .$	$\vec{r}^{1}_{j}+\vec{\lambda}_{i}\rightarrow\vec{r}^{2}_{j}$	$j=\|\mathcal{R}_{i}\|$	$\vec{R}_{i}^{j}+\vec{r}_{j}\rightarrow\vec{I}_{i}+\vec{X}_{i}$ (rule selected)
		$\vec{t}^{1}_{j}\rightarrow\vec{t}_{2}$		$X_{1}+\ldots+X_{\|\Gamma\|}\rightarrow\vec{F}$ (rules selected)
	$4 .$	$\vec{t}_{2}+\vec{r}^{2}_{j}\rightarrow\vec{\lambda}_{i}+\vec{E}$	$\forall\gamma_{i}\in\Gamma$	$\vec{I}_{i}+\vec{F}\rightarrow\vec{F}_{i}+\vec{F}+\overrightarrow{\mathcal{P}}% _{i}$ (output)
		$\vec{t}_{2}+\vec{r}^{1}_{j}\rightarrow\vec{z}+\vec{E}$		$\vec{N}_{i}+\vec{F}\rightarrow\vec{F}_{i}+\vec{F}$ (not run)
	$5 .$	$\vec{G_{i}}+\|\{\mathcal{R}_{i}\}\|\cdot\vec{E}\rightarrow\vec{G}$	reset	$\vec{F}+\vec{F}_{1}+\ldots+\vec{F}_{\|\Gamma\|}\rightarrow\vec{G}_{i}+\ldots+% \vec{G}_{\|\Gamma\|}$
(a) UI parallel CRN simulating a VG CRN.			(b) $k$ -VG simulating UI parallel CRN.

Lemma 29.

$k$ -VG CRNs can simulate any given UI Parallel CRN.

Construction.

Given a UI parallel CRN $\mathcal{C_{UI}}=(\Lambda,\Gamma)$ , we construct a $k$ -Void-Genesis CRN $\mathcal{C_{KVG}}=((\Lambda^{\prime},\Gamma^{\prime}),Z_{\emptyset})$ as described. Let $\Lambda^{\prime}=\Lambda\cup\{F\}\cup\{G_{i},N_{i},I_{i},F_{i},R_{i}^{j}:i\in% \{1,\dots,|\Gamma|\},j\in\{1,\dots,|\mathcal{R}_{i}|\}\}\cup\{z_{r_{j}}:r_{j}% \in\mathcal{R}_{i}s.t.1\leq i\leq|\Gamma|\}$ . For each reaction $\mathcal{\gamma}_{i}\in\Gamma$ , a $G_{i}$ species exists which attempts to sequentially consume the reactants of $\mathcal{\gamma}_{i}$ . If this is successful, it is indicated by the production of an $I_{i}$ species. If some reactant is missing, it returns any previously consumed reactants and creates an $N_{i}$ species instead. Both procedures create an $X_{i}$ species, and when a copy of $X_{i}$ exists for each reaction, this indicates a maximal set of simulated reactions has been chosen and the $F$ species is created. The $N_{i}$ or $I_{i}$ species then turn into a $F_{i}$ species, as well as produce the products of $\mathcal{\gamma}_{i}$ if $I_{i}$ was converted. Once a $F_{i}$ species exists for each reaction, they combine to reset the rule selection process by creating all the $G_{i}$ species again. The full reaction set is shown in Table 7 $b$ , and Figure 11 shows an example of a $k$ -VG CRN simulating a UI CRN with $\Lambda=\{a,b\}$ and reaction $a+b\rightarrow b$ .

Figure 11: A rule application in the simulated Unique Instruction CRN

\mathcal{C_{UI}}

and the equivalent rule application sequence in the simulating

k

-void genesis CRN

\mathcal{C_{KVG}}

.

Theorem 30.

The Void Genesis model is equivalent under polynomial simulation to the Unique-Instruction parallel model.

4.7 Register Machine

In this section, we show that Void Genesis CRNs are Turing Universal by constructing a simulation of a standard register machine.

Theorem 31.

$k$ -VG CRNs are Turing Universal.

Proof.

Given a Register Machine (RM) with $s_{1},\ldots,s_{n}$ states–each with either a $inc(r_{l},s_{j})$ or $dec(r_{l},s_{j},s_{k})$ instruction–and $r_{1},\ldots,r_{m}$ registers, we construct the $k$ -VG CRN as follows. Each register and state will be represented by a species, and the instructions will be encoded in the rules. The initial configurations should have one copy of $s_{1}$ (assume $s_{1}$ is the RM’s starting state) and the register species’ counts should be equal to the registers they represent.

Table 8: Rules for a Void Genesis CRN to simulate a given Register Machine.

Instruction	Relevant Rules	Instruction	Relevant Rules
$s_{j}:inc(r_{i},s_{k})$	$\vec{s}_{j}+\vec{r}_{i}\rightarrow\vec{s}_{k}+\vec{r}_{i}+\vec{r}_{i}$	$s_{j}:dec(r_{i},s_{k},s_{l})$	$\vec{s}_{j}+\vec{r}_{i}\rightarrow\vec{s}_{k}$
	$\vec{s}_{j}+\vec{z}_{r_{i}}\rightarrow\vec{s}_{k}+\vec{r}_{i}$		$\vec{s}_{j}+\vec{z}_{r_{i}}\rightarrow\vec{s}_{l}+\vec{z}_{r_{i}}$
			$Z_{\emptyset}(r_{i})=z_{r_{i}}$

Table 8 shows what rules should be made for each state of a given RM. Because $k$ -VG CRNs can simulate any given RM, $k$ -VG CRNs are Turing Universal. $\hfill\blacktriangleleft$

Although it can be inferred from this result and the simulation equivalence results that all the models studied here are Turing Universal, we do not give formal proofs of this due to space.

5 Conclusion

In this paper, we demonstrate equivalence through polynomial simulation between 5 natural extensions to the CRN model. We centralize these simulations around the Void Genesis CRN model, as this model’s ability to detect zero is one of the simplest augmentations to a regular CRN. We then show that Void Genesis CRNs are Turing Universal, implying that Step-Cycle CRNs, Inhibitory CRNs, Parallel CRNs, and Coarse-Rate CRNs are also Turing Universal. While this work is complete in proving equivalence between these models, there are still several interesting open problems to consider (some of which are shown in Figure 1):

$\blacksquare$

We aim to explore constrained versions of our simulation definition that recover existing notions as special cases. Does restricting the configuration map to be consistent with an underlying species-species mapping immediately results in weak bisimulation? If that underlying map is a total bijective function, does that yield strong bisimulation?
$\blacksquare$

For iCRNs, a rule is inhibited by the existence of one or more species. Our definition effectively uses a logical OR (inhibition is only false when all inhibitor counts are zero). A natural extension is to consider inhibition functions using other logic (e.g., AND – a reaction is inhibited only when all of its inhibitors are present).
$\blacksquare$

Coarse-Rate CRNs are limited to 2 ranks for reactions. A natural generalization of this model is to allow for $k$ different ranks ( $k$ -rate CRNs). What is the relationship between Coarse-Rate CRNs and $k$ -rate CRNs?
$\blacksquare$

Even when limited to only void reactions (rules where no species are created), step CRNs are able to compute threshold circuits [2, 3]. Does this suggest that Step-Cycle CRNs, even when limited to only void reactions (void Step-Cycle), are still Turing Universal?
$\blacksquare$

Are there more efficient ways to simulate these augmented CRNs using VG CRNs?
$\blacksquare$

What is the complexity of reachability in restricted instances of each model, such as [13, 14]? As mentioned, we know the complexity with step-cycles [20], but deletion-only rules have not been explored in detail in the other models.

References

[1] Tilak Agerwala. Complete model for representing the coordination of asynchronous processes. Technical report, Johns Hopkins Univ., Baltimore, Md.(USA), 1974.
[2] Rachel Anderson, Alberto Avila, Bin Fu, Timothy Gomez, Elise Grizzell, Aiden Massie, Gourab Mukhopadhyay, Adrian Salinas, Robert Schweller, Evan Tomai, and Tim Wylie. Computing threshold circuits with void reactions in step chemical reaction networks. In 10th conference on Machines, Computations and Universality, MCU’24, 2024.
[3] Rachel Anderson, Bin Fu, Aiden Massie, Gourab Mukhopadhyay, Adrian Salinas, Robert Schweller, Evan Tomai, and Tim Wylie. Computing threshold circuits with bimolecular void reactions in step chemical reaction networks. In International Conference on Unconventional Computation and Natural Computation, UCNC’24, pages 253–268. Springer, 2024. doi:10.1007/978-3-031-63742-1_18.
[4] Marco Antoniotti, Carla Piazza, Alberto Policriti, Marta Simeoni, and Bud Mishra. Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice. Theoretical Computer Science, 325(1):45–67, 2004. doi:10.1016/J.TCS.2004.03.064.
[5] Rutherford Aris. Prolegomena to the rational analysis of systems of chemical reactions. Archive for Rational Mechanics and Analysis, 19(2):81–99, January 1965. doi:10.1007/BF00282276.
[6] Bernard Berthomieu and Dmitry A. Zaitsev. Sleptsov nets are turing-complete. Theoretical Computer Science, 986:114346, 2024. doi:10.1016/j.tcs.2023.114346.
[7] Kim Calabrese and David Doty. Rate-independent continuous inhibitory chemical reaction networks are turing-universal. In International Conference on Unconventional Computation and Natural Computation, pages 104–118. Springer, 2024. doi:10.1007/978-3-031-63742-1_8.
[8] Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Algorithmic bioprocesses, pages 543–584. Springer, 2009. doi:10.1007/978-3-540-88869-7_27.
[9] Wojciech Czerwiński and Łukasz Orlikowski. Reachability in vector addition systems is ackermann-complete. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1229–1240. IEEE, 2022.
[10] Qing Dong. A bisimulation approach to verification of molecular implementations of formal chemical reaction networks. Master’s thesis, Stony Brook University, 2012.
[11] Javier Esparza and Mogens Nielsen. Decidability issues for petri nets–a survey. arXiv preprint arXiv:2411.01592, 2024. doi:10.48550/arXiv.2411.01592.
[12] Jean-Claude Fernandez. An implementation of an efficient algorithm for bisimulation equivalence. Science of Computer Programming, 13(2-3):219–236, 1990. doi:10.1016/0167-6423(90)90071-K.
[13] Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie. Brief announcement: Reachability in deletion-only chemical reaction networks. In Proc. of the Symposium on Algorithmic Foundations of Dynamic Networks, SAND, 2025.
[14] Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie. Reachability in deletion-only chemical reaction networks. In Proc. of the International Conference on DNA Computing and Molecular Programming, DNA, 2025.
[15] Michel Henri Théodore Hack. Decidability questions for Petri Nets. PhD thesis, Massachusetts Institute of Technology, 1976.
[16] Michel Henri Theódore Hack. Petri net language. Technical report, Massachusetts Institute of Technology, 1976.
[17] Robert Johnson, Qing Dong, and Erik Winfree. Verifying chemical reaction network implementations: a bisimulation approach. Theoretical Computer Science, 765:3–46, 2019. doi:10.1016/J.TCS.2018.01.002.
[18] Richard M Karp and Raymond E Miller. Parallel program schemata: A mathematical model for parallel computation. In 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), pages 55–61. IEEE, 1967. doi:10.1109/FOCS.1967.27.
[19] Jérôme Leroux. The reachability problem for Petri nets is not primitive recursive. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1241–1252. IEEE, 2022.
[20] Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. Polynomial simulations of crn models with trimolecular void step-cycle crns. In Proc. of the 22th International Conference on Unconventional Computing and Natural Computing, UCNC, 2025.
[21] Robin Milner. Communication and concurrency, volume 84. Prentice hall Englewood Cliffs, 1989.
[22] James Lyle Peterson. Petri net theory and the modeling of systems, 1981.
[23] Carl Adam Petri. Communication with automata. PhD thesis, Technische Universitat Darmstadt, 1966.
[24] Phillip Senum and Marc Riedel. Rate-independent constructs for chemical computation. PloS one, 6(6):e21414, 2011.
[25] Adam Shea, Brian Fett, Marc D Riedel, and Keshab Parhi. Writing and compiling code into biochemistry. In Biocomputing 2010, pages 456–464. World Scientific, 2010. URL: http://psb.stanford.edu/psb-online/proceedings/psb10/shea.pdf.
[26] Seung Woo Shin. Compiling and verifying DNA-based chemical reaction network implementations. PhD thesis, California Institute of Technology, 2012.
[27] Seung Woo Shin, Chris Thachuk, and Erik Winfree. Verifying chemical reaction network implementations: a pathway decomposition approach. Theoretical Computer Science, 765:67–96, 2019. doi:10.1016/J.TCS.2017.10.011.
[28] Pamela Bridgers Thomas. Petri net: a modeling tool for the coordination of asynchronous processes. Technical report, Tennessee Univ., Knoxville (USA); Oak Ridge Gaseous Diffusion Plant, Tenn.(USA), 1976.

[bib.bib1] [1] Tilak Agerwala. Complete model for representing the coordination of asynchronous processes. Technical report, Johns Hopkins Univ., Baltimore, Md.(USA), 1974.

[bib.bib2] [2] Rachel Anderson, Alberto Avila, Bin Fu, Timothy Gomez, Elise Grizzell, Aiden Massie, Gourab Mukhopadhyay, Adrian Salinas, Robert Schweller, Evan Tomai, and Tim Wylie. Computing threshold circuits with void reactions in step chemical reaction networks. In 10th conference on Machines, Computations and Universality, MCU’24, 2024.

[bib.bib3] [3] Rachel Anderson, Bin Fu, Aiden Massie, Gourab Mukhopadhyay, Adrian Salinas, Robert Schweller, Evan Tomai, and Tim Wylie. Computing threshold circuits with bimolecular void reactions in step chemical reaction networks. In International Conference on Unconventional Computation and Natural Computation, UCNC’24, pages 253–268. Springer, 2024. doi:10.1007/978-3-031-63742-1_18.

[bib.bib4] [4] Marco Antoniotti, Carla Piazza, Alberto Policriti, Marta Simeoni, and Bud Mishra. Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice. Theoretical Computer Science, 325(1):45–67, 2004. doi:10.1016/J.TCS.2004.03.064.

[bib.bib5] [5] Rutherford Aris. Prolegomena to the rational analysis of systems of chemical reactions. Archive for Rational Mechanics and Analysis, 19(2):81–99, January 1965. doi:10.1007/BF00282276.

[bib.bib6] [6] Bernard Berthomieu and Dmitry A. Zaitsev. Sleptsov nets are turing-complete. Theoretical Computer Science, 986:114346, 2024. doi:10.1016/j.tcs.2023.114346.

[bib.bib7] [7] Kim Calabrese and David Doty. Rate-independent continuous inhibitory chemical reaction networks are turing-universal. In International Conference on Unconventional Computation and Natural Computation, pages 104–118. Springer, 2024. doi:10.1007/978-3-031-63742-1_8.

[bib.bib8] [8] Matthew Cook, David Soloveichik, Erik Winfree, and Jehoshua Bruck. Programmability of chemical reaction networks. In Algorithmic bioprocesses, pages 543–584. Springer, 2009. doi:10.1007/978-3-540-88869-7_27.

[bib.bib9] [9] Wojciech Czerwiński and Łukasz Orlikowski. Reachability in vector addition systems is ackermann-complete. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1229–1240. IEEE, 2022.

[bib.bib10] [10] Qing Dong. A bisimulation approach to verification of molecular implementations of formal chemical reaction networks. Master’s thesis, Stony Brook University, 2012.

[bib.bib11] [11] Javier Esparza and Mogens Nielsen. Decidability issues for petri nets–a survey. arXiv preprint arXiv:2411.01592, 2024. doi:10.48550/arXiv.2411.01592.

[bib.bib12] [12] Jean-Claude Fernandez. An implementation of an efficient algorithm for bisimulation equivalence. Science of Computer Programming, 13(2-3):219–236, 1990. doi:10.1016/0167-6423(90)90071-K.

[bib.bib13] [13] Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie. Brief announcement: Reachability in deletion-only chemical reaction networks. In Proc. of the Symposium on Algorithmic Foundations of Dynamic Networks, SAND, 2025.

[bib.bib14] [14] Bin Fu, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Marco Rodriguez, Adrian Salinas, Robert Schweller, and Tim Wylie. Reachability in deletion-only chemical reaction networks. In Proc. of the International Conference on DNA Computing and Molecular Programming, DNA, 2025.

[bib.bib15] [15] Michel Henri Théodore Hack. Decidability questions for Petri Nets. PhD thesis, Massachusetts Institute of Technology, 1976.

[bib.bib16] [16] Michel Henri Theódore Hack. Petri net language. Technical report, Massachusetts Institute of Technology, 1976.

[bib.bib17] [17] Robert Johnson, Qing Dong, and Erik Winfree. Verifying chemical reaction network implementations: a bisimulation approach. Theoretical Computer Science, 765:3–46, 2019. doi:10.1016/J.TCS.2018.01.002.

[bib.bib18] [18] Richard M Karp and Raymond E Miller. Parallel program schemata: A mathematical model for parallel computation. In 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), pages 55–61. IEEE, 1967. doi:10.1109/FOCS.1967.27.

[bib.bib19] [19] Jérôme Leroux. The reachability problem for Petri nets is not primitive recursive. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1241–1252. IEEE, 2022.

[bib.bib20] [20] Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. Polynomial simulations of crn models with trimolecular void step-cycle crns. In Proc. of the 22th International Conference on Unconventional Computing and Natural Computing, UCNC, 2025.

[bib.bib21] [21] Robin Milner. Communication and concurrency, volume 84. Prentice hall Englewood Cliffs, 1989.

[bib.bib22] [22] James Lyle Peterson. Petri net theory and the modeling of systems, 1981.

[bib.bib23] [23] Carl Adam Petri. Communication with automata. PhD thesis, Technische Universitat Darmstadt, 1966.

[bib.bib24] [24] Phillip Senum and Marc Riedel. Rate-independent constructs for chemical computation. PloS one, 6(6):e21414, 2011.

[bib.bib25] [25] Adam Shea, Brian Fett, Marc D Riedel, and Keshab Parhi. Writing and compiling code into biochemistry. In Biocomputing 2010, pages 456–464. World Scientific, 2010. URL: http://psb.stanford.edu/psb-online/proceedings/psb10/shea.pdf.

[bib.bib26] [26] Seung Woo Shin. Compiling and verifying DNA-based chemical reaction network implementations. PhD thesis, California Institute of Technology, 2012.

[bib.bib27] [27] Seung Woo Shin, Chris Thachuk, and Erik Winfree. Verifying chemical reaction network implementations: a pathway decomposition approach. Theoretical Computer Science, 765:67–96, 2019. doi:10.1016/J.TCS.2017.10.011.

[bib.bib28] [28] Pamela Bridgers Thomas. Petri net: a modeling tool for the coordination of asynchronous processes. Technical report, Tennessee Univ., Knoxville (USA); Oak Ridge Gaseous Diffusion Plant, Tenn.(USA), 1976.

Polynomial Equivalence of Extended Chemical Reaction Models

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Background.

Our Contributions.

Organization.

2 Preliminaries

2.1 Models

2.1.1 Chemical Reaction Networks

Definition 1 (Discrete Chemical Reaction Network).

Definition 2 (Basic CRN Dynamics).

2.1.2 Void Genesis CRNs

Definition 3 (Void-Genesis Dynamics).

2.1.3 Inhibitory CRNs

Definition 4 (Inhibitory Dynamics).

2.1.4 Coarse-Rate CRNs

Definition 5 (Coarse-Rate Dynamics).

2.1.5 Step-Cycle CRNs

Definition 6 (Step-Cycle Dynamics).

2.1.6 Unique Instruction Parallel CRNs

Definition 7 (Plausibly Parallel Rules).

Definition 8 (Unique-Instruction Plausibly Parallel).

Definition 9 (Unique-Instruction Parallel Dynamics).

2.2 Simulation

Simulation Definition.

Intuition.

Definition 10 (It Follows).

Definition 11 (Models).

Definition 12 (Simulation).

Polynomial Simulation.

Theorem 13 (Transitivity).

Proof.

𝑻𝟏 follows 𝑻𝟑.

𝑻𝟑 models 𝑻𝟏.

Polynomial Simulation.

3 Detecting Zero: Examples in Each Model

Void Genesis.

Inhibitory CRNs.

Course-Rate CRNs.

Step-Cycle CRNs.

Unique-Instruction Parallel CRNs.

4 Equivalence

4.1 Equivalence Preliminaries

4.1.1 𝒌-Void Genesis

Definition 14 (k-Void-Genesis Dynamics).

4.1.2 Notation and Techniques

Notation.

Sequential Reactants.

Sequential Products.

4.2 𝒌-Void Genesis equivalence with Void Genesis

Lemma 15.

Construction.

Lemma 16.

Construction.

Theorem 17.

4.3 Inhibitory CRNs

Lemma 18.

Construction.

Lemma 19.

Construction.

Theorem 20.

4.4 Coarse-Rate CRNs

Lemma 21.

Construction.

Lemma 22.

Construction.

Theorem 23.

4.5 Step-Cycle CRNs

Lemma 24.

Construction.

Lemma 25.

$T_{1}$ follows $T_{3}$ .

$T_{3}$ models $T_{1}$ .

4.1.1 $𝒌$ -Void Genesis

Definition 14 ( $k$ -Void-Genesis Dynamics).

4.2 $𝒌$ -Void Genesis equivalence with Void Genesis