$\\{R^{*}(\alpha^{\prime}):\alpha\in\mathcal{A}_{*}(\Gamma^{\prime})\\}=\mathcal{A}_{*}(\Gamma)$.

##  8 Simulation between amoebot and clockwise sCRN

In this section, we show that clockwise sCRN and amoebot can simulate each
other. The simulation for amoebot by clockwise sCRN is given in Section 8.1,
and the simulation for clockwise sCRN by amoebot is given in Section 8.2

###  8.1 Simulating amoebot by clockwise sCRN

###### Theorem 8.1

Given an amoebot system $\Gamma=(Q,S,\delta)$, there exists a clockwise sCRN
$\Gamma^{\prime}=(Q^{\prime},S^{\prime},R^{\prime})$ which simulates $\Gamma$.

####  8.1.1 Simulation overview

In the amoebot model, a particle performs state transitions and movements
according to the flags placed by its neighbors, and it occupies two cells at a
time if it is expanded. Therefore, the corresponding sCRN must have pairs of
species that encode the same expanded particle, observe all the flags, and
simulate all possible types of movement. Notice that an algorithm for the
amoebot system may result in different, asymmetric configurations for
clockwise and counterclockwise chirality, so it is necessary to use a sCRN
with knowledge of the correct chirality (clockwise here). This could be
accomplished by providing the surface with a predefined coloring at the
beginning, or just using a clockwise sCRN. We now assume that
$\Gamma^{\prime}$ is given an initial pattern as in $\Gamma$. Recall that
$Q=\Phi\times\mathcal{O}\times D\times\Sigma^{10}$. The following are two
steps to construct the simulation:

  * •

First, we construct a set of states
$Q^{*}=\Phi\times\mathcal{O}\times\mathcal{H}\times\Sigma^{10}\times(\mathcal{O}\cup\\{\varepsilon\\})$
that can be used to encode each particle in $\Gamma$.

  * •

With $Q^{*}$, we can construct the corresponding reactions $R^{\prime}$ and
state set $Q^{\prime}$ in $\Gamma^{\prime}$ more easily.

We use a single species to represent a contracted particle, which is called
the _contracted species_. A pair of _expanded species_ consists of one _tail
species_ and one _head species_ , and they together represent an expanded
particle. Recall that expansion preserves local orientation; we observe that
each expanded particle can be classified into $6$ _types_ , depending on which
direction of cell a contracted particle expanded into when creating the
expanded particle. More details are given in Section 8.1.2.

To simulate a transition rule in the amoebot model, the corresponding species
in sCRN must first observe all its neighbors’ flags and then perform the
corresponding movement. For the observation part, we mainly follow the
designing idea in the simulation of cellular automata, which is stated in
Section 7.1. We’ll briefly describe when to lock or unlock the neighbors and
when to enter the pause state for each movement in Section 8.1.3. For the
second part, if the movement is idle, it is just state transition and the
simulation is straightforward. The protocol is given in Idle. For
$\textsf{expand}_{i}$, it can be simulated by having a contracted species
react with a blank species $\mathcal{O}$ in the $i$ direction, placing the
flags in each direction carefully. The protocol is given in Expansion. We
simulate contraction by having a pair of expanded species perform reactions
with each other, after which one of them is turned into the blank species
$\mathcal{O}$, and the other becomes the contracted species. The contracting
process is given in Contraction. For $\textsf{handover}_{i}$, we simulate by
slightly modifying the contraction and expansion protocols so that the
contracted species can remember which cells it pushes in a pair of expanded
species. After contracting out of that cell, the expanded species can tell the
contracted species to expand into it. We define the _switching cell_ to be the
one occupying by different particles before and after the handover operation.
In the simulation, the contracted species first transforms the switching cell,
say $v_{s}$, to a _prepare species_ and turns itself into a _pushing species_.
This makes the pair of expanded species contract out of $v_{s}$, leaving
$v_{s}$ with a _waiting species_ which waits for the expansion of the locked
contracted species. Details are provided in protocol Handover. These movements
are simulated in Section 8.1.4. The correctness proof is given in Section
8.1.5.

####  8.1.2 Encoding particles

Here we explain how to represent a particle in $Q$ by species in $Q^{*}$. The
labels $f_{0},\cdots,f_{9}$ are directly copied from the original particle, so
the contracted particles have $f_{6}=\cdots=f_{9}=\varepsilon$.
$\mathcal{H}=\\{H,T,\varepsilon\\}$ indicates whether head or tail the species
is, where $\varepsilon$ means that it is a contracted species. Recall that in
the amoebot system, the initial configuration consists of contracted
particles, so each expanded particle is created by some contracted particle
performing $\textsf{expand}_{i}$, $i\in\mathcal{O}$. The last variable
indicate this $i$, and a contracted species always has a $\varepsilon$ there.

We map a contracted particle
$\rho_{C}=(\phi,o,\varepsilon,f_{0},\cdots,f_{5},\varepsilon,\varepsilon,\varepsilon,\varepsilon)$
to a contracted species
$\psi_{C}=(\phi,o,\varepsilon,f_{0},\cdots,f_{5},\varepsilon,\varepsilon,\varepsilon,\varepsilon,\varepsilon)\in
Q^{*}$ naively. And each expanded particle
$\rho_{E}=(\phi,o,d,f_{0},\cdots,f_{9})$ is mapped to a pair of _type- $i$
species_

$(\psi_{T},\psi_{H})=\left((\phi,o,T,f_{0},\cdots,f_{9},i),(\phi,o,H,f_{0},\cdots,f_{9},i)\right)\text{
for some }i\in\mathcal{O}.$

We call $\psi_{T}$ the tail species, $\psi_{H}$ the head species, and we also
call the corresponding expanded particle the _type- $i$ particle_. Notice that
once $i$ and $h\in\mathcal{H}$ are given, the tail direction $d$ is determined
as well. See Figure 7 for an example of type-$0$ and type-$4$ species. The
light gray circle represents the tail, and the dark gray circle represents the
head. The one with an orange frame means that its local $0$ fits the local $0$
of the expanded particle. Such a mapping from $Q$ to $Q^{*}\cup(Q^{*})^{2}$ is
denoted as $F$, where $F(\rho_{C})=\psi_{C}$,
$F(\rho_{E})=(\psi_{T},\psi_{E})$.

(a) Type $0$.

(b) Type $4$.

Figure 7: Types of expanded species representing expanded particles

####  8.1.3 Observing flags

Here we explain how to adapt the idea in Section 7.1 to fit the purpose of
observing all the flags around a particle. Similarly, a release species can
only unlock its neighbors, and a paused species cannot lock any other species.
We allow a species to lock others only if it has not been locked by anyone
else, and most of the locks can be cancelled unconditionally except for some
cases we’ll specify in the following description.

For a contracted species $\psi_{C}$, it keeps locking and observing its
neighbors.

  * •

If all its neighbors have been locked, $\psi_{C}$ can perform idle. Note that
if no state transition is needed to be performed at this point, $\psi_{C}$
turns itself into the paused release state.

  * •

If the neighbor in direction $i$ is not locked by any other species, and the
rest of its neighbors have all been locked by $\psi_{C}$, it can perform
either an expansion or a handover toward direction $i\in\mathcal{O}$.

    * –

If an expansion is performed, the expanded species are produced in the release
state.

    * –

If a handover is performed, a pushing species and a prepare species appear
first. A pushing species cannot unlock any neighbors, and the prepare species
cannot lock the pushing species or its partner in the expanded species. Then
the expanded species contract out of the prepare species as long as all the
other neighbors have been locked. This results in a contracted species and a
waiting species, where the contracted one is produced in the release state,
and the waiting species cannot unlock any species. The last step is to let the
pushing species and waiting species simulate the expansion, and both of them
become a release state at the same time.

For a pair of expanded species $\psi_{E}$, they keep locking and observing all
their neighbors except for each other, once the neighbors around them are all
locked, they can either idle or perform a contraction.

  * •

If the movement is idle and there is no state transition needed to be
performed, then the species turn themselves into the paused release state.

  * •

If the movement is a contraction, then both the contracted species and blank
species resulting from the contraction are produced in the release state.

Following the design when simulating cellular automata, a paused species
leaves the pause state if any of its neighbors changes, which includes turning
into a pushing, prepare, or waiting species. The process described in this
section is similar to the one in Section 7.1, so we separate it from the
simulation of movements, and we are not giving the technical details or the
sketch of proof of this part in this paper. Further, we assume from now on,
every species knows all the flags facing it at any point.

####  8.1.4 Movements

The goal now remains to simulate any legal movement in $\Gamma$. See Figure 8
for some examples of these operations.

Figure 8: Examples of movements

##### Idle

It is just a state transition. Assume that a contracted particle $\rho_{C}$
becomes $\rho^{\prime}_{C}$ by performing idle, and that
$\psi_{C}=F(\rho_{C})$, $\psi^{\prime}_{C}=F(\rho^{\prime}_{C})$, we add the
unimolecular reaction $(\psi_{C},\psi^{\prime}_{C},\odot)$ to $R^{\prime}$.
For an expanded particle $\rho_{E}$ that becomes $\rho^{\prime}_{E}$, assume
that $(\psi_{T},\psi_{H})=F(\rho_{E})$ and
$(\psi^{\prime}_{T},\psi^{\prime}_{H})=F(\rho^{\prime}_{E})$, we add the
bimolecular reaction
$(\psi_{T},\psi_{H},\psi^{\prime}_{T},\psi^{\prime}_{H},k)$ to $R^{\prime}$
where $k$ is the type of $\rho_{E}$.

##### Expansion

To simulate a contacted particle $\rho_{C}\in Q$ that expands toward direction
$i$ and becomes an expanded particle $\rho_{E}\in Q$, assuming that
$\psi_{C}=F(\rho_{C})$ and $(\psi_{T},\psi_{H})=F(\rho_{E})$, we add
$(\psi_{C},\mathcal{O},\psi_{T},\psi_{H},i)$ to $R^{\prime}$.

##### Contraction

To simulate a type-$k$ particle performing $\textsf{contract}_{i}$, we first
see whether it is contracting into the head or the tail.

  * •

When $(k,i)\in C_{T}=\\{(0,5),(1,6),(2,9),(3,0),(4,1),(5,4)\\}$, a type-$k$
particle performing $\textsf{contract}_{i}$ is actually contracting into the
tail.

  * •

When $(k,i)\in C_{H}=\\{(0,0),(1,1),(2,4),(3,5),(4,6),(5,9)\\}$, a type-$k$
particle performing $\textsf{contract}_{i}$ is actually contracting into the
head.

Therefore, given an expanded particle $\rho_{E}\in Q$ which is contracting
toward direction $i$ and is turning into a contracted particle $\rho_{C}\in
Q$, we have the following reactions in $R^{\prime}$ assuming
$\psi_{C}=F(\rho_{C})$ and $(\psi_{T},\psi_{H})=F(\rho_{E})$:

$\displaystyle(\psi_{T},\psi_{H},\psi_{C},\mathcal{O},k),\text{ for all
}(k,i)\in C_{T}.$
$\displaystyle(\psi_{T},\psi_{H},\mathcal{O},\psi_{C},k),\text{ for all
}(k,i)\in C_{H}.$

##### Handover

A handover is equivalent to a contraction and an expansion happening
simultaneously. In particular, we view $\textsf{handover}_{i}$ as
$(\textsf{expand}_{i},\textsf{contract}_{j})$ performing on a pair of adjacent
particles. In the sCRN, it is impossible to change the states of three cells
at the same time, so we use an additional variable
$l\in\mathcal{O}\cup\\{\varepsilon,w\\}$ to ensure that the corresponding
contraction and expansion both happen eventually. If $l\in\mathcal{O}$, this
means a pushing species intending to push a tail or head species toward the
$l$ direction, otherwise, $l=\varepsilon$ represents a prepare species being
pushed by a pushing species. When the expanded species has contracted out of
the switching cell, $l$ is set to be $w$ that stands for the waiting species.

Assume that it is a contracted particle $\rho_{C}$ pushing an expanded
type-$k$ particle $\rho_{E}$ toward direction $i$, and they become
$\rho^{\prime}_{E}$ and $\rho^{\prime}_{C}$ eventually. Let
$F(\rho_{C})=\psi_{C}$, $F(\rho^{\prime}_{C})=\psi^{\prime}_{C}$,
$F(\rho_{E})=(\psi_{T},\psi_{H})$, and
$F(\rho^{\prime}_{E})=(\psi^{\prime}_{T},\psi^{\prime}_{H})$. We describe the
simulation protocol by the following three parts:

  1. 1.

We have $\rho_{C}$ remember $i$, the direction of the switching cell it is
pushing. Let the species located in the switching cell be $\psi_{h}$ for some
$h\in{H,T}$ ($h$ is fixed given $(k,j)$), then we have $\psi_{C}$ become a
pushing species and $\psi_{h}$ become a prepare species
$(\psi_{h},\varepsilon)$. At this point, $(\psi_{C},i)$ and
$(\psi_{h},\varepsilon)$ temporarily “tie” each other. We add the following
reaction to $R^{\prime}$:

$\displaystyle(\psi_{C},\psi_{H},(\psi_{C},i),(\psi_{H},\varepsilon)),\text{
for }(k,j)\in C_{T}.$
$\displaystyle(\psi_{C},\psi_{T},(\psi_{C},i),(\psi_{T},\varepsilon)),\text{
for }(k,j)\in C_{H}.$

At the same time there may be another contracted particle pushing $\rho_{E}$,
but these two pushes cannot be performed simultaneously. To avoid this
situation we also add the reverse reactions
$(\psi_{C},\psi_{h},(\psi_{C},i),(\psi_{h},\varepsilon))^{-1}$ to
$R^{\prime}$.

  2. 2.

After the prepare species $\psi_{h}$ appears within the expanded species, the
expanded species contracts out of $\psi_{h}$, and leaves a mark $W$ on
$\psi_{h}$, which serves as a signal that tells $(\psi_{C},i)$ to perform the
expansion. Suppose that $\rho_{E}$ is a type-$k$ particle, we add the
following reactions to $R^{\prime}$:

$\displaystyle(\psi_{T},(\psi_{H},\varepsilon),\psi^{\prime}_{C},(\psi_{H},w),k),\text{
for }(k,j)\in C_{T}.$
$\displaystyle((\psi_{T},\varepsilon),\psi_{H},(\psi_{T},w),\psi^{\prime}_{C},k),\text{
for }(k,j)\in C_{H}.$

Note that $k$ is known given $\rho_{E}$, which, together with $j$ determines
whether head or tail it is contracting into.

  3. 3.

After $(\psi_{C},i)$ observes its neighbor in direction $i$ becoming
$(\psi_{h},w)$, it complete the expanding process. So we add the following
reaction to $R^{\prime}$:

$\displaystyle((\psi_{C},i),(\psi_{h},w),\psi^{\prime}_{T},\psi^{\prime}_{H},i).$

We summarize the simulation of all the movements in the following protocol.

##### Simulate_Movements_by_c-sCRN

For any transition define by $\delta$, we simulate it according to the
movement being performed. For all contracted particles
$\rho_{C},\rho^{\prime}_{C}\in Q$, expanded type-$k$ particles
$\rho_{E},\rho^{\prime}_{E}\in Q$, a vector of flags
$\vec{f^{\prime\prime}}=(f^{\prime\prime}_{0},\cdots,f^{\prime\prime}_{9})$
around the particle that is about to move, we assume that
$F(\rho_{C})=\psi_{C}$, $F(\rho^{\prime}_{C})=\psi^{\prime}_{C}$,
$F(\rho_{E})=(\psi_{T},\psi_{H})$, and
$F(\rho^{\prime}_{E})=(\psi^{\prime}_{T},\psi^{\prime}_{H})$. For simplicity,
let $\delta(\cdot)=\delta(\cdot,\vec{f^{\prime\prime}})$. Add the following
reactions to $R^{\prime}$:

  1. 1.

$(\psi_{C},\psi^{\prime}_{C},\odot)$, if
$(\rho^{\prime}_{C},\textsf{idle})=\delta(\rho_{C})$.
$(\psi_{T},\psi_{H},\psi^{\prime}_{T},\psi^{\prime}_{H},k)$, if
$(\rho^{\prime}_{E},\textsf{idle})=\delta(\rho_{E})$. $\triangleright$ Idle.

  2. 2.

$(\psi_{C},\mathcal{O},\psi_{T},\psi_{H},i)$, if
$(\rho_{E},\textsf{expand}_{i})=\delta(\rho_{C})$ for some
$i\in\\{0,\cdots,5\\}$. $\triangleright$ Expansion.

  3. 3.

$(\psi_{T},\psi_{H},\psi_{C},\mathcal{O},k)$, if
$(\rho_{C},\textsf{contract}_{i})=\delta(\rho_{E})$ and $(k,i)\in C_{T}$.
$\triangleright$ Contract into tail.
$(\psi_{T},\psi_{H},\mathcal{O},\psi_{C},k)$, if
$(\rho_{C},\textsf{contract}_{i})=\delta(\rho_{E})$ and $(k,i)\in C_{H}$.
$\triangleright$ Contract into head.

  4. 4.

If $(\hat{\rho}_{C},\textsf{handover}_{i})=\delta(\rho_{C})$ s.t.
$\hat{\rho}_{C}$ puts the information on its flags that makes $\rho_{C}$
expand along direction $i$ and become $(\rho^{\prime}_{E})$, and makes
$\rho_{E}$ contract toward direction $j$ and change to $\rho^{\prime}_{C}$,
then we add the following reactions to $R^{\prime}$:

$(\psi_{C},\psi_{H},(\psi_{C},i),(\psi_{H},\varepsilon))$,
$(\psi_{C},\psi_{H},(\psi_{C},i),(\psi_{H},\varepsilon))^{-1}$, for $(k,j)\in
C_{T}$.
$(\psi_{C},\psi_{T},(\psi_{C},i),(\psi_{T},\varepsilon))$,
$(\psi_{C},\psi_{T},(\psi_{C},i),(\psi_{T},\varepsilon))^{-1}$, for $(k,j)\in
C_{H}$.
$(\psi_{T},(\psi_{H},\varepsilon),\psi^{\prime}_{C},(\psi_{H},w),k)$, for
$(k,j)\in C_{T}$.
$((\psi_{T},\varepsilon),\psi_{H},(\psi_{T},w),\psi^{\prime}_{C},k)$, for
$(k,j)\in C_{H}$.
$((\psi_{C},i),(\psi_{h},w),\psi^{\prime}_{T},\psi^{\prime}_{H},i)$, for
$h\in\\{T,H\\}$. $\triangleright$ Handover

####  8.1.5 Proof sketch

First we define the representation function. For any contracted species, it is
mapped to the contracted particle it represents, so
$R(\psi_{C})=F^{-1}(\psi_{C})$ for all $\psi_{C}\in\\{\text{contracted
species}\\}$. For tail and head species in a type-$i$ T-H pair s.t.
$F(\rho_{E})=(\psi_{T},\psi_{H})$ for some expanded particle $\rho_{E}$, let
$R(\psi_{T})=R(\psi_{H})=\rho_{E}$. This is well-defined since we can decode
$\rho_{E}$ by any one of the $\psi_{T}$ and $\psi_{H}$. For the remaining
species, let $R(\mathcal{O})=\textsf{null}$, and
$R((\psi,l))=R((\psi,\varepsilon))=R((\psi,w))=\textsf{UND}\ \forall
l\in\mathcal{O}$. The contraction, expansion, or handover, toward each
direction, corresponds one-to-one to a protocol in Section 8.1.4.

##### $\Gamma\dashv_{R}\Gamma^{\prime}$

For any $\alpha^{\prime}\rightarrow\beta^{\prime}$, it is a sequence consists
of contraction, expansion, or a reaction in the sub-protocol simulating
handover. If it was the last case, the configuration produced by one step of
reaction is not mapped to UND only if it performs item $3$ in protocol
Handover, which means that a handover has complete. Therefore, if
$R^{*}(\alpha^{\prime}),R^{*}(\beta^{\prime})\neq\textsf{UND}$, then
$R^{*}(\alpha^{\prime})\rightarrow R^{*}(\beta^{\prime})$ since it can be
achieved by a sequence of movements.

##### $\Gamma^{\prime}\models_{R}\Gamma$

For any $\alpha\in\mathcal{A}(\Gamma)$, let $\Pi=\\{\alpha\\}$. $\alpha$ is
achievable by simulating the movements one by one according to each sub-
protocol. Notice that for any $\alpha^{\prime\prime}$ s.t.
$R^{*}(\alpha^{\prime\prime})=\alpha$, there cannot be any prepare species or
waiting species in $\alpha^{\prime\prime}$. So $\alpha^{\prime\prime}$ must be
a configuration s.t. all sequence of reactions that simulate a single movement
is completely performed. Therefore $\alpha\rightarrow\alpha^{\prime\prime}$.

##### $\Gamma\Leftrightarrow_{R}\Gamma^{\prime}$

By the above explanation, it is obvious that
$\\{R^{*}(\alpha^{\prime}):\alpha\in\mathcal{A}(\Gamma^{\prime})\\}=\mathcal{A}(\Gamma)\cup\\{\textsf{UND}\\}$.
Notice that the ability of performing a movement in $\Gamma$ is equivalent to
the ability of performing the sub-protocol corresponds to that movement.
(Although in the handover operation there might be more than one contracted
species pushing the same expanded species, item $2$ of protocol Handover are
reversible reactions, so it will be only one species ”accepted” by the
expanded species eventually.) Therefore we have
$\\{R^{*}(\alpha^{\prime}):\alpha\in\mathcal{A}_{*}(\Gamma^{\prime})\\}=\mathcal{A}_{*}(\Gamma)$.

###  8.2 Simulate clockwise sCRN by amoebot

###### Theorem 8.2

Given a clockwise sCRN $\Gamma=(Q,S,R)$ , there exists an amoebot system
$\Gamma^{\prime}=(Q^{\prime},S^{\prime},\delta)$ which simulate $\Gamma$.

####  8.2.1 Simulation overview

We use only contracted particles, and with the property that each particle can
see every neighbors and perform state transition by the information in its
neighborhood, we can use the same technique as the simulation of d-sCRN by
non-deterministic async-CA (Section 7.2). Notice that the underlying lattice
does not matter and we don’t provide the precies protocol here.

## References

  * [1] Adleman, L., Cheng, Q., Goel, A., Huang, M.D.: Running time and program size for self-assembled squares. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. p. 740–748 (2001)
  * [2] Alaniz, R.M., Brunner, J., Coulombe, M., Demaine, E.D., Diomidova, J., Knobel, R., Gomez, T., Grizzell, E., Lynch, J., Rodriguez, A., Schweller, R., Wylie, T.: Complexity of reconfiguration in surface chemical reaction networks (2023)
  * [3] Alaniz, R.M., Caballero, D., Cirlos, S.C., Gomez, T., Grizzell, E., Rodriguez, A., Schweller, R., Tenorio, A., Wylie, T.: Building squares with optimal state complexity in restricted active self-assembly. Journal of Computer and System Sciences 138, 103462 (2023)
  * [4] Alumbaugh, J.C., Daymude, J.J., Demaine, E.D., Patitz, M.J., Richa, A.W.: Simulation of programmable matter systems using active tile-based self-assembly. In: DNA Computing and Molecular Programming. pp. 140–158 (2019)
  * [5] Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst. 3(4) (12 2008). https://doi.org/10.1145/1452001.1452003, https://doi.org/10.1145/1452001.1452003
  * [6] Bhattacharjee, K., Naskar, N., Roy, S., Das, S.: A survey of cellular automata: Types, dynamics, non-uniformity and applications. Natural Computing 19, 433–461 (06 2020)
  * [7] Brailovskaya, T., Gowri, G., Yu, S., Winfree, E.: Reversible computation using swap reactions on a surface. In: DNA Computing and Molecular Programming. pp. 174–196 (2019)
  * [8] Caballero, D., Gomez, T., Schweller, R., Wylie, T.: Verification and computation in restricted tile automata. Natural Computing pp. 1–19 (2021)
  * [9] Chalk, C., Luchsinger, A., Martinez, E., Schweller, R., Winslow, A., Wylie, T.: Freezing simulates non-freezing tile automata. In: DNA Computing and Molecular Programming. pp. 155–172 (2018)
  * [10] Chen, H.L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Natural Computing 13(4), 517–534 (2014)
  * [11] Chen, H.L., Doty, D., Soloveichik, D., Reeves, W.: Rate-independent computation in continuous chemical reaction networks. Journal of the ACM 70(3), 1–61 (2023)
  * [12] Clamons, S., Qian, L., Winfree, E.: Programming and simulating chemical reaction networks on a surface. Journal of The Royal Society Interface 17, 20190790 (2020)
  * [13] Cook, M., Soloveichik, D., Winfree, E., Bruck, J.: Programmability of Chemical Reaction Networks, pp. 543–584. Springer Berlin Heidelberg, Berlin, Heidelberg (2009), https://doi.org/10.1007/978-3-540-88869-7_27
  * [14] Dennunzio, A., Formenti, E., Manzoni, L.: Computing issues of asynchronous ca. Fundam. Inf. 120(2), 165–180 (2012)
  * [15] Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Amoebot - a new model for programmable matter. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures. p. 220–222. SPAA ’14, Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2612669.2612712, https://doi.org/10.1145/2612669.2612712
  * [16] Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 302–310 (2012)
  * [17] Fages, F., Le Guludec, G., Bournez, O., Pouly, A.: Strong turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs. In: Feret, J., Koeppl, H. (eds.) Computational Methods in Systems Biology. pp. 108–127. Springer International Publishing, Cham (2017)
  * [18] Fatès, N., Gerin, L.: Examples of fast and slow convergence of 2d asynchronous cellular systems. In: Cellular Automata. pp. 184–191 (2008)
  * [19] Hader, D., Patitz, M.J.: The impacts of dimensionality, diffusion, and directedness on intrinsic cross-model simulation in tile-based self-assembly (2023)
  * [20] von Neumann, J.: Theory of self-reproducing automata (1966), https://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf
  * [21] Patitz, M.J.: An introduction to tile-based self-assembly. In: Durand-Lose, J., Jonoska, N. (eds.) Unconventional Computation and Natural Computation. pp. 34–62 (2012)
  * [22] Qian, L., Winfree, E.: Parallel and scalable computation and spatial dynamics with dna-based chemical reaction networks on a surface. In: Murata, S., Kobayashi, S. (eds.) DNA Computing and Molecular Programming. pp. 114–131. Springer International Publishing, Cham (2014)
  * [23] Rothemund, P., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the Annual ACM Symposium on Theory of Computing. pp. 459–468 (2000)
  * [24] Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Natural Computing: An International Journal 7(4), 615–633 (dec 2008). https://doi.org/10.1007/s11047-008-9067-y, https://doi.org/10.1007/s11047-008-9067-y
  * [25] Winfree, E.: Algorithmic self-assembly of dna. In: Proceedings of the International Conference on Microtechnologies in Medicine and Biology. pp. 4–4 (2006)