Facilitation in reaction systems

Abstract

Reaction systems is a formal model of computation which originated as a model of interactions between biochemical reactions in the living cell. These interactions are based on two mechanisms, facilitation and inhibition, and this is well reflected in the formulation of reaction systems. In this paper, we investigate the facilitation aspect of reaction systems, where the products of a reaction may facilitate other reactions by providing some of their reactants. This aspect is formalized through positive dependency graphs which depict explicitly such facilitating interactions. The focus of the paper is on demonstrating how structural properties of reaction systems defined through the properties of their positive dependency graphs influence the behavioural properties of (suitable subclasses of) reaction systems, which, as usual, are defined through their transition graphs.

1 Introduction

Reaction systems is a novel model of interactive computation which originated as a model of interactions between biochemical reactions in the living cell (see, e.g. [10, 18, 20, 21]). The main feature of these interactions is that they are driven by two mechanisms, facilitation and inhibition. If a reaction takes place in a biochemical system (here the living cell), then its products may facilitate some reactions by providing (some of) their reactants or inhibit some reactions by providing (some of) their inhibitors. The model of reaction systems formulates biochemical reactions in such a way that dynamical processes (called interactive processes) taking place in reaction systems formalize these interactions.

Thus, a reaction is defined as a triplet of nonempty sets $a = (R,I,P)$, where R is the set of reactants that a needs to take place, I is the set of inhibitors each of which forbids a to take place, and P is the set of products produced by a when it takes place. All three sets are finite.

A reaction system $\mathcal{A}= (S,A)$ consists of a finite set of reactions A and a finite background set S of entities used for defining reactions in A as well as for analysing the functioning of $\mathcal{A}$. The intuition behind the entities of A is that they represent molecular entities (e.g. atoms, ions, molecules) that may be present in the states of a biochemical system. These states are represented by subsets of S, in fact each subset of S is a state of $\mathcal{A}$.

Given a state $T \subseteq S$ of $\mathcal{A}$, one may consider all reactions from A which are enabled by T, i.e. all reactions $a = (R,I,P)$ such that all reactants of a are in T ($R \subseteq T$) and none of the inhibitors of a is in T ($I \cap T = \varnothing$). The union of products P of all those reactions form the successor state of T. Iterating this procedure one gets the state sequence of $\mathcal{A}$ beginning with T. Then, the set of all state sequences of $\mathcal{A}$ beginning with all states of $\mathcal{A}$ formalizes the behaviour of $\mathcal{A}$, its interactive processes.

In the general model of behaviour of reaction systems, one also takes into account the interaction with the environment, but in this paper we consider the interactive processes of reaction systems not influenced by the environment (technically referred to as context-independent interactive processes).

Although the model of reaction systems was inspired by biology, the research on reaction system is driven by both the biological considerations (see, e.g. [1, 3,4,5, 11, 12, 19, 22]) and considerations concerned with the understanding of computations resulting from the interactions of biochemical reactions within a reaction system as well as from the interactions of a reaction system with its environment (see, e.g. [2, 6, 8, 13, 14, 16, 17, 23, 24, 26, 28, 30,31,32]). As a matter of fact, reaction systems turned out to be a novel and interesting foundational model of interactive computations.

In this paper, we investigate the facilitating aspect of interactions of reactions in a reaction system, i.e. we consider the effects that products of reactions have on the sets of reactants. In this investigation, our focus is on the influence of the structure of a reaction system on its behaviour.

A natural way to represent the structure of a reaction system $\mathcal{A}= (S,A)$ is through its dependency graph, ${{\,\mathrm{dg}\,}}(\mathcal{A})$, which is the directed graph, where the nodes are reactions from A and there is a directed edge (a, b) from reaction a to reaction b if the product set $P_a$ of a contains either some reactants of b or some inhibitors of b or both. Such an edge (a, b) means then that a influences b or, dually, that b depends on a.

Since we investigate the facilitating aspects of interactions, we will consider the “facilitating subgraph” of ${{\,\mathrm{dg}\,}}(\mathcal{A})$, where we include only edges (a, b) such that $P_a$ contains some reactants of b but none of the inhibitors of b. This facilitating subgraph of ${{\,\mathrm{dg}\,}}(\mathcal{A})$ is called the positive dependency graph of $\mathcal{A}$.

We will investigate the effect of the structure of the positive dependency graph of a reaction system on its behaviour (i.e. the set of its state sequences). To this aim we:

• 1. restrict ourselves to subclasses of reaction systems with facilitating behaviour only, and

• 2. restrict ourselves to specific graph-theoretic structures of positive dependency graph (and investigate the influence that those structures have on the behaviour).

The paper is organized as follows.

In Sect. 2, we settle the terminology and notation concerning basic mathematical notions to be used in this paper, while in Sect. 3 we recall basic notions concerning reaction systems. Graph theoretical notions for representing the structure of reaction systems, viz., the dependency graph and the positive dependency graph, are introduced in Sect. 4.

In Sect. 5, we introduce strongly self-sustaining reaction systems, abbreviated ss-s reaction systems, which are the subject of investigation in this paper. They result by requiring that no reaction can inhibit another one (ensuring facilitation only) and requiring that the positive dependency graph consists only of cycles which are self-sustaining in the sense that in each cycle, for each reaction a in it, its predecessor b in the cycle provides all reactants for a ($R_a \subseteq P_b$). Such cycles once activated can “run” on their own. Since self-sustaining cycles are the basic building blocks of ss-s reaction systems, in Sect. 6 we first investigate ss-s reaction systems with one cycle only. We prove some basic properties of their positive dependency graph, which we then use to prove behavioural properties of ss-s reactions systems, which, as usual, are represented by transition graphs, i.e. directed graphs where nodes are the states of the system and the directed edge $(T, T')$ from the state T to the state $T'$ means that $T'$ is the successor of T.

In Sect. 7, we consider ss-s reaction systems where the underlying positive dependency graph consists of more than one cycle, but all the cycles together form specific graph-theoretic structures, viz., the so called c-chains and flowers. Again, also for these reaction systems we demonstrate how their structures, i.e. structures of their positive dependency graph, imply specific behaviours, viz., specific properties of their transition graph.

2 Preliminaries

We recall here some basic mathematical notions to be used in this paper in order to establish the terminology and notation.

As usual, $\mathbb {N}$ and $\mathbb {N}^+$ denote the set of natural numbers and the set of positive integers, respectively.

Given sets X and Y, $X - Y$ denotes their difference, $X \cup Y$ denotes their union, $X \cap Y$ denotes their intersection, and $X \times Y$ denotes their Cartesian product. Given a finite family of sets $\mathcal {F}$, we use $\bigcup \mathcal {F}$ and $\bigcap \mathcal {F}$ to denote the union and the intersection of the sets from $\mathcal {F}$, respectively.

For a finite set X, |X| denotes its cardinality and $2^X$ the set of all subsets of X (the power set of X). The empty set is denoted by $\varnothing$.

For a set X and a subset $Y \subseteq X$, the characteristic function of Y in X is the function $\mathcal {X}_{Y,X} :X \rightarrow \{0,1\}$ defined as follows: for each $x \in X$, $\mathcal {X}_{Y,X} (x) = 1$ if $x \in Y$ and $\mathcal {X}_{Y,X}(x) = 0$ if $x \notin Y$. If X is clear from the context of considerations, then we write simply $\mathcal {X}_Y$ rather than $\mathcal {X}_{Y,X}$.

A (finite, directed) graph is an ordered pair $G = (V, E)$, where V is a finite set of nodes and $E \subseteq V \times V$ is the set of edges. For $v \in V$, ${{\,\mathrm{inc}\,}}_G(v) = \{u \in V :(u, v) \in E\}$ is the set of all nodes incoming to v and ${{\,\mathrm{out}\,}}_G(v) = \{u \in V :(v, u) \in E\}$ is the set of all nodes outgoing from v. If ${{\,\mathrm{inc}\,}}_G(v) = {{\,\mathrm{out}\,}}_G(v) = \varnothing$, the v is an isolated node. If there are no isolated nodes in V, then G is reduced.

For $n \ge 1$, a sequence $v_0, v_1, \ldots , v_{n-1}, v_{n}$ of $n+1$ nodes of v such that the first n are distinct is called a cycle of G of length n, if $(v_i, v_{(i + 1) \bmod n}) \in E$ for all $i \in \{0, \ldots , n-1\}$ and $v_n = v_0$. A cycle of length 1 is a loop.

In this paper, we will consider binary strings, i.e. strings over the alphabet $\Sigma = \{0,1\}$. We will use $\Sigma ^\star$, $\Sigma ^+$, and $\Sigma ^n$ for $n \ge 1$ to denote the set of all strings, the set of nonempty strings, and the set of strings of length n over $\Sigma$, respectively. For a string $w = x_0, \ldots , x_{n-1}$, $n \ge 1$, with $x_i \in \Sigma$ for $i \in \{0, \ldots , n-1\}$, we use the notation $\langle w \rangle _i$ to denote the i-th character of w, i.e. $\langle w \rangle _i = x_i$.

For strings $w, z \in \Sigma ^+$ we say that z is a rotation of w, if $w = w_1w_2$ and $z = w_2w_1$ for some $w_1,w_2 \in \Sigma ^\star$- The strings w, z are equivalent under rotation, and an equivalence class under rotation is called a necklace (of length n, when $w, z \in \Sigma ^n$ for $n \ge 1$). If $|w_2| = 1$, then z is the elementary rotation of w.

For $n \ge 1$, ${{\,\mathrm{elr}\,}}_n$ is the function ${{\,\mathrm{elr}\,}}_n :\Sigma ^n \rightarrow \Sigma ^n$ defined by: for $w \in \Sigma ^n$, ${{\,\mathrm{elr}\,}}_n(w) = z$ if and only if z is the elementary rotation of w.

3 Reaction systems

In this section, we recall some basic notions of reaction systems. We start by recalling the notion of a reaction.

Definition 1

A reaction a is a triple $a=(R, I, P)$ of finite sets such that $P \ne \varnothing$ and $R \cap I = \varnothing$.

The set R is called the set of reactants of a, I is called the set of inhibitors, and P is the set of products (we denote R, I, P by $R_a$, $I_a$, and $P_a$, respectively). The set $R_a \cup I_a$ is called the resource set of a, denoted by $M_a$. Also, for a set of reactions A, we use the notations $R_A$, $I_A$, and $P_A$ to denote $\bigcup _{a \in A} R_a$, $\bigcup _{a \in A} I_a$, and $\bigcup _{a \in A} P_a$, respectively. Given a finite set S with $R,I,P \subseteq S$, we say that a is a reaction over S.

We note here that in Definition 1 we do not require that R and I are nonempty. This was required in the original definition of reaction systems due to biological considerations. However, since then, also reactions not satisfying this restriction are considered, especially in more mathematically oriented papers (see, e.g. [28, 34]).

Definition 2

Let S be a finite nonempty set, let $a = (R,I,P)$ be a reaction over S, let A be a set of reactions over S, and let $T \subseteq S$. Then:

• (i) a is enabled by T if $R \subseteq T$ and $I \cap T = \varnothing$.

• (ii) The result of a on T, denoted by ${{\,\mathrm{res}\,}}_a(T)$, is defined by:

  $$\begin{aligned} {{\,\mathrm{res}\,}}_a(T) = {\left\{ \begin{array}{ll} P &{} \text {it { a} is enabled by { T}} \\ \varnothing &{} \text {otherwise} \end{array}\right. } \qquad . \end{aligned}$$

• (iii) The result of A on T, denoted by ${{\,\mathrm{res}\,}}_A(T)$, is defined by:

  $$\begin{aligned} {{\,\mathrm{res}\,}}_A (T) = \bigcup _{a \in A} {{\,\mathrm{res}\,}}_a(T) \quad . \end{aligned}$$

Thus, for a given finite nonempty set S, each set A of reactions over S induces the function ${{\,\mathrm{res}\,}}_A :2^S \rightarrow 2^S$, called the result function of A, such that, for each $T \subseteq S$, ${{\,\mathrm{res}\,}}_A(T)$ is defined as in (iii) above. In particular, if A is a singleton set, $A = \{a\}$, then ${{\,\mathrm{res}\,}}_A :2^S \rightarrow 2^S$, becomes the result function ${{\,\mathrm{res}\,}}_a :2^S \rightarrow 2^S$, called the result function of a, such that, for each $T \subseteq S$, ${{\,\mathrm{res}\,}}_a(T)$ is defined as in (ii) above.

Note that the definition of ${{\,\mathrm{res}\,}}_A$ implies that the result of applying A to T is cumulative, i.e. it is the union of the results of applying all reactions from A to T. In particular, this implies that no conflict occurs between (applying) reactions from A for which the intersection of their reactants sets is nonempty.

We move now to define the notion of a reaction system.

Definition 3

A reaction system, abbreviated rs, is an ordered pair $\mathcal{A}= (S, A)$, where S is a finite non-empty set and A is a set of reactions over S.

We refer to S as the background set of $\mathcal{A}$, to elements of S as entities of $\mathcal{A}$, to subsets of S as the states of $\mathcal{A}$, and to A as the set of reactions of $\mathcal{A}$. The result function of $\mathcal{A}$, denoted by ${{\,\mathrm{res}\,}}_{\mathcal{A}}$, is the function ${{\,\mathrm{res}\,}}_{\mathcal{A}} :2^S \rightarrow 2^S$ defined by: for each $T \subseteq S$, ${{\,\mathrm{res}\,}}_{\mathcal{A}}(T) = {{\,\mathrm{res}\,}}_A(T)$.

The dynamic behaviour of reaction systems is formalized through the notion of an interactive process (see, e.g. [10, 20, 21]). These processes take into account the fact that, in general, reaction systems are open systems which interact with their environment (where the environment is formalized through the set of the so called context sequences, which are sequences of subsets of the background set of the rs under consideration). In this paper, we consider the dynamic behaviour of closed reaction system, i.e. reaction systems which do not interact with their environment (which technically means that their context sequences are sequences of empty sets). In this case the interactive processes are de facto reduced to state sequences which are defined as follows.

Definition 4

Let $\mathcal{A}= (S,A)$ be a rs. A state sequence of $\mathcal{A}$ is a countable sequence of states of $\mathcal{A}$, $\tau = T_0, T_1, \ldots$ such that, for each $i \ge 0$, $T_{i+1} = {{\,\mathrm{res}\,}}_{\mathcal{A}}(T_i)$.

Thus, $\tau = T_0, {{\,\mathrm{res}\,}}_{\mathcal{A}}(T_0), {{\,\mathrm{res}\,}}_{\mathcal{A}}^2(T_0), {{\,\mathrm{res}\,}}_{\mathcal{A}}^3(T_0), \ldots$. The state $T_0$ is the initial state of $\tau$. The set of all state sequences of $\mathcal{A}$ is denoted by ${{\,\mathrm{STS}\,}}(\mathcal{A})$.

If T is such that, for some $j \ge 0$, $T_j = T_{j+1}$, then $T_j$ is a fixed point of $\tau$ and a fixed point of $\mathcal{A}$. Fixed points of a reaction system $\mathcal{A}$ represent an important feature of the behaviour of $\mathcal{A}$: if a state sequence of $\mathcal{A}$ arrives at a fixed point, then it remains trapped there “forever”. They also constitute an important notion in a broader framework of behaviour of dynamical systems, see, e.g. [15, 24].

Since ${{\,\mathrm{res}\,}}_{\mathcal{A}}$ is a function, for each $i, j \ge 0$, if $T_i = T_j$, then ${{\,\mathrm{res}\,}}_{\mathcal{A}}(T_i) = {{\,\mathrm{res}\,}}_{\mathcal{A}}(T_j)$. Since S is finite (and so the number of states of $\mathcal{A}$ is finite), this implies that either $\tau$ is periodic or $\tau$ is ultimately periodic, where

• 1. $\tau$ is periodic if there exists a $p \in \mathbb {N}^+$, such that, for each $i \ge 0$, $T_i = T_{i+p}$ (the smallest such p is the period of $\tau$), and

• 2. $\tau$ is ultimately periodic if $\tau$ is not periodic, but there exists a $q \in \mathbb {N}$ such that the sequence $T_{q+1},T_{q+2}, \ldots$ is periodic (the smallest such q is the preperiod of $\tau$).

The dynamic behaviour of a rs $\mathcal{A}= (S,A)$ is often represented by a directed edge-labelled graph, called the transition graph of $\mathcal{A}$, where nodes are the states of $\mathcal{A}$ and labels of the edges are context sets (which are subsets of S representing the effects of the environment). Since in this paper we consider closed reaction systems (where context sets are empty), the transition graphs reduce to directed (unlabelled) graphs defined as follows:

Definition 5

Let $\mathcal{A}= (S,A)$ be a rs. The context-independent transition graph of $\mathcal{A}$ is a directed graph (V, E) such that $V = 2^S$ and, for $x,y \in V$, $(x, y) \in E$ if $y = {{\,\mathrm{res}\,}}_{\mathcal{A}}(x)$.

Since we consider only closed reaction systems we will use the shorter name, transition graph of $\mathcal{A}$, and denote it by ${{\,\mathrm{trg}\,}}(\mathcal{A})$. Obviously, each edge of ${{\,\mathrm{trg}\,}}(\mathcal{A})$ represents a one-step transition in a state sequence. Hence, there is a loop on a state T of $\mathcal{A}$ if and only if T is a fixed point of $\mathcal{A}$.

4 Dependency and positive dependency graphs

In this section, we introduce graphs representing important aspects of interactions between reactions of a reaction system.

Definition 6

Let $\mathcal{A}= (S,A)$ be a rs. The dependency graph of $\mathcal{A}$ is the graph (V, E), where $V = A$ and

$$\begin{aligned} E = \{(a,b) \in A \times A :P_a \cap M_b \ne \varnothing \} \quad . \end{aligned}$$

We will use ${{\,\mathrm{dg}\,}}(\mathcal{A})$ to denote the dependency graph of $\mathcal{A}$.

The dependency graph ${{\,\mathrm{dg}\,}}(\mathcal{A})$ represents some aspects of interactions between the reactions of $\mathcal{A}$. For example, when (a, b) is an edge of ${{\,\mathrm{dg}\,}}(\mathcal{A})$, then a interacts with b by providing b with (some of) its resources. Thus, if b is an isolated node of ${{\,\mathrm{dg}\,}}(\mathcal{A})$, then b is not involved in any interaction of $\mathcal{A}$: no reaction of $\mathcal{A}$ (including b) can provide b with some of its resources, and b does not provide any reaction c of $\mathcal{A}$ (including b) with some of the resources of c. In other words, neither b is influenced by any reaction of $\mathcal{A}$, nor b influences any reaction of $\mathcal{A}$. Such a reaction b is called an isolated reaction of $\mathcal{A}$. Clearly, an isolated reaction can be applied only in the first step of a state sequence of $\mathcal{A}$ if its reactant set is nonempty, or at each time step if its reactant set is empty.

Example 1

Let $\mathcal{A}= (S,A)$ be the reaction system with $S = \{x_1, x_2, \ldots , x_{12}\}$ and A consisting of the following reactions:

$$\begin{aligned}&a_1 = (\{x_1\}, \varnothing , \{x_1\}),&a_2 = (\{x_1\}, \varnothing , \{x_2\}),\\&a_3 = (\{x_3\}, \varnothing , \{x_{12}\}),&a_4 = (\{x_4\}, \{x_8\}, \{x_4\}), \\&a_5 = (\{x_8\}, \{x_{12}\}, \{x_5\}),&a_6 = (\{x_5\}, \varnothing , \{x_6\}), \\&a_7 = (\{x_6\}, \varnothing , \{x_7\}),&a_8 = (\{x_7\}, \varnothing , \{x_8\}), \\&a_9 = (\{x_7\}, \varnothing , \{x_9\}),&a_{10} = (\{x_{10}, x_9\}, \varnothing , \{x_6\}), \\&a_{11} = (\{x_{11}\}, \varnothing , \{x_2\}), \text { and}&a_{12} = (\{x_9\}, \{x_5, x_{12}\}, \{x_2\}). \end{aligned}$$

The dependency graph of $\mathcal{A}$ is given in Fig. 1.

We note that:

• $a_{11}$ is an isolated node. Hence, $a_{11}$ does not interact with any other reaction in A, including itself. Thus, $a_{11}$ can be enabled only in the initial state of a state sequence.

• $a_3$ is not isolated, but it does not have any incoming edges. Hence, also $a_3$ can be enabled only in the initial state of a state sequence.

• There are two loops in ${{\,\mathrm{dg}\,}}(\mathcal{A})$, they involve $a_1$ and $a_4$. They are there, because for both $a_1$ and $a_4$ their products intersect with their resources; in fact $P_{a_1} = R_{a_1}$ and $P_{a_4} = R_{a_4}$.

• There are two cycles in ${{\,\mathrm{dg}\,}}(\mathcal{A})$ which are not loops, $a_5,a_6,a_7,a_8$ and $a_7,a_9,a_{10}$. They share exactly one node, viz., $a_7$.

Fig. 1

The dependency graph ${{\,\mathrm{dg}\,}}(\mathcal{A})$ for the reaction system $\mathcal{A}$ of Example 1.

While ${{\,\mathrm{dg}\,}}(A)$ represents interactions between the reactions of $\mathcal{A}$, it doesn’t show which of those interactions are facilitating (reaction a produces at least one reactant of reaction b) and which are inhibiting (reaction a produces at least one inhibitor of reaction b). For our considerations, we will need the information about facilitating interactions and to this aim we introduce the notion of positive dependency graph.

Definition 7

Let $\mathcal{A}= (S,A)$ be a rs. The positive dependency graph of $\mathcal{A}$ is the graph (V, E), where $V = A$ and

$$\begin{aligned} E = \{(a,b) \in A \times A :P_a \cap R_b \ne \varnothing \} \end{aligned}$$

We will use ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ to denote the positive dependency graph of $\mathcal{A}$.

Thus, ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is a subgraph of ${{\,\mathrm{dg}\,}}(\mathcal{A})$ with the same set of nodes (viz., A), where an edge (a, b) from ${{\,\mathrm{dg}\,}}(\mathcal{A})$ is also an edge of ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ if and only if $P_a \cap R_b \ne \varnothing$.

Example 2

Let us consider the reaction system $\mathcal{A}$ from Example 1.

Its positive dependency graph, ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ depicted in Figs. 2, results from ${{\,\mathrm{dg}\,}}(\mathcal{A})$ by removing 4 edges:

• $(a_3,a_5)$, because $P_{a_3} = I_{a_5}$,

• $(a_3,a_{12})$, because $P_{a_3} \cap R_{a_{12}} = \varnothing$,

• $(a_5,a_{12})$, because $P_{a_5} \cap R_{a_{12}} = \varnothing$,

• $(a_8,a_4)$, because $P_{a_8} = I_{a_4}$.

Fig. 2

The positive dependency graph ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ for the reaction system $\mathcal{A}$ of Example 2, with the edges in ${{\,\mathrm{dg}\,}}(\mathcal{A})$ but not in ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ represented with dotted lines

All other edges (x, y) from ${{\,\mathrm{dg}\,}}(\mathcal{A})$ are also edges in ${{\,\mathrm{pdg}\,}}(\mathcal{A})$, because for all of them $P_x \cap I_y = \varnothing$ (hence $P_x \cap R_y \ne \varnothing$).

Based on the positive dependency graph, we define now important sequences of reactions, called fully facilitating cycles, and then, based on such cycles, we define fully facilitating positive dependency graphs.

Definition 8

Let $\mathcal{A}= (S,A)$ be a rs and let ${{\,\mathrm{pdg}\,}}(\mathcal{A}) = (A, E)$.

• (1) A cycle of ${{\,\mathrm{pdg}\,}}(\mathcal{A})$, $\alpha = a_0, \ldots , a_{n-1}, a_n = a_0$, $n \ge 1$, where, for $i \in \{0, \ldots , n-1\}$, $a_i = (R_i, I_i, P_i)$, is a fully facilitating cycle of $\mathcal{A}$ if, for each $i \in \{0, \ldots , n-1\}$, $P_i \supseteq R_{(i+1) \bmod n}$.

• (2) ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is fully facilitating if it is reduced, each cycle of it is a fully facilitating cycle, and each edge of E is included in a cycle.

Thus, each reaction in a fully facilitating cycle provides all reactants for the next one (modulo n). Then, ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is fully facilitating if it consists of (is a union of) fully facilitating cycles.

Example 3

Let us continue with ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ from Example 2. There are two cycles which are not loops: $C_1 = a_5, a_6, a_7, a_8, a_5$ and $C_2 = a_7, a_9, a_{10}, a_7$. We note that $C_1$ is fully facilitating, since $P_{a_5} \supseteq R_{a_6}$, $P_{a_6} \supseteq R_{a_7}$, $P_{a_7} \supseteq R_{a_8}$, and $P_{a_8} \supseteq R_{a_5}$. However, $C_2$ is not fully-facilitating, because $R_{a_{10}} = \{x_9, x_{10}\}$ and $P_{a_9} = \{x_9\}$, hence $R_{a_9} \not \subseteq P_{a_{10}}$. Then, there are two loops $C_3 = a_1,a_1$ and $C_4 = a_4,a_4$. Both of them are fully facilitating, as $R_{a_1} = P_{a_1}$ and $R_{a_2} = P_{a_2}$.

5 Strongly self-sustaining reaction systems

In this section, we define strongly self-sustaining reaction systems, which will be investigated in the sequel of the paper. We also establish a basic technical property for them.

To begin with, we define a subclass of reaction systems where the only interactions between reactions are facilitating.

Definition 9

A reaction systems $\mathcal{A}= (S,A)$ is nonblocking if $P_A \cap I_A = \varnothing$.

Thus, $\mathcal{A}$ is nonblocking if an application of any reaction from A in the current state will not inhibit an application of any reaction from A in the successor state.

Note that a nonblocking $\mathcal{A}$ may contain reactions (R, I, P) such that $I \ne \varnothing$. We allow it, because this can be useful in more general situations. Even though we deal in this paper with reaction systems which do not interact with their environments, such interactions are considered in the general model of interactive processes. Then, in nonblocking reaction systems interacting with their environments, reactions may be blocked (disabled) by entities provided by the environment (the so called context of interactive processes).

Obviously for a nonblocking reaction system $\mathcal{A}$, the dependency graph and the positive dependency graph coincide, ${{\,\mathrm{dg}\,}}(\mathcal{A}) = {{\,\mathrm{pdg}\,}}(\mathcal{A})$. In the sequel of this paper, we will use the term “positive dependency graph” (and the notation ${{\,\mathrm{pdg}\,}}(\mathcal{A})$) to emphasize that we deal here only with positive (facilitating) aspects of interactions.

If $\mathcal{A}= (S,A)$ is nonblocking and $\alpha = a_0, \ldots , a_{n-1},a_n = a_0$ is a fully facilitating cycle of $\mathcal{A}$, as defined in Definition 8(1), then also $P_i \cap I_{(i+1) \bmod n} = \varnothing$ holds. This means that each reaction of $\alpha$ enables the next one (modulo n) and so such a cycle can “run on its own” (without the need of intervention of other reactions). Accordingly, we call such a cycle self-sustaining.

Thus, the fully facilitating positive dependency graph of a nonblocking reaction system consists of self-sustaining cycles and, accordingly, such graphs are called self-sustaining.

Definition 10

Let $\mathcal{A}= (S,A)$ be a rs. We say that $\mathcal{A}$ is strongly self-sustaining, a ss-s reaction system for short, if A is nonblocking and ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is fully facilitating.

Note that for a ss-s reaction system $\mathcal{A}$ its positive dependency graph is reduced and so $\mathcal{A}$ does not contain isolated reactions. This is a natural choice, since we investigate the structure of interactions between reactions and (as discussed after Definition 6) isolated reactions do not participate in such interactions.

The following result provides basic constraints on the form of reactions (their reactant, inhibitor, and product sets) in a ss-s reaction system.

Theorem 1

Let $\mathcal{A}= (S,A)$ be a ss-s reaction system and let $G = {{\,\mathrm{pdg}\,}}(\mathcal{A})$. For every $b \in A$,the following holds:

$$\begin{aligned} (1)\,R_b \subseteq \bigcap _{a \in {{\,\mathrm{inc}\,}}_G (b)} P_a, \quad (2) I_b \cap R_A = \varnothing , \text { and } \quad (3) P_b \supseteq \bigcup _{c \in {{\,\mathrm{out}\,}}_G (b)} R_c. \end{aligned}$$

Proof

Let $b \in A$.

• ad (1) Since G is self-sustaining, b is included in a cycle of G and so ${{\,\mathrm{inc}\,}}_G(b) \ne \varnothing$ and ${{\,\mathrm{out}\,}}_G(b) \ne \varnothing$. Since each cycle of G is self-sustaining, $R_b \subseteq P_a$ for each $a \in {{\,\mathrm{inc}\,}}_G(b)$, and so $R_b \subseteq \bigcap _{a \in {{\,\mathrm{inc}\,}}_G(b)} P_a$.

• ad (2) By (1), for each $a \in A$, $R_a \subseteq P_A$. Since A is nonblocking, this implies $I_b \cap R_A = \varnothing$.

• ad (3) Since G is self-sustaining, $R_c \subseteq P_b$ for each $c \in {{\,\mathrm{out}\,}}_G(b)$, and so $\bigcup _{c \in {{\,\mathrm{out}\,}}_G(b)} R_c \subseteq P_b$. $\square$

6 Single cycle strongly self-sustaining reaction systems

Since for each ss-s reaction system its positive dependency graph is a union of cycles, the most basic form of these reaction systems is the one where the positive dependency graph consists of just one cycle. Such reaction systems will be considered in this section.

Definition 11

A ss-s reaction system $\mathcal{A}$ is a single cycle ss-s reaction system if ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ consists of one cycle only.

The length of the cycle of $\mathcal{A}$ is called the index of $\mathcal{A}$.

Example 4

Let $\mathcal{A}_1 = (S_1, A_1)$ be the reaction system with

$$\begin{aligned}&S_1 = \{x_5, x_6, x_7, x_8, x_{12}\} \text { and}&A_1 = \{a_5,a_6,a_7,a_8\}, \end{aligned}$$

where reactions $a_5, \ldots , a_8$ are defined as in Example 1. Clearly, $\mathcal{A}_1$ is a nonblocking reaction system and the cycle $a_5, \ldots , a_8, a_5$ is a self-sustaining cycle, thus $\mathcal{A}_1$ is a single cycle ss-s reaction system of index 4.

The basic technical property of single cycle ss-s reaction systems is given by the following lemma.

Lemma 1

Let $\mathcal{A}$ be a single cycle ss-s reaction system. For all $B_1, B_2 \subseteq A$such that $B_1 \ne B_2$, $P_{B_1} \ne P_{B_2}$.

Proof

Let ${{\,\mathrm{pdg}\,}}(\mathcal{A}) = G = (A, E)$ and let $B_1, B_2 \subseteq A$ with $B_1 \ne B_2$. Since the statement of the lemma obviously holds if either $B_1$ or $B_2$ is empty, we will assume that both $B_1 \ne \varnothing$ and $B_2 \ne \varnothing$. Since $B_1 \ne B_2$, the symmetric difference of $B_1$ and $B_2$ is non-empty. Thus, there exists a reaction $a \in (B_1 \cup B_2) - (B_1 \cap B_2)$; without loss of generality let’s assume that $a \in B_1$. Since G consists of one cycle only, a is a node of this cycle and its successor b in this cycle (meaning $(a,b) \in E$) is such that ${{\,\mathrm{inc}\,}}_G(b) = \{a\}$. Since $\mathcal{A}$ is a ss-s reaction system, by Theorem 1, $R_b \subseteq P_a$ and so $R_b \subseteq P_{B_1}$.

Assume now that $P_{B_1} = P_{B_2}$. This implies that $R_b \subseteq P_{B_2}$ and so there exists $c \in B_2$ such that $P_c \cap R_b \ne \varnothing$. Thus, $(c,b) \in E$. Since $a \notin B_2$, this implies that $|{{\,\mathrm{inc}\,}}_G(b)| \ge 2$, contradicting the fact that G consists of one cycle only.

Consequently $P_{B_1} \ne P_{B_2}$. $\square$

For a reaction system $\mathcal{A}= (S,A)$, its positive dependency graph records the facilitating interactions among the reactions of A. Based on ${{\,\mathrm{pdg}\,}}(\mathcal{A})$, we can trace the propagation of the facilitating influence of any subset B of A, using the facilitation functions and then represent the facilitation dynamics using the facilitation graph.

Definition 12

Let $\mathcal{A}= (S,A)$ be a rs with ${{\,\mathrm{pdg}\,}}(\mathcal{A}) = (A,E)$.

• 1. The facilitating function of $\mathcal{A}$, denoted by ${{\,\mathrm{fac}\,}}_{\mathcal{A}}$, is the function ${{\,\mathrm{fac}\,}}_{\mathcal{A}}:2^A \rightarrow 2^A$ such that, for each $B \subseteq A$, ${{\,\mathrm{fac}\,}}_{\mathcal{A}}(B) = \{a \in A :(b, a) \in E \text { for some } b \in B\}$.

• 2. The facilitation graph of $\mathcal{A}$, denoted by ${{\,\mathrm{fcg}\,}}(\mathcal{A})$, is the graph (V, F) such that $V = 2^A$ and $F = \{(X,Y) :X, Y \subseteq 2^A \text { and }{{\,\mathrm{fac}\,}}_{\mathcal{A}}(X) = Y\}$.

The propagation of the influence of sets of reactions is represented by facilitating sequences defined as follows.

Definition 13

Let $\mathcal{A}= (S,A)$ be a rs. A facilitating sequence of $\mathcal{A}$ is a countable sequence of subsets of A, $\varphi = B_0, B_1, \ldots$ such that, for each $i \ge 0$, $B_{i+1} = {{\,\mathrm{fac}\,}}_{\mathcal{A}}(B_i)$.

Thus, $\varphi = B_0, {{\,\mathrm{fac}\,}}_{\mathcal{A}}(B_0), {{\,\mathrm{fac}\,}}_{\mathcal{A}}^2(B_0), \ldots$, where the set $B_0$ is the initial set of $\varphi$. In fact, the facilitation sequences of $\mathcal{A}$ are just trajectories in ${{\,\mathrm{fcg}\,}}(\mathcal{A})$.

For a reaction system $\mathcal{A}= (S,A)$ and a state T of $\mathcal{A}$, knowing the set $B_T$ of reactions enabled by T allows one to know the successor state $T'$ of T, viz., $T' = \{P_b :b \in B_T\}$. Such translations are formally defined as follows.

Definition 14

Let $\mathcal{A}= (S,A)$ be a reaction system.

• 1. The product function of $\mathcal{A}$, denoted by ${{\,\mathrm{prd}\,}}_{\mathcal{A}}$, is the function ${{\,\mathrm{prd}\,}}_{\mathcal{A}}:2^A \rightarrow 2^S$ such that, for each $B \subseteq A$, ${{\,\mathrm{prd}\,}}_{\mathcal{A}}(B) = P_B$.

• 2. A product sequence of $\mathcal{A}$ is a countable sequence $\psi$ of states of $\mathcal{A}$, $\psi = P_0, P_1, \ldots$, such that there exists a facilitating sequence $\varphi$ of $\mathcal{A}$, $\varphi = B_0, B_1, \ldots$, where, for each $i \ge 0$, $P_i = P_{B_i}$.

By Lemma 1, when dealing with a single cycle ss-s reaction system $\mathcal{A}= (S,A)$, each subset $B \subseteq A$ is uniquely determined (coded by) its product set $P_B$. In this case, the facilitating sequences of $\mathcal{A}$ are in one-to-one correspondence with the product sequences of $\mathcal{A}$. In fact, it turns out that one can directly compute consecutive elements of a product sequence $P_0, P_1, \ldots$ using the result function ${{\,\mathrm{res}\,}}_{\mathcal{A}}$.

Theorem 2

Let $\mathcal{A}$ be a single cycle ss-s reaction system and let $\varphi = P_0, P_1, \ldots$ be a product sequence of $\mathcal{A}$.For each $i \ge 0$, $P_{i+1} = {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i)$.

Proof

Let $\mathcal{A}= (S,A)$ and let ${{\,\mathrm{pdg}\,}}(\mathcal{A}) = (A,E)$. Let $\psi = P_0, P_1, \ldots$ be a product sequence of $\mathcal{A}$ and let $\varphi = B_0, B_1, \ldots$ be the facilitating sequence of $\mathcal{A}$ such that $\psi$ is obtained from $\varphi$ by the product function of $\mathcal{A}$, i.e. for each $i \ge 0$, $P_i = {{\,\mathrm{prd}\,}}_{\mathcal{A}}(B_i)$.

Let $i \ge 0$. Then, $P_{i+1} = {{\,\mathrm{prd}\,}}_{\mathcal{A}}(B_{i+1}) = \bigcup _{b \in B_{i+1}} P_b$.

Let $b \in B_{i+1}$. Then, there exists $a \in B_i$ such that $(a,b) \in E$. Since $\mathcal{A}$ is an ss-s reaction system, b is enabled by $P_a$ and so $P_b \subseteq {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_a)$. Since $P_i = {{\,\mathrm{prd}\,}}_{\mathcal{A}}(B_i)$, $P_a \subseteq P_i$ and ${{\,\mathrm{res}\,}}_{\mathcal{A}}(P_a) \subseteq {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i)$, and because the rs is nonblocking all reactions enabled by $P_a$ are also enabled by $P_i$. Consequently $P_{i+1} = \bigcup _{b \in B_{i+1}} P_b \subseteq {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i)$.

Since $\mathcal{A}$ is a single cycle ss-s reaction system, for each $b \in B_{i+1}$, there exists a unique $a \in B_i$ such that $(a, b) \in E$ and this correspondence is a bijection of $B_{i+1}$ onto $B_i$.

Now let $x \in {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i)$. The $x \in P_b$ for some $b \in A$ enabled by $P_i$, hence $R_b \subseteq P_i$. Therefore, for some a belonging to $B_i$, $P_a \cap R_b \ne \varnothing$. This implies that $(a,b) \in E$. Thus, $b \in B_{i+1}$ and so $x \in P_{i+1}$. Therefore, ${{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i) \subseteq P_{i+1}$.

Consequently $P_{i+1} = {{\,\mathrm{res}\,}}_{\mathcal{A}}(P_i)$. $\square$

Thus, to investigate product sequences of single cycle ss-s reaction systems one can use the product transition graphs defined as follows.

Definition 15

Let $\mathcal{A}= (S,A)$ be a rs. The product transition graph of $\mathcal{A}$, denoted by ${{\,\mathrm{ptg}\,}}(\mathcal{A})$, is the directed graph (V, E) such that $V = \{X \in 2^S :X = P_B \text { for some } B \subseteq A\}$ and, for $X, Y \in V$, $(X,Y) \in E$ if and only if $Y = {{\,\mathrm{res}\,}}_{\mathcal{A}}(X)$.

Hence, ${{\,\mathrm{ptg}\,}}(\mathcal{A})$ is the subgraph of the transition graph of $\mathcal{A}$ resulting by restricting the nodes of ${{\,\mathrm{trg}\,}}(\mathcal{A})$ to the set $\{X \in 2^S :X = P_B \text { for some } B \subseteq A\}$. Clearly, the product transition graph is an important construct for representing the behaviour of reaction systems in general. In each state sequence $\tau = T_0, T_1, \ldots$ of a rs $\mathcal{A}$, after the first step the remaining sequence $T_1, \ldots$ is a trajectory in ${{\,\mathrm{ptg}\,}}(\mathcal{A})$.

According to Theorem 2, if $\mathcal{A}$ is a single cycle ss-s reaction system, then the diagram of Fig. 3 commutes.

Fig. 3

Correspondence between trajectories in ${{\,\mathrm{fcg}\,}}_{\mathcal{A}}$ and ${{\,\mathrm{ptg}\,}}_{\mathcal{A}}$

One obtains in this way an elegant correspondence between the trajectories in the facilitation graph of $\mathcal{A}$ (determined by ${{\,\mathrm{pdg}\,}}(\mathcal{A})$) and the trajectories in the product transition graph (determined by ${{\,\mathrm{res}\,}}_{\mathcal{A}}$). Note that (by Lemma 2) also the “inverse” diagram (where the arrows labelled by ${{\,\mathrm{prd}\,}}_{\mathcal{A}}$ are reversed and relabelled by ${{\,\mathrm{prd}\,}}_{\mathcal{A}}^{-1}$) commutes.

We will assume now that a specification of a single cycle ss-s reaction system $\mathcal{A}= (S,A)$ includes (next to S and A) also a fixed representation (sequence of nodes) ${{\,\mathrm{cyc}\,}}_{\mathcal{A}}$ of the cycle of $\mathcal{A}$. Hence, ${{\,\mathrm{cyc}\,}}_{\mathcal{A}}= a_0, \ldots , a_{n-1}, a_n = a_0$ for some $n \ge 1$ and $a_0, \ldots , a_{n-1} \in A$.

To establish a link with the combinatorial notion of a binary necklace (see, e.g. [35] and also Sect. 2 for the definition), we need the following notion.

Let $\mathcal{A}= (S,A)$ be a single cycle ss-s reaction system of index n, where ${{\,\mathrm{cyc}\,}}_{\mathcal{A}}= a_0, \ldots , a_{n-1}, a_n = a_0$. Then, the binary translation by $\mathcal{A}$ is the function ${{\,\mathrm{bin}\,}}_{\mathcal{A}}$ defined by ${{\,\mathrm{bin}\,}}_{\mathcal{A}}:2^A \rightarrow \{0,1\}^n$, where for each $B \subseteq A$, ${{\,\mathrm{bin}\,}}_{\mathcal{A}}(B) = \mathcal {X}_B(a_0), \ldots , \mathcal {X}_B(a_{n-1})$ (recall, see Sect. 2, that $\mathcal {X}_B$ is the characteristic function of $B \subseteq A$). Thus, the binary translation of B extends $\mathcal {X}_B$ to the string ${{\,\mathrm{cyc}\,}}_{\mathcal{A}}$. Note that ${{\,\mathrm{bin}\,}}_{\mathcal{A}}$ is a bijection and so the inverse function ${{\,\mathrm{bin}\,}}_{\mathcal{A}}^{-1} :\{0,1\}^n \rightarrow 2^A$ is well defined.

We prove now that the elementary rotations of binary translations of sets of reactions corresponds to applying the facilitation function to those sets.

Lemma 2

Let $\mathcal{A}= (S,A)$ be a single cycle ss-s reaction system of index n.For each $B \subseteq A$ the following diagram commutes:

Proof

Let $G = {{\,\mathrm{pdg}\,}}(\mathcal{A})$ and let ${{\,\mathrm{cyc}\,}}_{\mathcal{A}}= a_0, \ldots , a_{n-1}, a_n = a_0$. Let $i \in \{0, \ldots , n-1\}$.

Assume that $a_i \in B$, hence $\langle {{\,\mathrm{bin}\,}}_{\mathcal{A}}(B) \rangle _i = 1$. Then, $\langle {{\,\mathrm{elr}\,}}_n({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B) \rangle _{(i+1)\bmod n} = 1$ and so $a_{(i+1) \bmod n} \in {{\,\mathrm{bin}\,}}_{\mathcal{A}}^{-1}({{\,\mathrm{elr}\,}}_n({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B)))$. Since $\mathcal{A}$ is a single cycle ss-s reaction system, $a_i \in B$ implies ${{\,\mathrm{out}\,}}_G(a_i) = \{a_{(i+1)\bmod n}\}$. Thus, $a_{(i+1)\bmod n} \in {{\,\mathrm{fac}\,}}_{\mathcal{A}}(B)$.

Assume that $a_i \notin B$, hence $\langle {{\,\mathrm{bin}\,}}_{\mathcal{A}}(B) \rangle _i = 0$. Then, $\langle {{\,\mathrm{elr}\,}}_n({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B)) \rangle _{(i+1)\bmod n} = 0$ and so $a_{(i+1)\bmod n} \notin {{\,\mathrm{bin}\,}}_{\mathcal{A}}^{-1}({{\,\mathrm{elr}\,}}_n({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B))$. Since $\mathcal{A}$ is a single cycle ss-s reaction system, ${{\,\mathrm{inc}\,}}_G(a_{(i+1) \bmod n}) = \{a_i\}$. Thus, $a_i \notin B$ implies $a_{(i+1) \bmod n} \notin {{\,\mathrm{fac}\,}}_{\mathcal{A}}(B)$.

Hence,

$$\begin{aligned} {{\,\mathrm{fac}\,}}_{\mathcal{A}}(B) = {{\,\mathrm{fac}\,}}_{\mathcal{A}}({{\,\mathrm{bin}\,}}_{\mathcal{A}}^{-1}({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B))) = {{\,\mathrm{bin}\,}}_{\mathcal{A}}^{-1}({{\,\mathrm{elr}\,}}_n({{\,\mathrm{bin}\,}}_{\mathcal{A}}(B)) \end{aligned}$$

and consequently the diagram commutes. $\square$

Single cycle ss-s reaction systems result by imposing specific restrictions on their positive dependency graphs. These structural restrictions imply then specific behavioural properties expressed through their transition graphs.

Theorem 3

Let $\mathcal{A}$ be a single cycle ss-s reaction system of index n.Then ${{\,\mathrm{trg}\,}}(\mathcal{A})$ contains only cycles of length dividing n,and for each divisor of n, ${{\,\mathrm{trg}\,}}(\mathcal{A})$ contains a cycle of this length.

Proof

By Theorem 2 and Lemma 1, the product sequence of $\mathcal{A}$ and the facilitation sequences of $\mathcal{A}$ are in one-to-one correspondence (each product sequence of $\mathcal{A}$ can be uniquely translated into a facilitation sequence of $\mathcal{A}$ and the other way around).

By Lemma 2, facilitation sequences of $\mathcal{A}$ are in one-to-one correspondence with sequences of binary strings of length n, where the initial term corresponds to the initial set of reactions and the successor term is obtained by elementary rotations. The binary strings contained in such sequences are all and only the binary necklaces of length n.

It is well known (see, e.g. [35]) that, for each n, k is the cardinality of a binary necklace of length n if and only if k is a divisor of n.

Since (through ${{\,\mathrm{bin}\,}}_{\mathcal{A}}$) the subsets of A and binary strings of length n are in one-to-one correspondence, this implies the statement of the theorem. $\square$

Theorem 3 yields the following result for arbitrary ss-s reaction systems.

Corollary 1

Let $\mathcal{A}$ be a ss-s reaction system where ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is the union of k cycles, $k \ge 1$,where $n_1, \ldots , n_k$ are the lengths of those cycles. Then, C is a cycle of ${{\,\mathrm{trg}\,}}(\mathcal{A})$ if and only if the length of C equals $d_1 \cdot \ldots \cdot d_k$ for some divisors $d_1, \ldots , d_k$ of $n_1, \ldots , n_k$,respectively.

Finally, we establish the number of cycles in the transition graph of a single cycle ss-s reaction system. We use here the Euler totient function (see, e.g. [36]), denoted by $\varphi$, which, for each $d \in \mathbb {N}$, gives the number of integers $\varphi (d)$ that are relatively prime with respect to d.

Theorem 4

Let $\mathcal{A}$ be a single cycle ss-s reaction system of index n and let $D_n$ be the set of all divisors of n.Then, the number of distinct cycles in ${{\,\mathrm{trg}\,}}(\mathcal{A})$ equals

$$\begin{aligned} \frac{1}{n} \sum _{d \in D_n} \varphi (d) 2^{\frac{n}{d}} \end{aligned}$$

Proof

By Theorem 3, the number of cycles in ${{\,\mathrm{trg}\,}}(\mathcal{A})$ is the number of binary necklaces of length n, which (see [33]) equals

$$\begin{aligned} \frac{1}{n} \sum _{d \in D_n} \varphi (d) 2^{\frac{n}{d}} \end{aligned}$$

Hence, the theorem holds. $\square$

7 c-chains and flowers

In this section, we consider ss-s reaction systems for which positive dependency graphs consist of more cycles, which however form specific graph structures, viz., c-chains and flowers, which are defined as follows.

Definition 16

Let $G = (V, E)$ be a graph and let $\mathcal {C}$ be a set of n cycles in G for $n \ge 2$.

• 1. $\mathcal {C}$ is a c-chain if there exists a linear ordering $C_1, \ldots , C_n$ of the n cycles such that, for all $i \in \{1, \ldots , n-1\}$, $|C_i \cap C_{i+1} | = 1$ and, for all $j \in \{1, \ldots , n\}$ such that $j \notin \{i, i+1\}$, $|C_i \cap C_j| = 0$, and moreover $|C_n \cap C_1| \le 1$. If $|C_n \cap C_1| = 0$, then $\mathcal {C}$ is an open c-chain. If $|C_n \cap C_1| = 1$, then $\mathcal {C}$ is a closed c-chain.

• 2. $\mathcal {C}$ is a flower if $\left| \bigcap _{C \in \mathcal {C}} C \right| = 1$ and for all $C_1, C_2 \in \mathcal {C}$ with $C_1 \ne C_2$, it holds that $|C_1 \cap C_2| = 1$.

The cycles in a flower are referred to as petals.

Note that every set of two cycles $\mathcal {C} = \{C_1, C_2\}$ sharing a single node (i.e. $|C_1 \cap C_2| = 1$), is both a (closed) c-chain and a flower. Moreover, no set of three or more cycles is both a flower and a c-chain.

Now, we define reaction systems to be considered in this section.

Definition 17

Let $\mathcal{A}$ be a ss-s reaction system.

• 1. $\mathcal{A}$ is a c-chain ss-s reaction system if ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is a c-chain, and if ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ consists of k-cycles, $k \ge 2$, then we say that $\mathcal{A}$ is a k-cycles c-chain ss-s reaction system.

• 2. $\mathcal{A}$ is a flower ss-s reaction system if ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ is a flower, and if ${{\,\mathrm{pdg}\,}}(\mathcal{A})$ consists of k-cycles, $k \ge 2$, then we say that $\mathcal{A}$ is a k-petals flower ss-s reaction system.

Example 5

Let $\mathcal{A}_1$, $\mathcal{A}_2$, and $\mathcal{A}_3$ be the ss-s reaction systems defined as follows.

• 1. $\mathcal{A}_1 = (S_1, A_1)$, with $S_1 = \{x_1, \ldots , x_{10}\}$ and $A_1 = \{a_1, \ldots , a_9\}$, where

  $$\begin{aligned}&a_1 = (\{x_4\}, \varnothing , \{x_1\}),&a_2 = (\{x_1\}, \varnothing , \{x_2\}), \\&a_3 = (\{x_2\}, \varnothing , \{x_3, x_{10}\}),&a_4 = (\{x_{10}\}, \varnothing , \{x_4\}), \\&a_5 = (\{x_3\}, \varnothing , \{x_5, x_9\}),&a_6 = (\{x_5, x_9\}, \varnothing , \{x_2, x_6\}), \\&a_7 = (\{x_6\}, \varnothing , \{x_7\}),&a_8 = (\{x_7\}, \varnothing , \{x_8\}), \text { and} \\&a_9 = (\{x_8\}, \varnothing , \{x_5, x_9\}). \end{aligned}$$

• 2. $\mathcal{A}_2 = (S_2, A_2)$, with $S_2 = \{x_1, \ldots , x_{10}\}$ and $A_2 = \{a_1, \ldots , a_{10}\}$ where $a_1, a_2, a_3$ and $a_5, \ldots , a_9$ are defined as above (for $\mathcal{A}_1$), while $a_4$ and $a_{10}$ are defined by $a_4 = (\{x_{10}\}, \varnothing , \{x_4, x_8\})$, and $a_{10} = (\{x_9\}, \varnothing , \{x_{10}\})$.

• 3. $\mathcal{A}_3 = (S_3, A_3)$, with $S_3 = \{y_1, \ldots , y_4\}$ and $A_3 = \{b_1, \ldots , b_6\}$, where

  $$\begin{aligned}&b_1 = (\{y_3\}, \varnothing , \{y_1\}),&b_2 = (\{y_1\}, \varnothing , \{y_2\}), \\&b_3 = (\{y_2\}, \varnothing , \{y_3\}),&b_4 = (\{y_1\}, \varnothing , \{y_3\}), \\&b_5 = (\{y_1\}, \varnothing , \{y_4\}), \text { and}&b_6 = (\{y_4\}, \varnothing , \{y_3\}). \end{aligned}$$

Then, the positive dependency graph for $\mathcal{A}_1$, $\mathcal{A}_2$, and $\mathcal{A}_3$ are given in Figs. 4, 5, and 6, respectively.

Note that ${{\,\mathrm{pdg}\,}}(\mathcal{A}_1)$ is an open c-chain, ${{\,\mathrm{pdg}\,}}(\mathcal{A}_2)$ is a closed c-chain, and ${{\,\mathrm{pdg}\,}}(\mathcal{A}_3)$ is a flower.

Fig. 4

${{\,\mathrm{pdg}\,}}(\mathcal{A}_1)$

Fig. 5

${{\,\mathrm{pdg}\,}}(\mathcal{A}_2)$

Fig. 6

${{\,\mathrm{pdg}\,}}(\mathcal{A}_3)$

We show now that in a 2-cycles c-chain ss-s reaction system, the two cycles “synchronise” over time, as they mutually enable each other’s reactions in a pattern depending on their lengths.

Lemma 3

Let $\mathcal{A}= (S,A)$ be a 2 -cycles c-chain ss-s reaction system with cycles $C_1$ and $C_2$ of lengths m and n,respectively. Let $T \subseteq S$ be such that at least one reaction from either $C_1$ or $C_2$ is enabled by T.Then, the facilitating sequence $\varphi = B_0, B_1, \ldots$,where $B_0$ is the set of all reactions enabled by T,is ultimately periodic, with some preperiod $q \in \mathbb {N}$ and period p such that $p \le \gcd (m,n)$ and $\bigcup _{i=1}^p B_{q+i} = A$.

Proof

Let $C_1 = a_0, \ldots , a_{m-1}, a_m = a_0$ and $C_2 = b_0, \ldots , b_{n-1}, b_n = b_0$.

We may assume without loss of generality that $a_0 = b_0$ and $T \subseteq S$ is such that $a_0 = b_0$ is enabled by T. This can be assumed since in each state where at least one reaction in either $C_1$ or $C_2$ is enabled, $a_0 = b_0$ will be enabled after at most $\max \{m, n\}$ steps (because $\mathcal{A}$ is a ss-s reaction system). Furthermore, we assume that no reaction except for $a_0 = b_0$ is enabled by $T_0$. If that is not the case, then the reasoning in the rest of the proof provides an upper bound on the length of the period rather than an exact value.

Let $\ell = {{\,\mathrm{lcm}\,}}(m,n)$ be the least common multiple of m and n. Let us consider $T_\ell = {{\,\mathrm{res}\,}}_{\mathcal{A}}^\ell (T_0)$ and the reactions enabled by it. First of all, notice that because $a_0 = b_0$ is enabled by $T_0$, $T_{\ell -1}$ is the first state in which $a_{m-1}$ and $b_{n-1}$ are both enabled and thus $T_\ell$ is the first state after $T_0$ in which $a_0 = b_0$ is enabled at the same time by both the reactions in $C_1$ and in $C_2$. Concerning other reactions of $C_2$ enabled by $T_\ell$, we note that $a_0 = b_0$ has also been enabled by cycle $C_1$ every m time steps, enabling reaction $b_1$ at the successive time step. Since every step $0< h < \ell$ is not a multiple of both m and n, if $a_0 = b_0$ is enabled by $T_h$, then this is due to the fact that at step $h-1$ either $a_{m-1}$ or $b_{n-1}$ was enabled (but not both). In the case $a_{m-1}$ was the reaction enabled by $T_{h-1}$, at time step $h+1$ the reaction $b_1$ becomes enabled by $T_{h+1}$ and it would not become enabled without the interactions between the two cycles $C_1$ and $C_2$. That is, every m steps in all steps before $\ell$, cycle $C_1$ is enabling a reaction of $C_2$ that would not have been enabled at that step by $C_2$ alone. Therefore, cycle $C_2$ contains $\ell / m$ enabled reactions in $T_\ell$. Since ${{\,\mathrm{lcm}\,}}(m, n) = \frac{m n}{\gcd (m,n)}$, $C_2$ contains $n / \gcd (m,n)$ enabled reactions. By repeating the above reasoning starting in $T_1 = {{\,\mathrm{res}\,}}_{\mathcal{A}}(T_0)$ and considering the reactions enabled by $T_{\ell + 1} = {{\,\mathrm{res}\,}}_{\mathcal{A}}^{\ell +1}(T_0)$, we observe that in $T_{\ell +1}$ there are $n /\gcd (m,n)$ enabled reactions from $C_2$ that, if $\gcd (m,n) > 1$, are all distinct from the ones enabled by $T_\ell$.

By reasoning as above, we conclude that in each of the states $T_\ell , T_{\ell + 1}, \ldots ,$ $T_{\ell + \gcd (m,n) -1}$ there are $n/\gcd (m,n)$ enabled reactions that are all distinct, yielding together n distinct enabled reactions (i.e. all reactions from $C_2$) every $\gcd (m,n)$ steps.

Symmetrically, analysing the reactions of $C_1$ enabled by $T_\ell , \ldots , T_{\ell + \gcd (m,n) -1}$, we obtain that m distinct reactions (i.e. all reactions from $C_1$) are enabled every $\gcd (m,n)$ steps.

Consequently, we conclude that the facilitating sequence $\varphi = B_0, B_1, \ldots$ is ultimately periodic for some preperiod q and a period $p \le \gcd (m,n)$ such that $\bigcup _{i=1}^p B_{q+i} = A$. $\square$

We will generalize now Lemma 3 to k-cycles c-chain ss-s reaction systems for $k \ge 2$.

Lemma 4

Let $\mathcal{A}= (S,A)$ be a k -cycles c-chain ss-s reaction system with cycles $C_1, \ldots , C_k$ of lengths $n_1, \ldots , n_k$, respectively. Let $T \subseteq S$ be such that at least one reaction in one of $C_1, \ldots , C_k$ is enabled by T.Then, the facilitating sequence $\varphi = B_0, B_1, \ldots$,where $B_0$ is the set of all reactions enabled by T,is ultimately periodic, with some preperiod $q \in \mathbb {N}$ and a period p such that $p \le \gcd (n_1, \ldots , n_k)$ and $\bigcup _{i=1}^p B_{q+i} = A$.

Proof

By induction on the number of cycles. For two cycles the statement holds by Lemma 3.

Now, suppose that the statement holds for $k \ge 2$ and assume that $\mathcal{A}$ is a $(k+1)$-cycles c-chain ss-s reaction system with cycles $C_1, \ldots , C_k, C_{k+1}$ of length $n_1, \ldots , n_k, n_{k+1}$, respectively. By induction hypothesis, every reaction in $C_1, \ldots , C_k$ is eventually enabled every $\gcd (n_1, \ldots , n_k)$ steps and also every reaction in $C_2, \ldots , C_{k+1}$ is eventually enabled every $\gcd (n_2, \ldots , n_{k+1})$ steps. Thus, every cycle $C_2, \ldots , C_k$ has each of its reactions eventually enabled every $\gcd (\gcd (n_1, \ldots , n_k), \gcd (n_2, \ldots , n_{k+1}))$ steps, which is equal to $\gcd (n_1, \ldots , n_{k+1})$ steps. We now only need to show that also $C_1$ and $C_{k+1}$ have all of their reaction enabled every $\gcd (n_1, \ldots , n_{k+1})$ steps.

If we consider the last two cycles $C_k$ and $C_{k+1}$, then, by Lemma 3, each reaction in $C_k$ and $C_{k+1}$ is eventually enabled every $\gcd (n_k, n_{k+1})$ steps. However, since $C_k$ has all of its reaction enabled every $\gcd (n_1, \ldots , n_{k+1})$ steps, we can apply the reasoning of the proof of Lemma 3 to conclude that every reaction in $C_{k+1}$ is enabled every $\gcd (n_1, \ldots , n_{k+1})$ steps. Analogously, we conclude that every reaction in $C_1$ is enabled every $\gcd (n_1, \ldots , n_{k+1})$ steps. Consequently, all reaction are eventually enabled at least once every $\gcd (n_1, \ldots , n_{k+1})$ steps. Hence, the lemma holds. $\square$

In particular, if the lengths of all cycles of a c-chain have the gcd equal to 1, we get exactly 2 fixed points in the transition graph of $\mathcal{A}$.

Theorem 5

Let $\mathcal{A}$ be a k -cycles c-chain ss-s reaction system with the lengths of the cycles $n_1, \ldots , n_k$.If $\gcd (n_1, \ldots , n_k) = 1$,then $\mathcal{A}$ has exactly two fixed points.

Proof

Let $\mathcal{A}= (S,A)$ and let $T \subseteq S$.

• 1. Assume that T is such that there is at least one reaction in A enabled by T. We show now that the state sequence beginning with T reaches a fixed point, which equals $\bigcup _{a \in A}P_a$. Since $\gcd (n_1, \ldots , n_k) = 1$, by Lemma 4 the facilitating sequence $\varphi = B_0, B_1, \ldots$, where $B_0$ is the set of all reactions enabled by T, is such that $B_{q+i} = A$, for all $i \ge 1$, where q is the preperiod of $\varphi$. This means that the state sequence $\tau = T_0, T_1, \ldots$, where $T_0 = T$, is such that $T_{(q+1)+i} = \bigcup _{a \in A}P_a$, for all $i \ge 1$. Hence, $\bigcup _{a \in A}P_a$ is a fixed point of $\mathcal{A}$.

• 2. Assume that T is such that no reaction of A is enabled by T. Then, the state sequence $\tau = T_0, T_1, \ldots$, where $T_0 = T$, is such that $T_i = \varnothing$ , for all $i \ge 1$.

Since either T enables at least one reaction from A or it doesn’t, $\mathcal{A}$ has exactly two fixed points: $\bigcup _{a \in A} P_a$ and $\varnothing$. $\square$

We move now to consider flower ss-s reaction systems and demonstrate that the result analogous to Theorem 5 holds for them. First we need a lemma analogous to Lemma 4.

Lemma 5

Let $\mathcal{A}= (S,A)$ be a k -petals flower ss-s reaction system with the set of cycles of lengths $n_1, \ldots , n_k$.Let $T \subseteq S$ be such that at least one reaction in one of the cycles is enabled by T.Then, the facilitating sequence $\varphi = B_0, B_1, \ldots$,where $B_0$ is the set of all reactions enabled by T,is ultimately periodic, with some preperiod $q \in \mathbb {N}$ and a period p such that $p \le \gcd (n_1, \ldots , n_k)$ and $\bigcup _{i=1}^p B_{q+i} = A$.

Proof

By induction on the number of cycles. For two cycles the statement holds by Lemma 3.

Now, suppose that the statement holds for $k \ge 2$ and assume that $\mathcal{A}$ is a $(k+1)$-petals flower ss-s reaction systems with the set of cycles $\mathcal {C}$ of lengths $n_1, \ldots , n_k, n_{k+1}$. Without loss of generality, we may consider an arbitrary linear order $\langle C_1, \ldots , C_k,C_{k+1} \rangle$ of $\mathcal {C}$.

Let $i,j \in \{1, \ldots , k+1\}$ with $i \ne j$. Thus, $C_i$ and $C_j$ are distinct cycles in $\mathcal {C}$, with the sets $\mathcal {C} - \{C_i\}$ and $\mathcal {C} - \{C_j\}$ both distinct and containing exactly k cycles. By induction hypothesis, every reaction in $\mathcal {C} -\{C_i\}$ and $\mathcal {C}- \{C_j\}$ is eventually enabled every $\gcd (n_1, \ldots , n_{i-1}, n_{i+1}, \ldots , n_{k+1})$ steps and every $\gcd (n_1, \ldots , n_{j-1}, n_{j+1}, \ldots , n_{k+1})$ steps. Thus, every reaction in $\mathcal {C} - \{C_i,C_j\}$ is enabled every $\gcd (n_1, \ldots , n_{k+1})$ steps. Since this holds for any choice of i and j, all reaction are eventually enabled at least once every $\gcd (n_1, \ldots , n_{k+1})$ steps. Hence, the lemma holds. $\square$

Theorem 6

Let $\mathcal{A}$ be a k -petals flower ss-s reaction system with the lengths of the cycles $n_1, \ldots , n_k$.If $\gcd (n_1, \ldots , n_k) = 1$,then $\mathcal{A}$ has exactly two fixed points.

Proof

We proceed analogously to the proof of Theorem 5, replacing the use of Lemma 4 by the use of Lemma 5. $\square$

8 Discussion

In a reaction system, reaction a can influence reaction b by producing either some reactants of b (hence facilitating b) or some inhibitors of b (hence inhibiting b) or both. In this paper, we have considered the facilitating aspects of such interactions.

To this aim, we have restricted ourselves to nonblocking reaction systems (which allow for facilitation only) and then focused on the research line often referred to as “structure vs behaviour”, where one investigates how structural properties of a system influence its behaviour. In this paper, the structure of a reaction system is formalized through its positive dependency graph which captures the facilitating interactions. The behaviour of a reaction system is formalized, in the standard way, through its transition graph.

We have defined specific structural properties of reaction systems through specific properties of their positive dependency graph and demonstrated how they imply specific behavioural properties, expressed through their transition graphs.

The research presented here is certainly worth to be continued in both directions:

• (1) investigating reaction systems based on facilitation, and

• (2) investigating how the structure of reactions, hence properties of the positive dependence graph, influence the behaviour, hence properties of the transition graph.

• ad.(1) Investigating facilitating reaction systems is natural, also from the point of view of other models of interactions of biochemical reactions. For example, chemical reaction networks, well-accepted and intensely investigated model (see, e.g. [9]) is based on facilitation only. Some “obvious” research topics for facilitating reaction systems are:

  • Properties of their state sequences, and in particular comparing those properties with the properties of state sequences of general reaction systems, which are well understood by now (see, e.g. [10, 11, 20, 28, 30,31,32]).

  • Complexity properties, and, again, comparing them with the complexity properties of general reaction systems, which are well understood by now (see, e.g. [16, 23,24,25]).

  • As pointed out in Sect. 5 already, reactions in a nonblocking reaction systems may have nonempty set of inhibitors. This becomes interesting when one considers the general framework of reaction systems where the environment can control the behaviour of reaction systems, a well-investigated research area (see, e.g. [7, 8, 27, 29]). One can now investigate reaction systems, where the inhibitors can be “activated” by the environment only, i.e. the so-called context sequences. This may lead to new classes of behaviour, in-between the context-independent and arbitrary interactive processes.

• ad.(2) Concerning the “structure vs behaviour” research line for facilitating reaction systems, interesting and perhaps really challenging topic is to find interesting structures of positive dependency graphs (interesting in the sense that they would imply interesting properties of transition graphs).

  • Our current proposal (and the topic we investigate now) is to consider “DAG-cycles” structure of positive dependency graphs. Such a graph is obtained by considering as a template a connected directed acyclic graph and substituting in it each node by a cycle. Consequently in these graphs cycles do not share nodes but rather they are connected by directed edges, which form sort of “bridges” between them.