2022

# An algebraic characterization of self-generating chemical reaction networks
using semigroup models

Dimitri Loutchko<EMAIL_ADDRESS>Institute of Industrial
Science, The University of Tokyo, 4-6-1, Komaba, Meguro-ku, 153-8505, Tokyo,
Japan

###### Abstract

The ability of a chemical reaction network to generate itself by catalyzed
reactions from constantly present environmental food sources is considered a
fundamental property in origin-of-life research. Based on Kaufmann’s
autocatalytic sets, Hordijk and Steel have constructed the versatile formalism
of catalytic reaction systems (CRS) to model and to analyze such self-
generating networks, which they named reflexively autocatalytic and food
generated (RAF). Previously, it was established that the subsequent and
simultaenous catalytic functions of the chemicals of a CRS give rise to an
algebraic structure, termed a semigroup model. The semigroup model allows to
naturally consider the function of any subset of chemicals on the whole CRS.
This gives rise to a generative dynamics by iteratively applying the function
of a subset to the externally supplied food set. The fixed point of this
dynamics yields the maximal self-generating set of chemicals. Moreover, the
lattice of all functionally closed self-generating sets of chemicals is
discussed and a structure theorem for this lattice is proven. It is also shown
that a CRS which contains self-generating sets of chemicals cannot be
nilpotent and thus a useful link to the combinatorial theory of finite
semigroups is established. The main technical tool introduced and utilized in
this work is the representation of the semigroup elements as decorated rooted
trees, allowing to translate the generation of chemicals from a given set of
resources into the semigroup language.

###### keywords:

Biochemical reaction networks, Autocatalytic sets, Algebraic models, Finite
semigroups

##  1 Introduction

Questions about the origin of life are as fascinating as they are difficult to
even attempt to answer. There are at least two schools of thought on how to
approach such questions. The first one is to construct minimal models
involving concrete chemicals, best exemplified by the RNA world hypothesis
formulated by Gilbert (1986), Joyce (1989) and many others. The great
advantage of such concrete models is that they can be tested experimentally,
going all the way back to the classical experiments by Miller (1953) and Oró
(1961). However, there can never be certainty about any hypothesized model,
and even the most convincing ones such as the RNA world hypothesis lack
reliable data with regard to their first appearance, cf. Joyce (2002); Penny
(2005). An alternative school of thought is focused on working out the minimal
requirements which any sensible theory of the origin of life should satisfy.
Prominent proponents of this approach are Oparin (1957), Dyson (1999),
Kauffman (1986), and many others. However, already the formulation of a
meaningful theoretical framework is challenging and there have been various
attempts including $(M,R)$-systems by Rosen (1958), hypercycles by Eigen
(1971), autopoetic systems by Varela et al (1974), chemotons by Gánti (1975)
and autocatalytic sets by Kauffman (1986). A common feature that all
frameworks have in common is the importance of autocatalysis and the
occurrence of autocatalytic cycles as discussed in the review by Hordijk and
Steel (2018).

The catalytic reaction system (CRS) formalism by Steel (2000); Hordijk and
Steel (2004) is a versatile framework that, motivated by Kauffman’s
autocatalytic sets, captures the essence of several of the aforementioned
approaches. It has been used to compute thresholds for the occurrence of self-
generating and self-sustaining motives in CRS based on the level of catalysis
by Hordijk et al (2010, 2011, 2012, 2015); Hordijk and Steel (2017, 2018) and
even for the analysis of the metabolic network of E. Coli by Sousa et al
(2015).

In the companion article by Loutchko (2022), it has been shown that CRS have
an algebraic structure that is generated by the simultaneous and subsequent
function of chemicals acting as catalysts on the CRS. It was then shown how a
naturally defined discrete dynamics yields the maximal self-sustaining set of
chemicals for any given CRS and a characterization of the lattice of
functionally closed self-sustaining sets of chemicals was derived. This
article aims to achieve the same for self-generating sets of chemicals, which
is a stricter notion than that of self-sustainment and requires more
mathematical care. In this regard, the main technical contribution of this
article is to construct a representation of the semigroup elements as
decorated rooted trees as they are naturally suited to deal with the
generation of chemicals from a set of externally supplied chemicals.

#### Mathematical outline

The construction of the semigroup models is based on the CRS formalism
introduced by Hordijk and Steel (2004); Hordijk et al (2011). A CRS is given
by the datum of a chemical reaction network, i.e. a finite set of chemicals
$X$ together with a finite set of reactions $R$ where each reaction $r\in R$
is determined by the set of its reactants $\textrm{dom}(r)\subset X$ and
products $\textrm{ran}(r)\subset X$. Additionally, catalysis data is specified
by a set $C\subset X\times R$ meaning that for each $(x,r)\in C$, the reaction
$r$ is catalyzed by the chemical $x$, and a food set $F\subset X$ of
constantly supplied chemicals is given. A CRS is said to be RAF (reflexively
autocatalytic and food-generated) if each chemical in the CRS can be generated
from the food set $F$ by a series of catalyzed reactions. A set of chemicals
is said to be RAF if the CRS supported on it is RAF. The notion of RAF
formalizes self-generating reaction networks in the framework of CRS. Details
on CRS are given in Section 2.1.

In Section 2.2, it is shown that the reactions and the catalytic functions of
chemicals have the structure of a semigroup, which is additionally equipped
with a partial order and an idempotent addition. The semigroup operation
corresponds to subsequent functionality whereas the addition corresponds to
simultaneous application of functions. More precisely, to each reaction $r\in
R$ a function $\phi_{r}$ is assigned as the set-map
$\phi_{r}:\mathfrak{X}\rightarrow\mathfrak{X}$ on the power set
$\mathfrak{X}:=\mathcal{P}(X_{F})$ of non-food chemicals $X_{F}=X\setminus F$.
The function $\phi_{r}$ gives the set of non-food products of $r$ if and only
if the set of non-food reactants of $r$ is contained in its argument. Such
functions have the usual composition given by
${(\phi_{r}\circ\phi_{r^{\prime}})(Y)=\phi_{r}(\phi_{r^{\prime}}(Y))}$ and an
idempotent addition given by
${(\phi_{r}+\phi_{r^{\prime}})(Y)=\phi_{r}(Y)\cup\phi_{r^{\prime}}(Y)}$ for
all $Y\subset X_{F}$ and $r,r^{\prime}\in R$. They generate the semigroup
model

$\displaystyle\mathcal{S}^{R}=\langle\phi_{r}\rangle_{r\in R}.$

To each of the chemicals $x\in X$, a function
$\phi_{x}:\mathfrak{X}\rightarrow\mathfrak{X}$ is assigned by using the
catalysis data:

$\phi_{x}=\sum_{(x,r)\in C}\phi_{r}.$

The functions of the chemicals generate the semigroup model

$\mathcal{S}=\langle\phi_{x}\rangle_{x\in X},$

which is a subsemigroup of $\mathcal{S}^{R}$. The objects $\mathcal{S}^{R}$
and $\mathcal{S}$ are semigroups with respect to both $+$ and $\circ$, hence
they are called semigroup models.

The elements of the semigroup models are partially ordered via $\phi\leq\psi$
iff $\phi(Y)\subset\psi(Y)$ for all $Y\subset X_{F}$. Lemma 2.13 states the
the partial order on the semigroup models, the partial order on
$\mathfrak{X}$, and the two operations $\circ$ and $+$ are all compatible. A
central notion is the function $\Phi_{Y}\in\mathcal{S}$ of a set of non-food
chemicals $Y\subset X_{F}$ which is defined as the unique maximal element of
the subsemigroup

$\displaystyle\mathcal{S}(Y)=\langle\phi_{x}\rangle_{x\in Y\cup F}$

of $\mathcal{S}$. The function $\Phi_{Y}$ captures all catalytic functionality
that can be exerted by $Y$ and the food set on all other chemicals of the CRS.

Section 3 provides more insight into the structure of the semigroup models.
The basis is the definition of a tree algebra $\mathfrak{T}(A)$ with a
decorating algebra $(A,\circ,+)$ as follows: The objects in $\mathfrak{T}(A)$
are rooted trees, whose edge labels are arbitrary elements in $A$. The vertrex
labels are determined by these edge labels: All leaves are labelled by the
multiplicatively neutral element id. At each non-leaf vertex the labels of the
outgoing edges are multiplied with the labels on the respective child vertex
and the sum is taken over all the outgoing edges. This is illustrated in Fig.
1A. The addition of trees is performed by identifying their roots, with
unchanged labels at the edges, as illustrated in Fig. 1B. The multiplication
of trees $T_{1}\circ T_{2}$ is carried out by replacing all leaves of $T_{1}$
with copies of $T_{2}$. Again, all edge labels are unchanged, as illustrated
in Fig. 1C.

Figure 1: An illustration of the algebra of decorated rooted trees. A The edge
labels $a,b,c,d,e\in A$ determine the vertex labels of the two trees $T_{1}$
and $T_{2}$ recursively: the leaves are labelled by the multiplicatively
neutral element and each vertex function is given by the summation of the
labels over all outgoing edges, multiplied with the labels of the vertices at
their heads. All edge and the resulting vertex labels are shown here, whereas
in B,C and D only the labels of the edges and of the root are shown. B
Addition of the two trees $T_{1}$ and $T_{2}$: The roots of both trees are
identified and the labels on all edges of both trees are retained. The vertex
labels are determined as in A. The root label of $T_{1}+T_{2}$ is equal to the
sum of the root labels of $T_{1}$ and $T_{2}$. C Multiplication of two trees
$T_{1}$ and $T_{2}$: Each leaf of $T_{1}$ is replaced with a copy of $T_{2}$.
Thereby, the edge labels from the original trees are retained, which yields
the respective vertex labels. If the right distributivity of the operations
$+$ and $\circ$ holds, then the root label of $T_{1}\circ T_{2}$ is equal to
the concatenation of the root labels of $T_{1}$ and $T_{2}$. D The replacement
of an edge with label $b=b_{1}+b_{2}$ by two edges with labels $b_{1}$ and
$b_{2}$. A copy of the child tree of the original edge is attached to each of
the new edges. If the right distributivity of the operations $+$ and $\circ$
holds, then the root labels of both shown trees are equal.

The tree algebras relevant for semigroup models have their edges labelled by
the generating sets of the respective models, i.e. they are
${\mathfrak{T}:=\mathfrak{T}(\\{\phi_{x}\\}_{x\in X}\cup\\{0\\})}$ and
${\mathfrak{T}^{R}:=\mathfrak{T}(\\{\phi_{r}\\}_{r\in R}\cup\\{0\\})}$. The
main result of the section is Theorem 3.7, which states that there is a
commutative diagram of homomorphisms

${\mathfrak{T}}$${\mathcal{S}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}}$${\mathfrak{T}^{R}}$${\mathcal{S}^{R}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\},}$$\scriptstyle{ev}$$\scriptstyle{\tau}$$\scriptstyle{\iota}$$\scriptstyle{ev}$

whereby the surjective evaluation map $ev$ sends the root label to the
corresponding semigroup element and the map $\tau$ is defined based on the
formula $\phi_{x}=\sum_{(x,r)\in C}\phi_{r}$. More precisely, $\tau$ replaces
an edge with the label $\phi_{x}$ by edges labeled by $\phi_{r}$ for each
$(x,r)\in C$ and a copy of the child tree of the original edge is attached to
each of the new edges, as illustrated in Fig. 1D. A tree representing a
semigroup element is a lift of the element via the evaluation homomorphism
$ev$. The algebraic reason for the existence of such representations is the
interplay of the two operations $\circ$ and $+$ via the right distributivity
$\phi\circ\chi+\psi\circ\chi=(\phi+\psi)\circ\chi$ for any
$\phi,\psi,\chi\in\mathcal{S}^{R}$.

Loosely speaking, the trees in $\mathfrak{T}^{R}$ correspond to ”reaction
mechanisms”, which proceed recursively from the leaves to the root such that a
reaction labeling an edge occurs subsequently with the ”mechanism” of its head
vertex and such that all reactions labeling edges with same tail are carried
out simultaneously. Thus, it is natural to assume that a chemical $x\in X_{F}$
can be generated from the food set if there is a reaction mechanism for its
generation, given by a tree $T\in\mathfrak{T}^{R}$. This translates to $x\in
ev(T)(\emptyset)$ in this setup. And indeed, it is proven in Lemma 3.12 that
this property is equivalent to the standard definition of generation from the
food set.

In Section 4, it is shown how the representation of semigroup elements by
decorated rooted trees can be used to describe CRS with the RAF property by
the simple condition $\Phi_{X_{F}}(\emptyset)=X_{F}$ (Theorem 4.1). This
implies that for a RAF set of chemicals $X^{\prime}_{F}\subset X_{F}$, the
property $X_{F}^{\prime}\subset\Phi_{X_{F}^{\prime}}(\emptyset)$ holds
(Corollary 4.2) and, moreover, that the equality
$X_{F}^{\prime}=\Phi_{X_{F}^{\prime}}(\emptyset)$ is a sufficient condition
for $X^{\prime}_{F}$ to be a RAF set of chemicals (Proposition 4.3). Then, a
generative dynamics on $\mathfrak{X}$ is defined by
$Y\mapsto\Phi_{Y}(\emptyset)$ and, as one of the main results, it is proven
that the dynamics with initial condition given by $X_{F}$ leads to the maximal
RAF set of chemicals. Finally, new insights and conjectures gained from the
semigroup approach to CRS with the RAF property are discussed. It is shown
that the generative dynamics with the initial condition given by a RAF set of
chemicals $X_{F}^{\prime}$ leads to a fixed point $X_{F}^{\prime*g}$, which
contains $X_{F}^{\prime}$. If $X_{F}^{\prime}\subsetneq X_{F}^{\prime*g}$
holds, then $X_{F}^{\prime}$ is not stable because its own catalytic function
will produce all chemicals in $X_{F}^{\prime*g}$ over time. Therefore
$X_{F}^{\prime*g}$ is termed the functional closure of $X_{F}^{\prime}$. A
characterization of the lattice of all functionally closed RAF sets of a CRS
is provided in Theorem 4.14. It is based on the reduced generative dynamics
given by $Y\mapsto Y\cap\Phi_{Y}(\emptyset)$. This dynamics always has a fixed
point, denoted by $Y_{0}^{*rg}$ for the inital condition $Y_{0}$. For each set
$Y\subset X_{F}$, the set of fixed points

$\displaystyle\mathfrak{N}(Y):=\left\\{(Y\setminus\\{y\\})^{*rg}\textrm{ for
}y\in Y\right\\}$

is introduced and one recursively defines

$\displaystyle\mathfrak{N}^{0}$ $\displaystyle:=\\{X_{F}^{*g}\\}$
$\displaystyle\mathfrak{N}^{i+1}$
$\displaystyle:=\bigcup_{Y\in\mathfrak{N}^{i}}\mathfrak{N}(Y)\textrm{ for all
}i\in\mathbb{Z}_{\geq 0}.$

The statement of the Theorem 4.14 is that the lattice of functionally closed
RAF sets of chemicals is given by

$\mathfrak{N}:=\bigcup_{i=0}^{\mid X_{F}\mid}\mathfrak{N}^{i}.$

In the concluding Section 5, the importance of the representations of
semigroup elements by decorated rooted trees is discussed, and the biochemical
significance of functionally closed RAF sets of chemicals is illustrated. For
example, one would expect chemicals which are uniquely contained in a minimal
functionally closed RAF set of chemicals to be involved solely in the
functionality of the respective RAF set, whereas chemicals that have multiple
minimal functionally closed RAF sets of chemicals containing them are more
likely to be involved in communication and interaction between the respective
RAF sets. This can potentially carry information on the evolutionary role of
the respective chemicals. This is an illustration of how the semigroup models
can be used to discover new concepts in CRS theory. In future work, such
concepts will be applied to CRS corresponding to real biological systems.

##  2 Semigroup models

The construction of semigroup models and their elementary properties are
provided in Section 2.2. They are based on the catalytic reaction system (CRS)
formalism, which is introduced in Section 2.1. This is a condensed version of
the Sections 2. and 3. from the introductory companion article by Loutchko
(2022). Only the RAF property (Definition 2.5) and the extended semigroup
model $\mathcal{S}^{R}$ (Definition 2.10) are newly introduced here.

###  2.1 The CRS formalism

The introduction of the catalytic reaction system (CRS) formalism and of the
reflexievly-autocatalytic and food generated (RAF) property are based on the
work of Hordijk and Steel (2004).

The notion of CRS is designed to capture the catalytic functionality within a
given chemical reaction network. It does not take into account detailed
kinetic or thermodynamic information.

######  Definition 2.1.

A catalytic reaction system (CRS) is a tuple $(X,R,C,F)$ where $X$ is a finite
discrete set of chemicals, $R$ is a finite set of reactions, $C\subset X\times
R$ is the catalysis data for the reactions $R$ and $F\subset X$ is the
constantly present food set.

Each reaction $r\in R$ is given by a pair $(\textrm{dom}(r),\textrm{ran}(r))$
of mutually disjoint subsets of $X$, called the domain and the range of $r$.
The elements of $\textrm{dom}(r)$ are called the reactants and the elements of
$\textrm{ran}(r)$ are the products of $r$. For a pair $(x,r)\in C$, the
reaction $r$ is said to be catalyzed by $x$ and $x$ is said to be a catalyst
of $r$. The food set $F$ is required to satisfy the following closure
property:

  1. (C)

All reactions $r\in R$ with a catalyst in $F$ must involve chemicals outside
of $F$ as reactants, i.e. they must satisfy $\text{dom}(r)\cap(X\setminus
F)\neq\emptyset$.

If $X=F$, the CRS is said to be trivial.

######  Example 2.2.

Fig. 2 shows a representation of a CRS as a directed bipartite graph. This
representation is used throughout this article. The chemicals are represented
by solid vertices and the reactions $r=(\textrm{dom}(r),\textrm{ran}(r))$ are
represented by circles. For each reaction, there are directed edges from each
chemical in $\textrm{dom}(r)$ to the reaction vertex and from the reaction
vertex to each chemical in $\textrm{ran}(r)$. The catalysis data $(x,r)\in C$
is indicated by a dashed directed edge from the chemical $x$ to the reaction
$r$. The food set is indicated by a circle around the food chemicals.

Figure 2: Example of a graphical representation of a CRS. The CRS consists of
five chemicals $X=\\{a,b,c,d,e\\}$ and four reactions $a+b\rightarrow c$,
$c+b\rightarrow d$, $b+d\rightarrow e$ and $c+d\rightarrow e$, which are
catalyzed by $d$, $a$, $e$ and $d$, respectively. The food set is given by
$F=\\{a,b\\}$.

The projection

$\displaystyle\pi_{R}:C\rightarrow R$

yields the set of all catalyzed reactions of the CRS as $\pi_{R}(C)$.

The support of a reaction $r$ is defined as

$\displaystyle\textrm{supp}(r):=\textrm{dom}(r)\cup\textrm{ran}(r)$

and the notions of domain, range, and support extend to sets of reactions
$R^{\prime}\subset R$ via

$\displaystyle\textrm{dom}(R^{\prime})=\bigcup_{r\in
R^{\prime}}\textrm{dom}(r)$

with the analogous definitions for $\textrm{ran}(R^{\prime})$ and
$\textrm{supp}(R^{\prime})$.

From now on, a CRS $(X,R,C,F)$ will be fixed. When referring to any of the
four sets $X,R,C$ or $F$, it is implicitly assumed that they are part of the
full data of the CRS. It will be convenient to abbreviate the non-food
chemicals as

$\displaystyle X_{F}:=X\setminus F$

and to make the same definition for any subset $X^{\prime}$ of $X$ containing
$F$, i.e. $X^{\prime}_{F}:=X^{\prime}\setminus F$. Moreover, given a set
$X^{\prime}_{F}\subset X_{F}$, the symbol $X^{\prime}$ will denote the set
$X^{\prime}_{F}\cup F\subset X$.

######  Definition 2.3.

For a set $X^{\prime}_{F}\subset X_{F}$ of non-food chemicals, define the
restrictions of $R$ and $C$ as

$\displaystyle R\mid_{X^{\prime}}$ $\displaystyle=\\{r\in R\text{ such that
supp}(r)\subset X^{\prime}\\},$ $\displaystyle C\mid_{X^{\prime}}$
$\displaystyle=C\cap(X^{\prime}\times R\mid_{X^{\prime}}).$

The tuple $(X^{\prime},R\mid_{X^{\prime}},C\mid_{X^{\prime}},F)$ is called the
subCRS generated by $X^{\prime}_{F}$.

In the article by Loutchko (2022), a broader notion of subCRS is introduced.
This notion is, however, not needed in this work as the focus will be
exclusively on subCRS generated by sets of non-food chemicals. Note that the
subCRS according to Definition 2.3 is always closed in the terminology used by
Hordijk and Steel (2017), i.e. all reactions of the full CRS with support on
$X^{\prime}$ are actually contained in the respective subCRS.

Now the central notions of food generated CRS and reflexively autocatalytic
and food generated (RAF) CRS are introduced following Hordijk and Steel (2004,
2017). However, the definitions given by Hordijk and Steel (2004, 2017) are
centered around the set of reactions $R$, whereas the definitions given here
involve the whole CRS. In Remark 2.9, the relation to the definitions used in
this work is discussed. The F property formalizes the idea that all chemicals
of the CRS can be generated from the food set. The RAF property means that the
generation from the food set can be achieved with catalyzed reactions only.

######  Definition 2.4.

A CRS $(X,R,C,F)$ has the food generation property (F property) if each $x\in
X_{F}$ is generated by some sequence of reactions from $F$, i.e. if the
following condition is satisfied for each $x\in X_{F}$:

  1. (F)

There exist sets of reactions $R_{1},...,R_{n}\subset R$ with the following
properties:

  1. (F1)

$\textrm{dom}(R_{1})\subset F$.

  2. (F2)

$\textrm{dom}(R_{i+1})\subset\bigcup_{j=1}^{i}\textrm{ran}(R_{j})\cup F$ for
all $1\leq i\leq n-1$.

  3. (F3)

$x\in\textrm{ran}(R_{n})$.

######  Definition 2.5.

A CRS $(X,R,C,F)$ is refelxively autocatalytic and food generated (RAF) if it
is has the F property and if for each chemical $x\in X_{F}$, the sets of
reactions $R_{1},\dots R_{n}\subset R$ featured in the condition (F) can be
chosen to be subsets of $\pi_{R}(C)$. In other words, the reactions in
$R_{1},\dots R_{n}$ are all required to be catalyzed.

######  Remark 2.6.

The notion of self-generation is stronger than the one of self-sustainment.
Self-sustaining CRS are treated within the semigroup formalism by Loutchko
(2022). Self-sustainment requires the CRS to have a catalyzed set of reactions
$R^{\prime}\subset\pi_{R}(C)$ such that
$\textrm{dom}(R^{\prime})\subset\textrm{ran}(R^{\prime})\cup F$ and
$X_{F}\subset\textrm{ran}(R^{\prime})$. The RAF condition is stronger than
this, because one can set $R^{\prime}_{x}:=\cup_{i=1}^{n}R_{n}$ for the
reactions featured in condition (F) and $R^{\prime}=\cup_{x\in
X_{F}}R^{\prime}_{x}$ will satisfy the requirement for self-sustainment. On
the contrary, there are self-sustaining CRS which are not self-generating.

The definition of the RAF property descends to sets of non-food chemicals
$X^{\prime}_{F}\subset X_{F}$ based on the Definition 2.3.

######  Definition 2.7.

A set of chemicals $X^{\prime}_{F}\subset X_{F}$ is said to be a RAF set of
chemicals if the subCRS $(X^{\prime},R\mid_{X^{\prime}},C\mid_{X^{\prime}},F)$
generated by it is RAF.

######  Example 2.8.

The CRS in Fig. 2 is RAF and thus $X_{F}=\\{c,d,e\\}$ is a RAF set of
chemicals. Moreover, there is a RAF subset of chemicals consisting of
$X_{F}^{\prime}=\\{c,d\\}$, because $d$ catalyzes the formation of $c$ from
the food set and $c$ reacts with the food set to form $d$, which is catalyzed
by the food set.

######  Remark 2.9 (Relation to the notion of RAF commonly used in the
literature).

The Definition 2.4 of the F property given here coincides verbatim with the
one commonly used in the CRS literature. The Definition 2.5 of the RAF
property is equivalent to the definitions of a closed111In Hordijk and Steel
(2017), a subset $R^{\prime}\subset R$ is called a closed RAF set of reactions
if it is RAF and if, in addition, all reactions with a catalyst and support in
$\textrm{supp}(R^{\prime})$ are elements of $R^{\prime}$. RAF set of reactions
given by Hordijk and Steel (2004, 2017) modulo the inclusion of uncatalyzed
reactions in the set of reactions $R$ in the definition given here. Hordijk
and Steel (2004, 2017) define the RAF property for subsets of $R$ as follows:
A subset $R^{\prime}\subset R$ is a RAF set of reactions if it has the F
property222The F property for a set $R^{\prime}\subset R$ means that each
chemical in $\textrm{supp}(R^{\prime})\cap X_{F}$ satisfies the condition (F)
with the $R_{i}$ satisfying $R_{i}\subset R^{\prime}$. and if each reaction
$r\in R^{\prime}$ is catalyzed by a chemical
$x\in\textrm{supp}(R^{\prime})\cup F$. Thus, a subCRS
$(X^{\prime},R\mid_{X^{\prime}},C\mid_{X^{\prime}},F)$ corresponds the RAF set
of reactions $\pi_{R^{\prime}}(C^{\prime})$ and, vice versa, a closed RAF set
of reactions $R^{\prime}$ corresponds to the CRS
$(X^{\prime},R\mid_{X^{\prime}},C\mid_{X^{\prime}},F)$ with
$X^{\prime}:=\textrm{supp}(R^{\prime})$.

One can easily lift the restriction of the RAF sets of reactions being closed
by defining subCRS with sets of chemicals $X^{\prime}$ to allow for arbitrary
sets of reactions $R^{\prime}\subset R\mid_{X^{\prime}}$. This construction is
given by Loutchko (2022).

###  2.2 The semigroup model of a CRS

The chemical reactions of a CRS have a natural algebraic structure given by
the simultaneous and subsequent occurrence of reactions, as well as
combinations thereof. Making this mathematically precise leads to the notion
of an extended semigroup model $\mathcal{S}^{R}$ of a CRS. The function of a
chemical is defined by the simultaneous occurrence of all the reactions it
catalyzes. All combinations of subsequent and simultaneous functions of
chemicals give rise to the semigroup model $\mathcal{S}$ of a CRS. The
construction of the semigroup models is motivated by the work of Rhodes and
Nehaniv (2010) in spirit, but technically the objects constructed here differ
significantly, cf. Loutchko (2022), Remark 3.4.

Throughout this section, let $(X,R,C,F)$ be a CRS. The state of the CRS is
defined by the presence or absence of each of the non-food chemicals, i.e. by
a subset $Y\subset X_{F}$. Therefore, the state space $\mathfrak{X}$ of the
CRS is the power set

$\displaystyle\mathfrak{X}:=\mathcal{P}(X_{F})=\\{0,1\\}^{X_{F}}.$

A reaction $r\in R$ acts on the state space via its function

$\phi_{r}:\mathfrak{X}\rightarrow\mathfrak{X}$

given by

$\displaystyle\phi_{r}(Y)=\begin{cases}\text{ran}(r)\cap X_{F}&\text{if
$\text{dom}(r)\subset Y\cup F$}\\\ \emptyset&\text{else}\end{cases}$ (2.1)

for all $Y\subset X_{F}$. Two maps
$\phi,\psi:\mathfrak{X}\rightarrow\mathfrak{X}$ can be composed via the
addition $+$, which is defined as

$(\phi+\psi)(Y)=\phi(Y)\cup\psi(Y)$ (2.2)

for all $Y\subset X_{F}$. This operation is associative, commutative and
idempotent. Moreover, the multiplication $\circ$ is given by the usual
composition of maps

$(\phi\circ\psi)(Y):=\phi(\psi(Y))$ (2.3)

for all $Y\subset X_{F}$.

Finally, the function $\phi_{x}:\mathfrak{X}\rightarrow\mathfrak{X}$ of a
chemical $x\in X$ is defined as the sum over all reactions catalyzed by it via

$\phi_{x}=\sum_{(x,r)\in C}\phi_{r}.$ (2.4)

Recall that the full transformation semigroup $\mathcal{T}(A)$ of a finite
discrete set $A$ is the set of all maps $\\{f:A\rightarrow A\\}$, where the
semigroup operation $\circ$ is the composition of maps. The semigroup model of
a CRS is a subsemigroup of $\mathcal{T}(\mathfrak{X})$ and is defined as
follows.

######  Definition 2.10.

The semigroup model $\mathcal{S}$ of a CRS is a subsemigroup of
$\mathcal{T}(\mathfrak{X})$ generated by the functions $\\{\phi_{x}\\}_{x\in
X}$ through the operations of addition and composition, i.e. $\mathcal{S}$ is
the smallest subsemigroup of the full transformation semigroup
$\mathcal{T}(\mathfrak{X})$ closed under $\circ$ and $+$ that contains
$\\{\phi_{x}\\}_{x\in X}$ and the zero function, given by $0(Y)=\emptyset$ for
all $Y\subset X_{F}$. It is denoted by

$\mathcal{S}=\langle\phi_{x}\rangle_{x\in X}.$

Analogously, the extended semigroup model of the CRS is generated by the
functions $\phi_{r}$ of all reactions $r\in R$. This model is denoted as

$\mathcal{S}^{R}=\langle\phi_{r}\rangle_{r\in R}.$

As subsemigroups of $\mathcal{T}(\mathfrak{X})$, the semigroups $\mathcal{S}$
and $\mathcal{S}^{R}$ are finite. The objects $\mathcal{S}$ and
$\mathcal{S}^{R}$ are called semigroup models, because they are semigroups
with respect to both operations $\circ$ and $+$. The correct description in
terms of universal algebra is, however, an algebra of type $(2,2,0)$, cf.
Almeida (1995). The semigroup model $\mathcal{S}^{R}$ contains $\mathcal{S}$
as a subalgebra of type $(2,2,0)$ and this will be expressed by saying that
$\mathcal{S}$ is a subsemigroup model of $\mathcal{S}^{R}$.

######  Remark 2.11.

In addition to the two algebraic operations, there is a natural partial order
on $\mathcal{S}^{R}$ and $\mathcal{S}$, given by
$\phi\leq\psi\Leftrightarrow\phi(Y)\subset\psi(Y)\text{ for all $Y\subset
X_{F}$}$ for $\phi,\psi\in\mathcal{S}^{R}$.

There is an important subsemigroup of $\mathcal{S}$ generated by the functions
of chemicals in a given set $X_{F}^{\prime}\subset X_{F}$ together with the
food set:

######  Definition 2.12.

For a subset $X^{\prime}_{F}$ of $X_{F}$, the semigroup model
$\mathcal{S}(X_{F}^{\prime})<\mathcal{S}$ generated by the functions of
$X_{F}^{\prime}$ is defined as

$\mathcal{S}(X^{\prime}_{F})=\langle\phi_{x}\rangle_{x\in X^{\prime}}$

and the function $\Phi_{X_{F}^{\prime}}$ of the set $X_{F}^{\prime}$ is given
by

$\Phi_{X_{F}^{\prime}}=\sum_{\phi\in\mathcal{S}(X_{F}^{\prime})}\phi.$

The semigroup models satisfy the following elementary properties. These
properties follow directly from the definitions. However, if necessary, the
proofs for the respective statements on $\mathcal{S}$ can be found in Loutchko
(2022), Section 3.2., and the proofs for $\mathcal{S}^{R}$ are analogous.

######  Lemma 2.13 (Elementary properties of semigroup models).

  1. (S1)

All elements $\phi\in\mathcal{S}^{R}$ respect the partial order on
$\mathfrak{X}$ given by inclusion of sets, i.e.

$Z\subset Y\subset X_{F}\implies\phi(Z)\subset\phi(Y).$

  2. (S2)

The partial order is compatible with addition and multiplication, i.e. for any
$\phi,\phi^{\prime},\psi,\psi^{\prime}\in\mathcal{S}^{R}$ the following
relations hold

$\displaystyle\phi\leq\psi\textrm{ and }\phi^{\prime}\leq\psi^{\prime}$
$\displaystyle\Rightarrow\phi\circ\phi^{\prime}\leq\psi\circ\psi^{\prime},$
(2.5) $\displaystyle\phi\leq\psi\textrm{ and }\phi^{\prime}\leq\psi^{\prime}$
$\displaystyle\Rightarrow\phi+\phi^{\prime}\leq\psi+\psi^{\prime}.$ (2.6)

  3. (S3)

Any $\phi,\psi\in\mathcal{S}$ satisfy

$\phi\leq\phi+\psi.$

  4. (S4)

Any $\phi,\phi^{\prime},\psi\in\mathcal{S}$ such that $\phi\leq\psi$ and
$\phi^{\prime}\leq\psi$ satisfy

$\phi+\phi^{\prime}\leq\psi.$

  5. (S5)

The operations $\circ$ and $+$ on $\mathcal{S}^{R}$ have the following
distributivity properties:

$\displaystyle\phi\circ\chi+\psi\circ\chi$
$\displaystyle=(\phi+\psi)\circ\chi,$ (2.7)
$\displaystyle\chi\circ\phi+\chi\circ\psi$
$\displaystyle\leq\chi\circ(\phi+\psi)$ (2.8)

hold for any $\phi,\psi,\chi\in\mathcal{S}^{R}$.

  6. (S6)

The right distributivity in Equation (2.7) holds more generally for arbitrary
elements $\phi,\psi,\chi\in\mathcal{T}(\mathfrak{X})$.

  7. (S7)

$\Phi_{X^{\prime}_{F}}$ is the unique maximal element of
$\mathcal{S}(X^{\prime}_{F})$. In particular, $\mathcal{S}$ has a unique
maximal element, given by $\Phi_{X_{F}}$.

  8. (S8)

The functions of sets $X^{\prime\prime}_{F}\subset X^{\prime}_{F}\subset
X_{F}$ satisfy

$\Phi_{X^{\prime\prime}_{F}}\leq\Phi_{X^{\prime}_{F}}.$

######  Remark 2.14.

Any subCRS $(X^{\prime},R\mid_{X^{\prime}},C\mid_{X^{\prime}},F)$ generated by
the set of chemicals $X_{F}^{\prime}$ has a semigroup model given by
Definition 2.10, which will be denoted by
$\mathcal{S}^{\prime}(X^{\prime},R\mid_{X^{\prime}})$. It is a subsemigroup of
the full transformation semigroup $\mathcal{T}(\mathcal{P}(X^{\prime}_{F}))$
on the power set of $X^{\prime}_{F}$. Any element
$\phi\in\mathcal{S}^{\prime}(X^{\prime},R\mid_{X^{\prime}})$ can be extended
to a function $ext(\phi)\in\mathcal{T}(\mathfrak{X})$ via

$ext(\phi)(Y)=\phi(Y\cap X^{\prime}_{F})$

for $Y\subset X_{F}$. By definition, the generators
$\\{\phi^{\prime}_{x}\\}_{x\in
X^{\prime}}\subset\mathcal{T}(\mathcal{P}(X^{\prime}_{F}))$ of
$\mathcal{S}^{\prime}(X^{\prime},R\mid_{X^{\prime}})$ and the generators
$\\{\phi_{x}\\}_{x\in X^{\prime}}\subset\mathcal{T}(\mathfrak{X})$ of
$\mathcal{S}(X^{\prime}_{F})$ satisfy ${ext(\phi^{\prime}_{x})\leq\phi_{x}}$
for all $x\in X^{\prime}$. Together with the property (S2) this yields the
inequality

$\displaystyle ext(\Phi^{\prime}_{X^{\prime}_{F}})\leq\Phi_{X^{\prime}_{F}}$
(2.9)

for the maximal functions $\Phi^{\prime}_{X^{\prime}_{F}}$ and
$\Phi_{X^{\prime}_{F}}$ of
$\mathcal{S}^{\prime}(X^{\prime},R\mid_{X^{\prime}})$ and
$\mathcal{S}(X^{\prime}_{F})$.

This finishes the summary of the elementary properties of the semigroup
models. In the next section, a representation of the semigroup elements, which
is well suited to deal with the condition (F) in food generated CRS, is
constructed.

##  3 Semigroup Models as Decorated Rooted Trees

This section is dedicated to the construction of a representation of elements
of $\mathcal{S}$ as decorated rooted trees. It forms the technical basis for
the proofs in the next section. Albeit the main idea of this section is rather
straightforward, the verification of all the claimed properties requires some
care. Therefore, the reader might prefer to skip this section up until Theorem
3.7 during the first reading.

The general idea developed in this section is as follows: The edges of the
rooted trees are labeled by functions in a subset of the full transformation
semigroup $\mathcal{T}(\mathfrak{X})$. Each vertex is labelled by the sum of
the functions on the outgoing edges multiplied with the functions of the
respective head vertices (Definition 3.1, see Fig. 3 for an illustration).
Moreover, there are operations of addition and multiplication (Definition 3.3
and Fig. 4) on the set of decorated rooted trees that are compatible with the
addition and multiplication of the semigroup elements on the root (Lemma 3.5).
The addition of two trees is performed by identifying their roots, and the
multiplication is given by replacing the leaves of first tree with copies the
second tree. Finally, to establish a relation to the semigroup models
$\mathcal{S}^{R}$ and $\mathcal{S}$, the edge labels are chosen from the
generating sets $\\{\phi_{r}\\}_{r\in R}\cup\\{0\\}$ and $\\{\phi_{x}\\}_{x\in
X}\cup\\{0\\}$, respectively. This idea is also sketched in the mathematical
outline in the introductory Section 1. The main Theorem 3.7 of this section
establishes that both classes of decorated rooted trees are compatible with
the algebraic structure of the semigroup models. The merit of this
construction is that the F and RAF properties of a CRS can be reformulated in
terms of decorated rooted trees and then directly cast into the language of
semigroup models (Lemma 3.12).

The following notations and conventions with regard to rooted trees will be
used. Let $T=(V,E,t)$ be a rooted tree with vertex set $V$, edge set $E\subset
V\times V$ and root $t\in V$. Edges $(v,w)\in E$ are directed from $v$ to $w$.
Here, $v$ is called the tail of $e$ and $w$ is its head. For each vertex $v\in
V$, let $\textrm{ch}(v)\subset V$ denote the set of children of $V$, which is
defined as $\textrm{ch}(v):=\\{w\in V\textrm{ such that }(v,w)\in E\\}$. Also,
denote by $T_{v}$ the subtree of $T$ rooted at the vertex $v$. The level
$\textrm{lv}(v)$ of a vertex $v$ is the length of the path from the root to
$v$ and $\textrm{lv}_{n}(T)\subset V$ denotes the set of all vertices of a
given level $n$. Moreover, the non-standard notation
$\textrm{elv}_{n}(T)\subset E$ denotes the set of edges of level $n$, which
are all the edges whose head vertex has level $n$. The notation
$\mathrm{ht}(T)$ denotes the height of the tree, i.e. the length of the
longest path from the root to a leaf. Finally, $\mathrm{lf}(T)$ is the set of
all leaves of $T$, which is given by $\mathrm{lf}(T):=\\{v\in V\textrm{ such
that }\textrm{ch}(v)=\emptyset\\}$. An edge $(v,w)\in E$ is said to be
terminal if the vertex $w$ is a leaf.

######  Definition 3.1.

For any subset $A\subset\mathcal{T}(\mathfrak{X})$ of the full transformation
semigroup $\mathcal{T}(\mathfrak{X})$, an $A$-decorated rooted tree
$T=(A,V,E,t,\omega_{V},\omega_{E})$ is a finite rooted tree with vertex set
$V$, edge set $E$, a root $t\in V$ and two maps

$\displaystyle\omega_{V}$
$\displaystyle:V\longrightarrow\mathcal{T}(\mathfrak{X})$
$\displaystyle\omega_{E}$ $\displaystyle:E\longrightarrow A,$

where $\omega_{V}$ is recursively given by

$\displaystyle\omega_{V}(v)=\begin{cases}\textrm{id}\mid_{\mathfrak{X}}&\textrm{if
}v\in\textrm{lf}(T)\\\
\sum_{w\in\textrm{ch}(v)}\omega_{E}((v,w))\circ\omega_{V}(w)\qquad&\textrm{else}.\end{cases}$
(3.1)

The addition and multiplication in the definition of $\omega_{V}$ takes place
inside $\mathcal{T}(\mathfrak{X})$ as previously defined (cf. Equations (2.2)
and (2.3)). Fig. 3 illustrates this construction.

Figure 3:  Example of a decorated rooted tree with decorations from the
generating set $A=\\{\phi_{x}\\}_{x\in X_{F}}\cup\\{0\\}$ of a semigroup model
$\mathcal{S}=\langle\phi_{x}\rangle_{x\in
X_{F}}\subset\mathcal{T}(\mathfrak{X})$. The labels of the edges determine the
labels on the vertices recursively: At each vertex, a sum over the labels of
its children, multiplied by the labels on the respective connecting edges, is
taken. The edges are labeled to the left of the respective edge and the
resulting labels of the vertices are on the right of the respective vertex.
The root is labelled by the function
$\phi_{a}\circ(\phi_{d}\circ\phi_{g}+\phi_{e})+\phi_{b}\circ\phi_{f}+\phi_{c}\in\mathcal{S}$.

Decorated rooted trees will be referred to as trees. For the set of edge
labels $A\subset\mathcal{T}(\mathfrak{X})$, denote the set of all
$A$-decorated trees by $\mathfrak{T}(A)$. Also denote the set of all
$A$-decorated trees of height $n$ by $\mathfrak{T}(A)^{n}$ and of height at
most $n$ by $\mathfrak{T}(A)^{\leq n}$. A subtree is defined as follows.

######  Definition 3.2.

A decorated rooted tree
$T^{\prime}=(A,V^{\prime},E^{\prime},t^{\prime},\omega^{\prime}_{V^{\prime}},\omega^{\prime}_{E^{\prime}})\in\mathfrak{T}(A)$
is a subtree of $T=(A,V,E,t,\omega_{V},\omega_{E})\in\mathfrak{T}(A)$ if there
exists an injective map of rooted trees

$g:(V^{\prime},E^{\prime},t^{\prime})\rightarrow(V,E,t),$

which respects the labels on the edges, i.e.

$\omega^{\prime}_{E^{\prime}}(e^{\prime})=\omega_{E}(g(e^{\prime}))$

holds for all $e^{\prime}\in E^{\prime}$.

The set $\mathfrak{T}(A)$ is equipped with two operations: Loosely speaking,
given two trees $T_{1},T_{2}\in\mathfrak{T}(A)$, their sum is defined by
identifying the roots of $T_{1}$ and $T_{2}$ and their product by replacing
each leaf of $T_{1}$ with a copy of $T_{2}$.

######  Definition 3.3.

Let $T_{1},T_{2}\in\mathfrak{T}(A)$ be two $A$-decorated rooted trees given by
the data $T_{1}=(A,V_{1},E_{1},t_{1},\omega_{V1},\omega_{E1})$ and
$T_{2}=(A,V_{2},E_{2},t_{2},\omega_{V2},\omega_{E2})$. Define the tree
$T^{+}:=T_{1}+T_{2}$ with data
$T^{+}=(A,V^{+},E^{+},t^{+},\omega_{V}^{+},\omega_{E}^{+})$ by identifying the
roots of the two trees, i.e. by

$V^{+}:=\faktor{V_{1}\sqcup V_{2}}{t_{1}\sim t_{2}}.$

There is a canonical map

$\epsilon^{+}:(V_{1}\times V_{1})\sqcup(V_{2}\times
V_{2})\hookrightarrow(V_{1}\sqcup V_{2})\times(V_{1}\sqcup
V_{2})\twoheadrightarrow V^{+}\times V^{+}.$

The edge set $E^{+}$ is defined as

$E^{+}:=\epsilon^{+}(E_{1}\sqcup E_{2})$

with the decoration map

$\displaystyle\omega_{E}^{+}(e)=\begin{cases}\omega_{E1}((\epsilon^{+})^{-1}(e))&\textrm{if
}(\epsilon^{+})^{-1}(e)\in E_{1}\\\
\omega_{E2}((\epsilon^{+})^{-1}(e))&\textrm{if }(\epsilon^{+})^{-1}(e)\in
E_{2}.\end{cases}$ (3.2)

Because the restriction of $\epsilon^{+}$ to $E_{1}\sqcup E_{2}$ is one-to-
one, this map is well-defined. The map $\omega_{V}^{+}$ is given by the
relation (3.1) with $E^{+}$ and $\omega_{E}^{+}$ instead of $E$ and
$\omega_{E}$. The construction is illustrated in Fig. 4A.

Moreover, define the tree $T^{\circ}:=T_{1}\circ T_{2}$ with data
$T^{\circ}=(A,V^{\circ},E^{\circ},t^{\circ},\omega_{V}^{\circ},\omega_{E}^{\circ})$
by replacing each leaf of $T_{1}$ with a copy of $T_{2}$. The data on
$T^{\circ}$ is given as follows.

$V^{\circ}:=\faktor{V_{1}\sqcup\coprod_{l\in\textrm{lf}(T_{1})}V_{2}}{\sim},$

where the equivalence relation $\sim$ relates each leaf
$l\in\textrm{lf}(T_{1})\subset V_{1}$ with the root $t_{2}\in V_{2}$ of the
respective copy of $V_{2}$ indexed by $l$. Again, there is a canonical map

$\epsilon^{\circ}:(V_{1}\times
V_{1})\sqcup\coprod_{l\in\textrm{lf}(T_{1})}(V_{2}\times V_{2})\rightarrow
V^{\circ}\times V^{\circ}$

and the edge set is defined as
$E^{\circ}:=\epsilon^{\circ}(E_{1}\sqcup\coprod_{l\in\textrm{lf}(T_{1})}E_{2})$.
The restriction of $\epsilon^{\circ}$ to
$E_{1}\sqcup\coprod_{l\in\textrm{lf}(T_{1})}E_{2}$ is one-to-one such that
$\omega_{E}^{\circ}$ is defined analogously to $\omega_{E}^{+}$ as in (3.2).
The map $\omega_{V}^{\circ}$ is defined by the relation (3.1) using
$E^{\circ}$ and $\omega_{E}^{\circ}$ instead of $E$ and $\omega_{E}$. This
construction is illustrated in Fig. 4B.

The set $\mathfrak{T}(A)$, together with the two operations $\circ$ and $+$,
is referred to as the tree algebra $\mathfrak{T}(A)$.

Figure 4: A Addition of two trees $T_{1}$ and $T_{2}$: The roots of both trees
are identified and the labels on all edges of both trees are retained. All
vertex labels are given by the relation (3.1). B Multiplication of two trees
$T_{1}$ and $T_{2}$: Each leaf of $T_{1}$ is replaced with a copy of $T_{2}$.
Thereby the edge labels from the original trees are retained, yielding the
vertex labels by relation (3.1). Only the root labels are shown in the figure
(To arrive at the form of the root label of $T_{1}\circ T_{2}$ given here, the
right-distributivity, cf. propery (S6), is used).

######  Remark 3.4.

It follows directly from the definition of the addition and multiplication of
trees that the operations are associative. Moreover, the addition is
commutative and the right distributivity

$(T_{1}+T_{2})\circ T_{3}=T_{1}\circ T_{3}+T_{2}\circ T_{3}$

holds by construction.

The algebraic structure on $\mathfrak{T}(A)$ thus defined is compatible with
the algebraic structure on $\mathcal{T}(\mathfrak{X})$ by mapping a tree
$T\in\mathfrak{T}(A)$ to the label on its root

$\displaystyle\mathfrak{T}(A)$
$\displaystyle\xlongrightarrow{ev}\mathcal{T}(\mathfrak{X})$ (3.3)
$\displaystyle(A,V,E,t,\omega_{V},\omega_{E})$
$\displaystyle\longmapsto\omega_{V}(t).$

######  Lemma 3.5.

The map $ev:\mathfrak{T}(A)\longrightarrow\mathcal{T}(\mathfrak{X})$ is a
homomorphism with respect to addition $+$ and multiplication $\circ$.

Proof: The notation from Definition 3.3 is used. Let
$T_{1},T_{2}\in\mathfrak{T}(A)$ be two $A$-decorated rooted trees.

Let $T^{+}=T_{1}+T_{2}$. By construction of $T^{+}$, the projection
$\pi:V_{1}\sqcup V_{2}\rightarrow V^{+}$ is injective on all vertices except
on the root. Moreover, $\pi$ respects the level of a vertex, i.e.
$\textrm{lv}(v)=\textrm{lv}(\pi(v))$, and the decoration function for vertices
$v$ of level 1 satisfies

$\displaystyle\omega_{V}^{+}(v)=\begin{cases}\omega_{V1}(\pi^{-1}(v))&\textrm{if
}\pi^{-1}(v)\in V_{1}\\\ \omega_{V2}(\pi^{-1}(v))&\textrm{if }\pi^{-1}(v)\in
V_{2}.\end{cases}$

This yields the homomorphism property for addition

$\displaystyle\omega_{V}^{+}(t^{+})$
$\displaystyle=\sum_{v\in\textrm{lv}_{1}(T^{+})}\omega_{E}^{+}((t^{+},v))\circ\omega_{V}^{+}(v)$
$\displaystyle=\sum_{\begin{subarray}{c}v\in\textrm{lv}_{1}(T^{+}),\\\
\pi^{-1}(v)\in
V_{1}\end{subarray}}\omega_{E1}((t_{1},v))\circ\omega_{V1}(\pi^{-1}(v))+$
$\displaystyle+\sum_{\begin{subarray}{c}v\in\textrm{lv}_{1}(T^{+}),\\\
\pi^{-1}(v)\in
V_{2}\end{subarray}}\omega_{E2}((t_{2},v))\circ\omega_{V2}(\pi^{-1}(v))$
$\displaystyle=\omega_{V1}(t_{1})+\omega_{V2}(t_{2}).$

Let $T^{\circ}=T_{1}\circ T_{2}$. By construction, $T_{1}$ is a subtree of
$T^{\circ}$ and thus the respective vertices and edges of $T^{\circ}$ and
$T_{1}$ can be identified. It is now shown inductively that for all $v\in
T_{1}$, considered as a subtree of $T^{\circ}$, the relation

$\omega_{V}^{\circ}(v)=\omega_{V1}(v)\circ\omega_{V2}(t_{2})$ (3.4)

holds. For all leaves $l\in\textrm{lv}(T_{1})$, the relation

$\omega_{V}^{\circ}(l)=\omega_{V2}(t_{2})=\textrm{id}\mid_{\mathfrak{X}}\circ\omega_{V2}(t_{2})=\omega_{V1}(l)\circ\omega_{V2}(t_{2})$

holds by construction. For the induction from vertex level $n$ (with $1\leq
n\leq\textrm{ht}(T_{1})$ to $n-1$, let $v\in V_{1}\setminus\textrm{lf}(T_{1})$
be a vertex of level $n-1$. The recursion (3.1) yields

$\displaystyle\omega^{\circ}_{V}(v)$
$\displaystyle=\sum_{w\in\textrm{ch}(v)\cap
V_{1}}\omega^{\circ}_{E}((v,w))\circ\omega^{\circ}_{V}(w)$
$\displaystyle=\sum_{w\in\textrm{ch}(v)\cap
V_{1}}\omega_{E1}((v,w))\circ\omega_{V1}(w)\circ\omega_{V2}(t_{2})$
$\displaystyle=\left[\sum_{w\in\textrm{ch}(v)\cap
V_{1}}\omega_{E1}((v,w))\circ\omega_{V1}(w)\right]\circ\omega_{V2}(t_{2})$
$\displaystyle=\omega_{V1}(v)\circ\omega_{V2}(t_{2}),$

where $\omega^{\circ}_{E}((v,w))=\omega_{E1}((v,w))$ holds by definition, the
second line is the induction hypothesis, and the third line follows from the
right distributivity of the operations, cf. property (S6). In particular, the
homomorphism property
$\omega_{V}^{\circ}(t^{+})=\omega_{V1}(t_{1})\circ\omega_{V2}(t_{2})$ holds.

Of particular importance are the trees decorated by the generating sets
$\\{\phi_{x}\\}_{x\in X}\cup\\{0\\}$ and $\\{\phi_{r}\\}_{r\in R}\cup\\{0\\}$
of $\mathcal{S}^{R}$ and $\mathcal{S}$. The respective tree algebras are
denoted by

$\displaystyle\mathfrak{T}$ $\displaystyle:=\mathfrak{T}(\\{\phi_{x}\\}_{x\in
X}\cup\\{0\\}),$ $\displaystyle\mathfrak{T}^{R}$
$\displaystyle:=\mathfrak{T}(\\{\phi_{r}\\}_{r\in R}\cup\\{0\\}).$

There is a map with nice algebraic properties between the tree algebras

$\displaystyle\mathfrak{T}$
$\displaystyle\xlongrightarrow{\tau}\mathfrak{T}^{R},$

which is defined based on the relation $\phi_{x}=\sum_{(x,r)\in C}\phi_{r}$
between the edge labels. First, $\tau$ maps the trivial tree with one vertex
in $\mathfrak{T}$ to the trivial tree in $\mathfrak{T}^{R}$. Next, let
$T_{\phi}$ be the decorated rooted tree with one edge which is labelled by
$\phi$. The tree $T_{\phi}$ is said to be the atomic tree with label $\phi$.
For an atomic tree $T_{\phi_{x}}\in\mathfrak{T}$, the label function
$\phi_{x}$ can be uniquely decomposed as a sum of functions corresponding to
reactions according to its definition, cf. Equation (2.4):

$\phi_{x}=\sum_{(x,r)\in C}\phi_{r}.$

Thus, $\tau(T_{\phi_{x}})$ is defined as the sum of the corresponding atomic
trees

$\tau(T_{\phi_{x}}):=\sum_{(x,r)\in C}T_{\phi_{r}}.$

A tree $T\in\mathfrak{T}$ of height one can be written as a finite sum of
atomic trees, i.e. $T=\sum_{j=1}^{m}T_{\phi_{x_{j}}}$, and the map $\tau$ on
$\mathfrak{T}^{1}$ is defined as

$\tau(T):=\sum_{j=1}^{m}\tau(T_{\phi_{x_{j}}}).$

An arbitrary tree $T\in\mathfrak{T}^{n}$ of height $n$ can be written as
$T=\sum_{j=1}^{m}T_{\phi_{x_{j}}}\circ T_{j}$ for atomic trees
$T_{\phi_{x_{j}}}$ and trees $T_{j}\in\mathfrak{T}^{\leq(n-1)}$ of height
$\leq(n-1)$. The map $\tau$ is defined recursively as

$\displaystyle\tau(T):=\sum_{j=1}^{m}\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j}).$
(3.5)

The substitution process is illustrated in Fig. 5A and an example of the
construction $T\mapsto\tau(T)$ for the CRN in Fig. 5B is given in Fig. 5C.

Figure 5: Illustration of the construction of the map
$\tau:\mathfrak{T}\rightarrow\mathfrak{T}^{R}$. A Illustration of the general
procedure of replacing an edge of $T\in\mathfrak{T}$ with label $\phi_{x}$ by
an edge for each summand in $\phi_{x}=\sum_{(x,r)\in
C}\phi_{r}=\sum_{j=1}^{m}\phi_{r_{j}}$ with labels $\phi_{r_{j}}$. This is
performed recursively starting with the terminal edges and working upwards
toward the root. B An example CRS with the functions of chemicals given by
$\phi_{a}=\phi_{r_{1}}+\phi_{r_{2}}$, $\phi_{c}=\phi_{r_{1}}+\phi_{r_{3}}$ and
$\phi_{d}=\phi_{r_{3}}$. C The map $\tau$ applied to the tree $T$ on the left
for the CRS featured in B.

######  Lemma 3.6.

The map $\tau:\mathfrak{T}\rightarrow\mathfrak{T}^{R}$ defined above is a
homomorphism with respect to the addition and multiplication of trees.
Moreover, the label of the root $\omega_{V}(t)$ is invariant under $\tau$ for
any tree $T\in\mathfrak{T}$, i.e., using the evaluation map defined in (3.3),
the relation

$\displaystyle ev(T)=ev(\tau(T))$

holds.

Proof: Let $T_{1},T_{2}$ be two nontrivial trees in $\mathfrak{T}$. They can
be written as $T_{1}=\sum_{j=1}^{m}T_{\phi_{x_{j}}}\circ T_{j}$ and
$T_{2}=\sum_{j=m+1}^{l}T_{\phi_{x_{j}}}\circ T_{j}$ with atomic trees
$T_{\phi_{x_{j}}}$. Their sum is given by
$T_{1}+T_{2}=\sum_{j=1}^{l}T_{\phi_{x_{j}}}\circ T_{j}$ and the compatibility
of $\tau$ with respect to addition follows from the definition (3.5) and from
the associativity of addition
$\tau(T_{1}+T_{2})=\sum_{j=1}^{l}\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j})=\tau(T_{1})+\tau(T_{2})$.

The compatibility of $\tau$ with respect to multiplication is shown
inductively on $\textrm{ht}(T_{1})$. If $\textrm{ht}(T_{1})=1$, then
$T_{1}=\sum_{j=1}^{m}T_{\phi_{x_{j}}}$ and $T_{1}\circ
T_{2}=(\sum_{j=1}^{m}T_{\phi_{x_{j}}})\circ
T_{2}=\sum_{j=1}^{m}(T_{\phi_{x_{j}}}\circ T_{2})$ by Remark 3.4. Thus, the
property $\tau(T_{1}\circ
T_{2})=\sum_{j=1}^{m}(\tau(T_{\phi_{x_{j}}})\circ\tau(T_{2}))=(\sum_{j=1}^{m}\tau(T_{\phi_{x_{j}}}))\circ\tau(T_{2})=\tau(T_{1})\circ\tau(T_{2})$
follows from the definition (3.5) and the right distributivity of the tree
algebra $\mathfrak{T}^{R}$. Let $\textrm{ht}(T_{1})=n$ and let $T_{1}$ be
given by expression $T_{1}=\sum_{j=1}^{m}T_{\phi_{x_{j}}}\circ T_{j}$ as above
with $\textrm{ht}(T_{j})\leq(n-1)$. Then $T_{1}\circ
T_{2}=(\sum_{j=1}^{m}T_{\phi_{x_{j}}}\circ T_{j})\circ
T_{2}=\sum_{j=1}^{m}(T_{\phi_{x_{j}}}\circ T_{j}\circ T_{2})$ yields

$\displaystyle\tau(T_{1}\circ T_{2})$
$\displaystyle=\sum_{j=1}^{m}\left[\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j}\circ
T_{2})\right]$
$\displaystyle=\sum_{j=1}^{m}\left[\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j})\circ\tau(T_{2})\right]$
$\displaystyle=\sum_{j=1}^{m}\left[\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j})\right]\circ\tau(T_{2})=\tau(T_{1})\circ\tau(T_{2}),$

where the first line follows from the definition (3.5), the second line from
the induction hypothesis, and the third line from the right distributivity of
the tree algebra.

The invariance of the root label holds for an atomic tree as
$ev(T_{\phi_{x}})=\phi_{x}$ and $ev(\tau(T_{\phi_{x}}))=ev(\sum_{(x,r)\in
C}T_{\phi_{r}})=\sum_{(x,r)\in C}\phi_{r}=\phi_{x}$. It extends to the trees
of height 1 by the associativity of the addition of trees and elements in
$\mathcal{T}(\mathfrak{X})$. For a tree of arbitrary height this is verified
inductively. Let $T=\sum_{j=1}^{m}T_{\phi_{x_{j}}}\circ T_{j}$. Its root label
is determined by (3.1) as $ev(T)=\sum_{j=1}^{m}\phi_{x_{j}}\circ ev(T_{j})$.
The root label of $\tau(T)$ is given by

$ev(\tau(T))=ev\left(\sum_{j=1}^{m}\tau(T_{\phi_{x_{j}}})\circ\tau(T_{j})\right)=\sum_{j=1}^{m}\phi_{x_{j}}\circ
ev(\tau(T_{j})),$

which agrees with $ev(T)$ by induction hypothesis.

These constructions yield the following central theorem.

######  Theorem 3.7.

With the maps $ev$ and $\tau$ defined above and the inclusion
${\iota:\mathcal{S}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}}\rightarrow\mathcal{S}^{R}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}$,
the following diagram commutes

${\mathfrak{T}}$${\mathcal{S}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}}$${\mathfrak{T}^{R}}$${\mathcal{S}^{R}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}}$$\scriptstyle{ev}$$\scriptstyle{\tau}$$\scriptstyle{\iota}$$\scriptstyle{ev}$

and all maps are homomorphisms. Moreover, the evaluation maps $ev$ are
surjective.

Proof: The homomorphism property follows from the Lemmata 3.5 and 3.6. The
commutativity of the diagram has also been proven in Lemma 3.6. The evaluation
maps are surjective because the generators $\\{\phi_{x}\\}_{x\in
X}\cup\\{0\\}\subset\mathcal{S}$ and ${\\{\phi_{r}\\}_{x\in
R}\cup\\{0\\}\subset\mathcal{S}^{R}}$ have preimages given by the atomic trees
$\\{T_{\phi_{x}}\\}_{x\in X}\cup\\{T_{0}\\}\subset\mathfrak{T}$ and
${\\{T_{\phi_{r}}\\}_{r\in R}\cup\\{T_{0}\\}\subset\mathfrak{T}^{R}}$ combined
with the fact that the tree algebras are closed under the operations of
addition and multiplication.

The finiteness of $\mathcal{S}$ yields the following corollary.

######  Corollary 3.8.

There is an $N$ such that the set of trees of height at most
$\mathfrak{T}^{\leq N}$ maps surjectively onto
$\mathcal{S}\cup\\{\textrm{id}\mid_{\mathfrak{X}}\\}$.

Moreover, Theorem 3.7 implies that the elements of $\mathcal{S}$ and
$\mathcal{S}^{R}$ can be represented as decorated rooted trees by lifting the
respective semigroup elements via the homomorphism $ev$.

######  Definition 3.9.

A tree representative of an element $\phi\in\mathcal{S}$ is an element
$T\in\mathfrak{T}$ such that $ev(T)=\phi$. The representative is called
minimal if it has no subtree $T^{\prime}$ such that $ev(T^{\prime})=\phi$. The
analogous definition holds for tree representatives of elements of
$\mathcal{S}^{R}$ in $\mathfrak{T}^{R}$.

######  Remark 3.10 (Biochemical interpretation of a tree).

A tree $T\in\mathfrak{T}^{R}$ of level $n$ corresponds to a ”reaction
mechanism” of the network which can be described as follows: The reactions at
the terminal edges are carried out and their products are supplied to their
tail vertices. For each vertex, once it has received the products from all its
outgoing edges, these products act as reactants for the reaction on its
incoming edge. This procedure is carried out iteratively for the levels of the
tree and therefore takes $n-1$ steps for a tree of height $n$. For a tree
$T\in\mathfrak{T}$, the respective reaction mechanism is the reaction
mechanism described $\tau(T)\in\mathfrak{T}^{R}$.

Finally, the decorated rooted trees in $\mathfrak{T}^{R}$ can be used to
reformulate the F property given in Definition 2.4. In particular, the
condition (F) can be encoded in a tree:

######  Definition 3.11.

Let $x\in X_{F}$ be a chemical for which the condition (F) holds. Let
$R_{1},\dotsc,R_{n}$ be the sets of reactions featured in (F) and denote by
$T_{\phi_{r}}$ the atomic trees for the functions $\phi_{r}$. Define the trees
$T_{1}^{R},\dotsc,T_{n}^{R}\in\mathfrak{T}^{R}$ inductively as follows: Let

$T_{1}^{R}:=\sum_{r\in R_{1}}T_{\phi_{r}},$ (3.6)

and for $1<i<n$:

$T_{i+1}^{R}:=\sum_{r\in\bigcup_{j=1}^{i+1}R_{j}}T_{\phi_{r}}\circ T_{i}^{R}.$
(3.7)

The tree $T_{n}^{R}$ is said to be the F-tree for the element $x$. It is
denoted by $T^{R}(x)$.

######  Lemma 3.12.

Let $x\in X_{F}$ be a chemical for which the condition (F) holds. Then for the
F-tree $T^{R}(x)$, the relation

$x\in ev\left(T^{R}(x)\right)(\emptyset)$

holds. In other words, $T^{R}(x)$ represents a reaction mechanism that
produces $x$ from the food set.

Proof: Let $T_{i}^{R}$ be the trees from Definition 3.11 with
$T_{n}^{R}=T^{R}(x)$. It will be shown inductively that

$\displaystyle\bigcup_{j=1}^{i}\textrm{ran}(R_{j})\subset
ev\left(T_{i}^{R}\right)(\emptyset)\cup F$ (3.8)

holds for all $i=1,\dotsc,n$ and therefore

$\displaystyle\bigcup_{j=1}^{i+1}\textrm{dom}(R_{j})\subset
ev\left(T_{i}^{R}\right)(\emptyset)\cup F$ (3.9)

holds for all $i=1,\dotsc,n-1$. The inclusion (3.9) follows from (3.8)
together with the conditions (F1) and (F2). Then, the claim $x\in
ev\left(T_{n}^{R}\right)(\emptyset)$ will follow from the inclusion (3.8)
together with the condition (F3).

For $i=1$, the definition of $T_{1}^{R}$ gives

$ev\left(T_{1}^{R}\right)(\emptyset)\cup F=\sum_{r\in
R_{1}}\phi_{r}(\emptyset)\cup F.$

From condition (F1), i.e. $\textrm{dom}(R_{1})\subset F$, it follows that
$\textrm{ran}(R_{1})=\sum_{r\in R_{1}}\phi_{r}(\emptyset)\subset
ev\left(T_{1}^{R}\right)(\emptyset)\cup F$. And from condition (F2), i.e.
$\textrm{dom}(R_{2})\subset\textrm{ran}(R_{1})\cup F$, together with (F1), it
follows that $\textrm{dom}(R_{1})\cup\textrm{dom}(R_{2})\subset
ev\left(T_{1}^{R}\right)(\emptyset)\cup F$.

For $i+1$, one obtains

$\displaystyle ev\left(T_{i+1}^{R}\right)(\emptyset)\cup F$
$\displaystyle=\sum_{r\in\bigcup_{j=1}^{i+1}R_{j}}\phi_{r}\left(ev\left(T_{i}^{R}\right)(\emptyset)\right)\cup
F$ $\displaystyle\supset\bigcup_{j=1}^{i+1}\textrm{ran}(R_{j}),$

where the final inclusion is obtained from the induction hypothesis
$\bigcup_{j=1}^{i+1}\textrm{dom}(R_{j})\subset
ev\left(T_{i}^{R}\right)(\emptyset)\cup F$. The conditions (F1) and (F2) imply
now that $\bigcup_{j=1}^{i+2}\textrm{dom}(R_{j})\subset
ev\left(T^{R}_{i+1}\right)(\emptyset)\cup F$ for $i\leq n-2$.

##  4 Characterization of self-sustaining and self-generating CRS

In this section, the representation of semigroup elements as trees is used to
derive a succinct expression for the maximal RAF set of chemicals of a CRS as
the fixed point of the generative dynamics $Y\mapsto\Phi_{Y}(\emptyset)$ with
the initial condition $Y_{0}=X_{F}$ (Theorem 4.8). In Section 4.1, it is shown
that a CRS if RAF if and only if $\Phi_{X_{F}}(\emptyset)=X_{F}$ holds
(Theorem 4.1) and that the condition
$\Phi_{X_{F}^{\prime}}(\emptyset)=X_{F}^{\prime}$ is sufficient for a set of
chemicals $X_{F}^{\prime}\subset X_{F}$ to be a RAF set of chemicals
(Proposition 4.3). The latter statement is the key statement to prove that the
fixed point of the dynamics, which is introduced in Section 4.2, satisfies the
desired properties. The importance of fixed points of the dynamics as
functionally closed and therefore biologically relevant entities is discussed
in Section 4.3.

This whole section follows a logical structure which is analogous the
structure of Section 4 in Loutchko (2022), where the analogous statements are
proven for self-sustaining CRS. However, the treatment of self-generating CRS
is technically more involved, which is forced by the fact that the F property
is more involved than the self-sustainment property of a CRS, cf. Remark 2.6.

Throughout this section, fix a CRS $(X,R,C,F)$ and let $\mathcal{S}$ be its
semigroup model.

###  4.1 Characterization of CRS with the RAF property

A CRS with the RAF property can be conveniently characterized via the set of
chemicals generated by the maximal function of its semigroup model from the
food set.

######  Theorem 4.1.

A CRS is RAF if and only if the maximal function $\Phi_{X_{F}}$ of its
semigroup model satisfies

$\Phi_{X_{F}}(\emptyset)=X_{F}.$ (4.1)

Proof: If the CRS is RAF, then by Lemma 3.12, the function $ev(T^{R}(x))$
satisfies $x\in ev(T^{R}(x))(\emptyset)$ for all $x\in X_{F}$. This function
is an element of $\mathcal{S}^{R}$ but not of $\mathcal{S}$ in general. The
RAF property allows to construct a tree $T(x)\in\mathfrak{T}$ such that
$ev(T^{R}(x))\leq ev(T(x))$ and thus $x\in ev(T(x))(\emptyset)$: Choose a
catalyst $y(r)\in X$ for each reaction $r\in R_{i}$ for all $R_{i}$ featured
in the condition (F) for $x\in X_{F}$. In analogy to the formulae (3.6) and
(3.7), define

$T_{1}:=\sum_{r\in R_{1}}T_{\phi_{y(r)}},$ (4.2)

and for $1<i<n$:

$T_{i+1}:=\sum_{r\in\bigcup_{j=1}^{i+1}R_{j}}T_{\phi_{y(r)}}\circ T_{i}$ (4.3)

with the atomic trees $T_{\phi_{y(r)}}\in\mathfrak{T}$ and set $T(x):=T_{n}$.
The properties (S1), (S2) and (S3) ensure that $ev(T^{R}(x))\leq ev(T(x))$.
The function

$\displaystyle\Phi:=\sum_{x\in X_{F}}ev(T(x))$

satisfies $X_{F}\subset\Phi(\emptyset)$ and thus the equality
$\Phi(\emptyset)=X_{F}$ holds. Therefore, $\Phi$ is the maximal function
$\Phi_{X_{F}}$ of $\mathcal{S}$ and the claim $\Phi_{X_{F}}(\emptyset)=X_{F}$
holds.

To prove the reverse, assume that $\Phi_{X_{F}}(\emptyset)=X_{F}$ holds.
Choose a representative $T\in\mathfrak{T}$ for $\Phi_{X_{F}}$, i.e. a tree $T$
such that $ev(T)=\Phi_{X_{F}}$, and consider its image
$\tau(T)\in\mathfrak{T}^{R}$. Fix a chemical $x\in X_{F}$. By Theorem 3.7, the
relation

$\displaystyle x\in ev(\tau(T))(\emptyset)$

holds. Choose a subtree $T^{min}(x)\in\mathfrak{T}^{R}$ of $\tau(T)$ which is
minimal under the condition

$\displaystyle x\in ev(T^{min}(x))(\emptyset).$ (4.4)

The existence of $T^{min}(x)$ follows from the existence of $\tau(T)$. The
sets $R_{1},\dotsc,R_{n}$ featured in the condition (F) are constructed as
follows: Let the height of $T^{min}(x)$ be $n$ and define the set $R_{i}$ to
contain the reaction corresponding to the labels of all edges whose heads have
level $n+1-i$ for $1\leq i\leq n$, i.e.

$R_{i}:=\\{r\in R\textrm{ such that }\phi_{r}=\omega_{E}(e)\textrm{ for some
}e\in\textrm{elv}_{n+1-i}(T^{min}(x))\\},$ (4.5)

where $\omega_{E}$ is the decoration function for the edges of $T^{min}(x)$.
By the minimality of $T^{min}(x)$, the conditions (F1) and (F2) must be
satisfied (reactions in any of the $R_{i}$ which do not satisfy the conditions
could be omitted from the tree without violating the condition (4.4) thus
contradicting the minimality of $T^{min}(x)$). The condition (F3) holds by
construction of $T^{min}(x)$. Finally, all reactions appearing as edge labels
of $T^{min}(x)$, and thereby all reactions in the sets $R_{1},\dotsc,R_{n}$,
are catalyzed because this holds for $\tau(T)$ by construction. This concludes
the proof.

######  Corollary 4.2.

If $X_{F}^{\prime}\subset X_{F}$ is a RAF set of chemicals, then the inclusion

$X_{F}^{\prime}\subset\Phi_{X_{F}^{\prime}}(\emptyset)$

holds.

Proof: The maximal function $\Phi^{\prime}_{X^{\prime}_{F}}$ of the semigroup
model $\mathcal{S}^{\prime}(X^{\prime},R\mid_{X^{\prime}})$ satisfies
$\Phi^{\prime}_{X^{\prime}_{F}}(\emptyset)=X^{\prime}_{F}$ by Theorem 4.1. Its
extension $ext(\Phi^{\prime}_{X^{\prime}_{F}})$, defined in Remark 2.14,
satisfies $ext(\Phi^{\prime}_{X^{\prime}_{F}})(\emptyset)=X^{\prime}_{F}$ by
definition. The relation (2.9) gives

$ext(\Phi^{\prime}_{X^{\prime}_{F}})\leq\Phi_{X^{\prime}_{F}}$

and yields the claim when the functions above are applied to the empty set.

For a RAF set of chemicals $X^{\prime}_{F}$, the inclusion
$X^{\prime}_{F}\subset\Phi_{X^{\prime}_{F}}(\emptyset)$ can be strict and
therefore, in general, the equality
$X^{\prime}_{F}=\Phi_{X^{\prime}_{F}}(\emptyset)$ is not satisfied. However,
it is a sufficient condition for $X^{\prime}_{F}$ to be a RAF set of
chemicals.

######  Proposition 4.3.

If the equality $X^{\prime}_{F}=\Phi_{X^{\prime}_{F}}(\emptyset)$ holds for a
set of chemicals $X^{\prime}_{F}\subset X_{F}$, then $X^{\prime}_{F}$ is a RAF
set of chemicals.

Proof: The proof is analogous to the second part of the proof of Theorem 4.1.
As in that proof, let $T\in\mathfrak{T}$ be a tree representative for the
function $\Phi_{X^{\prime}_{F}}\in\mathcal{S}$ of minimal height and let
$T^{min}(x)\in\mathfrak{T}^{R}$ be a minimal subtree of $\tau(T)$ that
satisfies $x\in ev(T^{min}(x))(\emptyset)$ for $x\in X^{\prime}_{F}$ and has
the same height as $T$. Moreover, let $T$ be chosen such that all its edge
labels are contained in the generating set $\\{\phi_{x}\\}_{x\in X^{\prime}}$
of $\mathcal{S}(X^{\prime}_{F})$ (this is always possible since $T$ represents
an element of $\mathcal{S}(X^{\prime}_{F})$). This leads to the sets of
reactions $R_{1},\dots,R_{n}$ defined by (4.5) and satisfying the condition
(F) (the verification of this condition is analogous to the verification in
the proof of Theorem 4.1). One only needs to ensure that all reactions $r$
contained in the $R_{i}$ satisfy $\textrm{supp}(r)\subset X^{\prime}$, i.e.
that they are elements of $R\mid_{X^{\prime}}$, which is now shown:

The domain of each $R_{i}$ for $1\leq i\leq n$ satisfies

$\textrm{dom}(R_{i})\subset\bigcup_{v\in\textrm{lv}_{n+1-i}(T^{min}(x))}\omega_{V}(v)(\emptyset)\cup
F,$

because the edges corresponding to the reactions with domains which are not
contained in the set on the right hand side could be removed from
$T^{min}(x)$, which would contradict its minimality (in the above formula,
$\omega_{V}$ is the vertex decoration function of $T^{min}(x)$). Therefore, it
follows inductively that

$\textrm{ran}(R_{i})\subset\bigcup_{v\in\textrm{lv}_{n-i}(T^{min}(x))}\omega_{V}(v)(\emptyset)\cup
F.$

Consider the functions

$\phi_{i}^{R}:=\sum_{v\in\textrm{lv}_{n-i}(T^{min}(x))}\omega_{V}(v)\in\mathcal{S}^{R},$

which satisfy $\textrm{ran}(R_{i})\subset\phi_{i}^{R}(\emptyset)\cup F$. By
construction of $T^{min}(x)$ as a subtree of $\tau(T)$ of the same height, the
function $\phi_{i}^{R}$ is bounded from above by corresponding function
$\phi_{i}$ constructed from $T$

$\phi_{i}:=\sum_{v\in\textrm{lv}_{n-i}(T)}\omega_{V}(v)\in\mathcal{S}.$

The $\phi_{i}$ are elements of $\mathcal{S}(X^{\prime}_{F})$ and are thus
bounded from above by $\Phi_{X^{\prime}_{F}}$. This leads to the inclusion

$\displaystyle\textrm{ran}(R_{i})\subset\phi_{i}^{R}(\emptyset)\cup
F\subset\phi_{i}(\emptyset)\cup F\subset\Phi_{X^{\prime}_{F}}(\emptyset)\cup
F=X^{\prime}.$

Together with the properites (F1) and (F2), this yields
$\textrm{supp}(R_{i})\subset X^{\prime}$ for all sets $R_{i}$.

This proposition will be used to show that the fixed points of the dynamics,
defined in the next section, are RAF sets of chemicals.

###  4.2 Generative dynamics on a semigroup model and identification of the
maximal RAF set of chemicals

The generative discrete dynamics of a CRS is introduced and used to determine
the maximal RAF set of chemicals. Starting with any set of chemicals
$Y_{0}\subset X_{F}$, there is a maximal function $\Phi_{Y_{0}}$ (Definition
2.12) that is supported on this set. By acting on the empty set,
$\Phi_{Y_{0}}(\emptyset)$ gives all non-food chemicals that can be generated
from the food set by using functionality supported only on $Y_{0}$ and the
food set. The argument can be applied iteratively and gives rise to the
following definition.

######  Definition 4.4.

The generative dynamics of a CRS with the initial condition $Y_{0}\subset
X_{F}$ is generated by the propagator

$\displaystyle\mathcal{D}^{g}:\mathfrak{X}$
$\displaystyle\rightarrow\mathfrak{X}$ (4.6) $\displaystyle Y$
$\displaystyle\mapsto\Phi_{Y}(\emptyset),$

where $\Phi_{Y}$ is the function of $Y\subset X_{F}$. The dynamics generated
by $\mathcal{D}^{g}$ is parametrized by $\mathbb{Z}_{\geq 0}$ as

$Y_{n+1}=\mathcal{D}^{g}(Y_{n})\text{ for all }n\in\mathbb{Z}_{\geq 0}.$

The generative dynamics has analogous properties to the sustaining dynamics
and the reader is referred to Section 4.2. in Loutchko (2022) for a more
detailed discussion. Here, only the properties needed for the proof of the
main theorem are given.

######  Remark 4.5.

Due to the finiteness of the state space $\mathfrak{X}$, the dynamics either
leads to a fixed point or to periodic behavior. If the initial condition
$Y_{0}$ leads to a fixed point, the dynamics is said to stabilize and the
fixed point is denoted by $Y_{0}^{*g}$.

######  Proposition 4.6.

Let the dynamics be given by $(Y_{n})_{n\in\mathbb{Z}_{\geq 0}}$. If
$Y_{1}\subset Y_{0}$, then

$Y_{n+1}\subset Y_{n}$

holds for all $n\in\mathbb{Z}_{\geq 0}$ and the dynamics stabilizes. The
analogous statement holds for the case that $Y_{1}\supset Y_{0}$.

Proof: The proof proceeds by induction. By hypothesis $Y_{1}\subset Y_{0}$ is
satisfied. Let $Y_{n}\subset Y_{n-1}$. This implies the ordering of the
respective functions $\Phi_{Y_{n}}\leq\Phi_{Y_{n-1}}$ by the property (S8).
Together with the property (S1) this gives

$Y_{n+1}=\Phi_{Y_{n}}(\emptyset)\subset\Phi_{Y_{n-1}}(\emptyset)=Y_{n}.$

The dynamics is thus given by the decreasing chain of subsets $Y_{0}\supset
Y_{1}\supset...\supset Y_{n}\supset Y_{n+1}\dots$ and, because $X_{F}$ is
finite, the chain stabilizes. The case $Y_{1}\supset Y_{0}$ is treated
analogously.

######  Lemma 4.7.

Let $X^{\prime}_{F}\subset X_{F}$ be a RAF set of chemicals let $Y$ be a set
that satisfies $X^{\prime}_{F}\subset Y\subset X_{F}$. Then the inclusion

$X^{\prime}_{F}\subset\Phi_{Y}(\emptyset)$

holds.

Proof: The chain of inclusions

$X^{\prime}_{F}\subset\Phi_{X^{\prime}_{F}}(\emptyset)\subset\Phi_{Y}(\emptyset)$

follows from the Corollary 4.2 and the property (S8).

Now the main theorem is stated and proven:

######  Theorem 4.8 (on the maximal RAF set of chemicals).

The maximal RAF set of chemicals of a CRS is the fixed point of the generative
dynamics $(Y_{n})_{n\in\mathbb{Z}_{\geq 0}}$ with the initial condition
$Y_{0}=X_{F}$, i.e. it is the set $X_{F}^{*g}$.

Proof: It follows from Proposition 4.6 that the dynamics has a fixed point
$X_{F}^{*g}$. By Proposition 4.3 this fixed point is a RAF set of chemicals.
It remains to show the maximality of $X_{F}^{*g}$: For any RAF set of
chemicals $X_{F}^{\prime}\subset X_{F}$, the repeated application of Lemma 4.7
implies that $X_{F}^{\prime}\subset Y_{n}$ for all $n\in\mathbb{Z}_{\geq 0}$
and therefore $X_{F}^{\prime}\subset X_{F}^{*g}$.

######  Corollary 4.9.

A CRS with a nilpotent semigroup $(\mathcal{S},\circ)$ has no nontrivial RAF
sets of chemicals.

Proof: Let $X_{F}^{\prime}\subset X_{F}$ be a nontrivial RAF set of chemicals.
Then $X_{F}^{\prime}\subset\Phi_{X_{F}^{\prime}}(\emptyset)$ holds by
Corollary 4.2 and thus the condition (S1) implies that

$X_{F}^{\prime}\subset\Phi_{X_{F}^{\prime}}^{n}(\emptyset)$

for any power of $\Phi_{X_{F}^{\prime}}$, i.e. $\Phi_{X_{F}^{\prime}}^{n}$ is
nonzero for any $n\in\mathbb{N}$.

Nilpotent semigroups comprise the largest class of semigroups as any magma333A
magma is a semigroup without the associativity property. with the product of
any three elements equal to zero is automatically a semigroup, cf. Satoh et al
(1994); Almeida (1995). The above corollary weeds out all nilpotent semigroups
as candidates for semigroup models of self-generating CRS and states that such
models are located in a more interesting class of semigroups.

######  Remark 4.10 (Connection to the RAF algorithm).

Hordijk and Steel (2004) have presented an algorithm to find the maximal RAF
set of reactions. It consists of a dynamics on the power set of reactions
$\mathcal{P}(R)$ generated by $R^{\prime}\mapsto\delta(\gamma(R^{\prime}))$
with the initial condition $R_{0}=R$. The following two operations are
performed iteratively:

  1. (R1)

For a set $R^{\prime}\subset R$, remove all reactions from $R^{\prime}$ that
have no catalyst in $\textrm{supp}(R^{\prime})$ until no further reductions
can be made. This yields the set $\gamma(R^{\prime})$.

  2. (R2)

For a set $R^{\prime}\subset R$, until no further reductions can be made,
remove all reactions $r$ from $R^{\prime}$ that satisfy
${\textrm{dom}(r)\not\subset\Phi_{R^{\prime}}(\emptyset)\cup F}$, where
$\Phi_{R^{\prime}}$ is the maximal function of the semigroup model
$\mathcal{S}^{R}(R^{\prime}):=\langle\phi_{r}\rangle_{r\in R^{\prime}}$. This
yields the set $\delta(R^{\prime})$.

Note that (R2) has been rephrased here to suit the language of semigroup
models. This is similar in spirit to the algorithm given in Theorem 4.8 by the
generative dynamics $Y\mapsto\Phi_{Y}(\emptyset)$, where the sets of chemicals
$Y$ should be thought of as the support of $R^{\prime}$ featured in the RAF
algorithm. By forming the function $\Phi_{Y}$, all reactions without a
catalyst in $Y=\textrm{supp}(R^{\prime})$ are excluded, which corresponds to
(R1). The application of the function $\Phi_{Y}$ to the empty set corresponds
to the exclusion of all reactions without support in $\Phi_{Y}(\emptyset)$,
i.e. to the step (R2).

###  4.3 Functionally closed RAF sets of chemicals

In addition to the knowledge of the maximal RAF set of chemicals, the
hierarchy of RAF subsets of chemicals plays an important role in the
understanding of a CRS. Of particular importance are the RAF sets of chemicals
which satisfy the fixed point equation for the dynamics and are termed
functionally closed RAF sets of chemicals in this section. This is closely
related to the notion of functionally closed sets of self-sustaining
chemicals, which is developed in Loutchko (2022), Section 4.4.

If, for a RAF set of chemicals $X_{F}^{\prime}\subset X_{F}$, the inclusion
$X_{F}^{\prime}\subset\Phi_{X_{F}^{\prime}}(\emptyset)$ is strict, then the
set is not stable in the sense that it will produce additional chemicals over
time. First, the chemicals in $Y_{1}=\Phi_{X_{F}^{\prime}}(\emptyset)$ will be
generated from the food set, followed by chemicals in
$Y_{2}=\Phi_{Y_{1}}(\emptyset)$, etc. By Proposition 4.6, this dynamics
stabilizes at the fixed point $X_{F}^{\prime*g}$, which contains the original
RAF set of chemicals $X_{F}^{\prime}$. Moreover, being a fixed point of the
dynamics, $X_{F}^{\prime*g}$ satisfies

$\Phi_{X_{F}^{\prime*g}}(\emptyset)=X_{F}^{\prime*g}$

and is thus a RAF set of chemicals by Proposition 4.6. The set
$X_{F}^{\prime*g}$ is not able to further catalyze the generation of chemicals
outside of $X_{F}^{\prime*g}$ from the food set and is thus functionally
closed. This motivates the following definition.

######  Definition 4.11.

The functional closure of a RAF set of chemicals $X_{F}^{\prime}\subset X_{F}$
is the fixed point $X_{F}^{\prime*g}$ of the generative dynamics. If
$X_{F}^{\prime}$ satisfies the fixed point equation
$\Phi_{X_{F}^{\prime}}(\emptyset)=X_{F}^{\prime}$, then it is said to be a
functionally closed RAF set of chemicals.

Alternatively, the closure of a RAF set of chemicals can be characterized as
follows:

######  Lemma 4.12.

The functional closure $X_{F}^{\prime*g}$ of a RAF set of chemicals
$X_{F}^{\prime}$ is the unique minimal functionally closed RAF set of
chemicals which contains $X_{F}^{\prime}$.

Proof: Let $Y$ be a minimal functionally closed RAF set which contains
$X_{F}^{\prime}$ and let $(Y_{n})_{n\in\mathbb{Z}_{\geq 0}}$ be the generative
dynamics with the initial condition $Y_{0}=X_{F}^{\prime}$ and fixed point
$X_{F}^{\prime*g}$. Then $Y_{n}\subset Y$ holds for all $n\in\mathbb{Z}_{\geq
0}$, which can be verified by induction: For $n=0$, the claim holds by
assumption and the inductive step is verified by

$Y_{n+1}=\Phi_{Y_{n}}(\emptyset)\subset\Phi_{Y}(\emptyset)=Y,$

which follows from the property (S8). This implies that
$X_{F}^{\prime*g}\subset Y$ and by the minimality of $Y$, the equality
$X_{F}^{\prime*g}=Y$ must hold.

######  Remark 4.13.

Note that the characterization of the closure of a RAF set of chemicals given
by Lemma 4.12 does not extend to arbitrary sets, i.e. in general there does
not exist a unique minimal functionally closed set of chemicals which contains
$Y$ for a arbitrary set of chemicals $Y\subset X_{F}^{*g}$. Fig. 6 provides an
illustration. The shown CRS is RAF and it has the functionally closed sets of
chemicals given by $X_{F}=\\{c,d,e\\}$, $X_{F}^{\prime}=\\{c,d\\}$ and
$X_{F}^{\prime\prime}=\\{d,e\\}$. For the set $\\{d\\}$, there exists no
unique minimal functionally closed set of chemicals which contains it.

Figure 6:  This CRS has the three functionally closed sets of chemicals given
by $X_{F}=\\{c,d,e\\}$, $X_{F}^{\prime}=\\{c,d\\}$ and
$X_{F}^{\prime\prime}=\\{d,e,\\}$. There is no unique minimal functionally
closed set of chemicals which contains the set $\\{d\\}$.

The lattice of all functionally closed sets of chemicals can be obtained by
the following construction. Define the reduced generative dynamics by the
propagator

$\displaystyle\mathcal{D}^{rg}:\mathfrak{X}$
$\displaystyle\rightarrow\mathfrak{X}$ $\displaystyle Y$ $\displaystyle\mapsto
Y\cap\Phi_{Y}(\emptyset).$

This dynamics always stabilizes, and the fixed point for the initial condition
$Y_{0}$ is denoted as $Y_{0}^{*rg}$. The fixed point equation of this dynamics
reads ${Y=Y\cap\Phi_{Y}(\emptyset)}$, which is equivalent to the fixed point
equation $Y=\Phi_{Y}(\emptyset)$ of the generative dynamics. For a set
$Y\subset X_{F}$, define the set $\mathfrak{N}(Y)\subset\mathfrak{X}$ as

$\displaystyle\mathfrak{N}(Y):=\left\\{(Y\setminus\\{y\\})^{*rg}\textrm{ for
}y\in Y\right\\}.$

All of the sets contained in $\mathfrak{N}(Y)$ are functionally closed RAF
sets of chemicals by Proposition 4.3. Moreover, let $X^{\prime}_{F}\subset Y$
be a functionally closed RAF set of chemicals which is strictly contained in
$Y$ and is maximal with this property. Then there is a chemical $y\in
Y\setminus X^{\prime}_{F}$ and one verifies that
$X^{\prime}_{F}=(Y\setminus\\{y\\})^{*rg}$.

Now inductively define the following sets

$\displaystyle\mathfrak{N}^{0}$ $\displaystyle:=\\{X_{F}^{*g}\\}$
$\displaystyle\mathfrak{N}^{i+1}$
$\displaystyle:=\bigcup_{Y\in\mathfrak{N}^{i}}\mathfrak{N}(Y)\textrm{ for all
}i\in\mathbb{Z}_{\geq 0}.$

Due to the finiteness of $\mathfrak{X}$, there is an $N\in\mathbb{N}$ such
that $\mathfrak{N}^{i+1}=\\{\emptyset\\}$ for all $i>N$. The following theorem
gives a description of the lattice of functionally closed RAF sets of
chemicals of a CRS, which extends the characterization of the maximal RAF set
of chemicals provided in Theorem 4.8.

######  Theorem 4.14.

The set

$\mathfrak{N}:=\bigcup_{i=0}^{N}\mathfrak{N}^{i}$

is the set of all functionally closed RAF sets of chemicals of the CRS.

Proof: By construction, all elements of $\mathfrak{N}$ are functionally closed
RAF sets of chemicals. It remains to show that all functionally closed RAF
sets of chemicals are indeed contained in $\mathfrak{N}$. In this regard,
recall that $\mathfrak{N}(Y)$ contains all maximal closed RAF sets of
chemicals which are strictly contained in $Y$. For a functionally closed RAF
set of chemicals $X_{F}^{\prime}$, there exists a chain of maximal length of
functionally closed RAF sets of chemicals

$X_{F}^{\prime}=X_{n}\subsetneq X_{n-1}\subsetneq\dots\subsetneq
X_{0}=X_{F}^{*g}.$

Then, $X_{F}^{\prime}$ must be contained in $\mathfrak{N}^{n}$.

This finishes the application of the semigroup models and their
representations by decorated rooted tree to self-generating CRS. The possible
implications of the results of this section are now discussed.

##  5 Discussion

A general discussion of the semigroup models of CRS is given by Loutchko
(2022), where, for example, algebraic properties and the possibility to
analyze the computational properties of CRS with their semigroup models are
expounded upon.

In this article, it was demonstrated how the language of semigroup models
provides a natural framework to treat CRS with the RAF property, to determine
the maximal RAF set of chemicals and to determine the lattice of functionally
closed RAF sets of chemicals. The technical basis is provided by the
representation of the elements of the semigroup models as decorated rooted
trees, because this representation is particularly useful in making the
relation of semigroup elements with the F property precise. It will be
interesting to investigate whether such representations can be used more
generally in the theoretical study of (not necessarily finite) semigroups and
semirings. Similar representations have turned out to be useful in the theory
of self-similar groups introduced by Nekrashevych (2005).

With regard to CRS theory, the notion of functionally closed sets of RAF
chemicals is a very natural concept within the theory of semigroup models. One
is naturally led to consider the fixed points of the dynamics, which are RAF
sets of chemicals by Proposition 4.6. Moreover, Lemma 4.12 ensures that each
RAF set of chemicals has a uniquely determined functional closure with nice
properties. The analysis of the lattice of functionally closed RAF sets of
chemicals of a CRS within a living organism can potentially provide insights
into the modular organization of its metabolism and the respective control
mechanisms. The fact that arbitrary subsets of $X_{F}$ \- in contrast to RAF
sets of chemicals - do not have a unique minimal functionally closed RAF set
of chemicals which contains them, inspires further investigation of CRS of
real biological systems. If a chemical (or a set of chemicals) has a unique
minimal functionally closed RAF set of chemicals to which it belongs, then one
can conjecture that this chemical is specific for the respective functional
module. And it is likely that this chemical was acquired together with the
respective module in the course of evolution. If, however, this is not the
case - such as for the chemical $d$ the example shown in Fig. 6, then the
respective chemical serves as a kind of mediator between the functional
modules in which it is contained. It will be interesting to test such
hypotheses on CRS of biological systems and to develop new ones by applying
the techniques provided by the semigroup formalism.

Another possibility suggested by the algebraic models of CRS is the coarse-
graining obtained by taking quotients of the semigroups which are well-behaved
with respect to the algebraic operations. The technical difficulty is thereby
to relate the quotients of functions, which live in
$\mathcal{T}(\mathfrak{X})$ to quotients of the state space $\mathfrak{X}$ in
a natural manner. This work is currently being finalized. This more algebraic
approach provides an alternative way to reveal and analyze the modularity of a
given CRS. Whereas the lattice of functionally closed RAF sets of chemicals
rely on the self-generating property, the quotient structures do not.
Therefore, in future, it will be interesting to compare the approach presented
in Section 4.3 of this article to the algebraic coarse-graining procedures.

Acknowledgments

I thank Tetsuya J. Kobayashi and all members of the Kobayashi lab for
stimulating discussions. This research is supported by JSPS KAKENHI Grant
Numbers 19H05799 and 21K21308, and by JST CREST JPMJCR2011 and JPMJCR1927.

## References

  *   * Almeida (1995) Almeida J (1995) Finite semigroups and universal algebra, vol 3. World Scientific
  * Dyson (1999) Dyson F (1999) Origins of life. Cambridge University Press
  * Eigen (1971) Eigen M (1971) Selforganization of matter and the evolution of biological macromolecules. Naturwissenschaften 58(10):465–523
  * Gánti (1975) Gánti T (1975) Organization of chemical reactions into dividing and metabolizing units: the chemotons. BioSystems 7(1):15–21
  * Gilbert (1986) Gilbert W (1986) Origin of life: The RNA world. nature 319(6055):618–618
  * Hordijk and Steel (2004) Hordijk W, Steel M (2004) Detecting autocatalytic, self-sustaining sets in chemical reaction systems. Journal of Theoretical Biology 227(4):451–461
  * Hordijk and Steel (2017) Hordijk W, Steel M (2017) Chasing the tail: The emergence of autocatalytic networks. Biosystems 152:1–10
  * Hordijk and Steel (2018) Hordijk W, Steel M (2018) Autocatalytic networks at the basis of life’s origin and organization. Life 8(4):62
  * Hordijk et al (2010) Hordijk W, Hein J, Steel M (2010) Autocatalytic sets and the origin of life. Entropy 12(7):1733–1742
  * Hordijk et al (2011) Hordijk W, Kauffman SA, Steel M (2011) Required levels of catalysis for emergence of autocatalytic sets in models of chemical reaction systems. International Journal of Molecular Sciences 12(5):3085–3101
  * Hordijk et al (2012) Hordijk W, Steel M, Kauffman S (2012) The structure of autocatalytic sets: Evolvability, enablement, and emergence. Acta Biotheoretica 60(4):379–392
  * Hordijk et al (2015) Hordijk W, Smith JI, Steel M (2015) Algorithms for detecting and analysing autocatalytic sets. Algorithms for Molecular Biology 10(1):15
  * Joyce (1989) Joyce GF (1989) RNA evolution and the origins of life. Nature 338(6212):217–224
  * Joyce (2002) Joyce GF (2002) The antiquity of RNA-based evolution. nature 418(6894):214–221
  * Kauffman (1986) Kauffman SA (1986) Autocatalytic sets of proteins. Journal of Theoretical Biology 119(1):1–24
  * Loutchko (2022) Loutchko D (2022) Semigroup models for biochemical reaction networks. arxiv preprint, arXiv:190804642
  * Miller (1953) Miller SL (1953) A production of amino acids under possible primitive earth conditions. Science 117(3046):528–529
  * Nekrashevych (2005) Nekrashevych V (2005) Self-similar groups. 117, American Mathematical Soc.
  * Oparin (1957) Oparin AI (1957) The Origin of Life on the Earth. Oliver & Boyd, Edinburgh & London
  * Oró (1961) Oró J (1961) Mechanism of synthesis of adenine from hydrogen cyanide under possible primitive earth conditions. Nature 191(4794):1193–1194
  * Penny (2005) Penny D (2005) An interpretive review of the origin of life research. Biology and Philosophy 20(4):633–671
  * Rhodes and Nehaniv (2010) Rhodes J, Nehaniv CL (2010) Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific
  * Rosen (1958) Rosen R (1958) A relational theory of biological systems. Bulletin of Mathematical Biology 20(3):245–260
  * Satoh et al (1994) Satoh S, Yama K, Tokizawa M (1994) Semigroups of order 8. In: Semigroup Forum, Springer, pp 7–29
  * Sousa et al (2015) Sousa FL, Hordijk W, Steel M, et al (2015) Autocatalytic sets in e. coli metabolism. Journal of Systems Chemistry 6(1):4
  * Steel (2000) Steel M (2000) The emergence of a self-catalysing structure in abstract origin-of-life models. Applied Mathematics Letters 13(3):91–95
  * Varela et al (1974) Varela FG, Maturana HR, Uribe R (1974) Autopoiesis: the organization of living systems, its characterization and a model. BioSystems 5(4):187–196