Communicating reaction systems are new variants of networks of reaction systems where the components communicate with each other by sending products or reactions. Reaction system, a mathematical formalism inspired by the biochemistry of the living cell, focuses on an abstract set-based representation of chemical reactions via facilitation and inhibition. In this paper we examine bio-inspired properties of communicating reaction systems such as steady state and mass conservation.
The concept of a reaction system (an R system) was
introduced by A. Ehrenfeucht and G. Rozenberg as a formal
model of interactions between biochemical reactions. The
interested reader is referred to [
A reaction system consists of a finite set of objects that
represent chemicals and a finite set of triplets that
represent chemical reactions. Each reaction consists of three
nonempty finite sets: the set of reactants, the set of
inhibitors, and the set of products. The set of reactants and
the set of inhibitors are disjoint. Let T be a set of reactants.
A reaction is enabled for T and it can be performed if all of
its reactants are present in T and none of its inhibitors are
in T . When the reaction is performed, then the set of its
reactants is replaced by the set of its products. All enabled
reactions are applied in parallel. The set of products
obtained by the reactions performed in parallel is the union
of the sets of products that were obtained by the reactions
that were enabled for T . For further details on reaction
systems consult [
Reaction systems are qualitative models, opposed to membrane systems (P systems) that are quantitative ones. The model of reaction systems focuses only on the presence or absence of the chemical species, and does not consider their amounts. Multiple reactions that have common reactants do not interfere. All of the reactions that are enabled at a certain step are performed simultaneously. Another feature of reaction systems which makes them different from other bio-inspired computational models, as for example, P systems, is the lack of permanency: the state of the system consists of the products of those reactions that were performed in the last step. Those reactants that were not involved in any reaction disappear from the system. This property is widely used in the theory of R systems.
R systems have been studied in detail over the last
sixteen years. One interesting topic of their study is the
theory of networks of reaction systems [
There are various research topics in the domain of
reactions systems. One type of investigations focuses on the
mathematical properties of reaction systems, for example
functions defined by reaction systems, state sequences,
effect of limited resources, cycles and connections to
propositional logic. For details consult [
In this paper we examine some of these biologically inspired properties like steady state, conserved sets in the frame of communicating reaction systems with direct communication. A system is said to be in a steady state if it does not experience any changes over time. Studying steady states is a relevant topic in many fields of science. Similarly, also mass conservation plays important role in many scientific areas.
The paper is organized as follows. In Section 2 we introduce basic notions and notations concerning reactions and reaction systems. In Section 3 we recall communicating reaction systems with direct communication and in Section 4 we define different properties of cdcR systems which communicate products. Finally, we provide conclusions and few suggestions for further research in Section 5. 2
For basic notions of formal languages and computation
theory the reader is encouraged to consult [
In this section we recall the basic notions concerning
reaction systems, following [
Let S be a finite nonempty set; S is called the background set. A reaction r over S is a triplet (R; I; P) where R; I; P are nonempty subsets of S such that R \ I = 0/ . Sets R; I; P are called the set of reactants, the set of inhibitors, and the set of products of r, respectively; they can also be denoted by Rr ; Ir , and Pr . In this case the reaction is denoted by r : (Rr ; Ir ; Pr ).
A finite nonempty set of reactions over the same background set is a reaction system. Thus, a reaction system is an ordered pair A = (S; A); where S is a background set and A is a finite nonempty set of reactions over S.
Now we recall how reaction systems operate over a set of reactants.
Let S be a background set, T S, r : (Rr ; Ir ; Pr ) be a reaction over S, and let A be a finite set of reactions over S. Then
T and Ir \ T = 0/ ; 2. the result of applying r to T , denoted by resr (T ), equals Pr if r is enabled for T and is equal to the emptyset, 0/, otherwise; 3. the result of applying A to T , denoted by resA(T ), is
Sr2A resr (T ).
That is, a reaction r is enabled for a set of reactants T if T contains all reactants of r and none of its inhibitors. If r is enabled for T , then its products contribute to the successor state of the reaction system. For T S, enA(T ) denotes the set of reactions in A that are enabled for T . It is easy to see that resA defines a function on 2S, called the result function.
The state sequence of a reaction system A with initial state T is given by successive iterations of the result function: (resnA (T ))n2N = (T; resA (T ); res2A (T ); :::):
In this section we briefly recall the most important
concepts concerning a variant of communicating reaction
systems (cdcR(p) systems, for short), where the reaction
systems directly communicate with each other. The concept
was introduced in [
Now we recall the notion of a cdcR(p) system from [
A cdcR system communicating by products (a cdcR(p) system, for short), of degree n, n 1, is an (n + 1)-tuple D = (S; A1; : : : ; An), where
S is a finite nonempty set, the background set of D; Ai, 1 i
n, is the i-th component of D, where – Ai is a finite nonempty set of extended reactions of type pc (pc-reactions, for short). – Each pc-reaction r of Ai is of the form r : (Rr ; Ir ; Pr ); where Rr and Ir are nonempty subsets of S and Rr \ Ir = 0/ , and Pr Pr f1; : : : ; ng, Pr is a nonempty subset of S. Rr , Ir , Pr are called the set of reactants, the set of inhibitors, and the set of products with targets. A pair (b; j), 1 j n in Pr means that product b is communicated to component A j.
The name pc-reaction refers to reaction communicating products.
The notions and notations concerning reaction systems
are extended to cdcR(p) systems, we recall them from [
A pc-reaction r : (Rr ; Ir ; Pr ) is enabled for a set U S if Rr U and Ir \ U = 0/ as in case of standard reaction systems; this fact is denoted by enr (U ).
Let D = (S; A1; : : : ; An) be a cdcR(p) system and let U S. Then, we define resAi (U ) = fb j (b; j) 2 Pr ; r 2 Ai; enr (U ); 1 j ng.
We consider result all of the products obtained by performing the pc-reactions, including those ones that will leave the component by communication.
cdcR(p) systems operate by transitions, i.e., by changing their states. A state of a cdcR(p) system D = (S; A1; : : : ; An) is an n-tuple (D1; : : : ; Dn) where Di S, 1 i n; Di is called the state of component Ai, 1 i n: Notice that Di can be empty set.
A transition in D means that every component of the cdcR(p) system performs all of its enabled pc-reactions on the current set of reactants and then communicates the obtained products to their target components, indicated in the corresponding pc-reaction. Notice that the same product from several components can be communicated to a component and by several pc-reactions.
The sequence of transitions starting with the initial state forms the state sequence in D. Observe that for a given initial state there is only one state sequence in D, i.e. the sequence of transitions is deterministic.
Let D = (S; A1; : : : ; An), n 1, be a cdcR(p) system. The sequence D¯ 0; : : : ; D¯ j; : : : is called the state sequence of D starting with initial state D¯ 0 if the following conditions are met: For every D¯ j, j 0 where D¯ j = (D1; j : : : ; Di; j; : : : ; Dn; j); 1 i n it holds that D¯ j+1 = (D1; j+1 : : : ; Di; j+1; : : : ; Dn; j+1) with Di; j+1 = [1 k nComk!i(resAk (Dk; j)) where Comk!i(resAk (Dk; j)) = fb j (b; i) 2 Pr ; r : (Rr ; Ir ; Pr ) 2 Ak; enr (Dk; j)g. Sequence Di;0; Di;1; : : : is said to be the state sequence of component Ai of D; 1 i n.
The state sequence does not end if resAi (Di; j) is the empty set, since products can be communicated to the component in the coming steps.
Let D = (S; A1; : : : ; An), n 1, be a cdcR(p) system and let D¯ 0; D¯ 1 : : : ; D¯ i; : : : be the state sequence of D starting with D¯ 0. Then every pair (D¯ i; D¯ i+1), i 0 is said to be a transition in D and is denoted by D¯ i =) D¯ i+1.
In [
The statement was proved by a so-called flattening
technique (frequently used in the theory of P systems) where
the notation of the reactants at the nodes indicates the
location of the object (entity) as well. The reader interested
in the details is referred to [
The reaction system A obtained in this way is called
the flattened reaction system or a flattened version of D.
We recall the definition from [
Definition 1. Let D = (S; A1; : : : ; An), n 1, be a cdcR(p) system. Let reaction system A = (S0; A0) be defined as follows. Let S0 = f[x; i] j x 2 S; 1 i ng be the background set of A . For any pc-reaction r : (Rr ; Ir ; Pr ) of component Ai, we define reaction r0 : (Rr0 ; Ir0 ; Pr0 ) of A where Rr0 = f[x; i] j x 2 Rr g, Ir0 = f[y; i] j x 2 Ir g, Pr0 = f[x; k] j (x; k) 2 Pr ; 1 k ng. No other reaction is in A0. Then A is called the flattened reaction system of D. 4
In [
We first start with steady states from [
Definition 2. . Let A = (S; A) be a reaction system. We say that a nonempty set W S is a steady state of A if resA (W ) = W:
Notice that this property means that no change can be experienced in this state in a process of evolution, i.e. if A enters state W , then all elements following W in the state sequence will be equal to W .
Before defining the steady state for cdcR(p) systems,
we make some remarks. As it was shown in [
Now we define the notion of a steady state of a cdcR(p) system.
Definition 3. Let D = (S; A1; : : : ; An), n 1, be a cdcR(p) system and let D¯ W = (W1; : : : ;Wn) be a state of D. Then D¯ W is said to be a steady state of D if for D¯ W0 = (W10; : : : ;Wn0) where DW =) D0w it holds that Wi = Wi0 for i, 1 i n.
Notice that for any Wi, 1 i n, resAi (Wi) consists of all products obtained by the performed pc-reactions, including those ones which will leave the component by communication. Thus, Wi 6= resAi (Wi) may hold.
Next we will present a statement concerning a connection between steady states of cdcR(P) systems and steady states of their flattened reaction systems.
Theorem 2. Let D = (S; A1; : : : ; An), n 1, be a cdcR(p) system and let A = (S0; A0) be its flattened reaction system. Let W be a steady state of A . Then there exist mappings gi : 2S0 ! 2S, 1 i n and a state D¯ W = (W1; : : : ;Wn) of D such that D¯ W = (W1; : : : ;Wn) is a steady state of D and gi(W ) = Wi.
Let D¯ W = (W1; : : : ;Wn) be a steady state of D. Then there exist mappings hi : 2S ! 2S0 , 1 i n and W n
S0 such that W = [i=1hi(Wi) is a steady state of A .
Proof sketch. To prove the statement, we consider the definition of the flattened reaction systems of D. It is given by A = (S0; A0), where S0 = f[x; i] j x 2 S; 1 i ng is the background set and for any pc-reaction r : (Rr ; Ir ; Pr ) of component Ai of D, 1 i n, we define reaction r0 : (Rr0 ; Ir0 ; Pr0 ) of A where Rr0 = f[x; i] j x 2 Rr g, Ir0 = f[y; i] j x 2 Ir g, Pr0 = f[x; k] j (x; k) 2 Pr ; 1 k ng. No other reaction is in A0. It is easy to see that if we define gi such way that it orders to each reactant [x; i] in A a reactant x at component Ai, and by hi we order to each reactant x of component Ai a reactant [x; i] of A , then we obtain from state W of A state D¯ W = (W1; : : : ;Wn) of D and reversely. Furthermore if W is a steady state, then D¯ W will be a steady state as well, and reversely. We leave the details to the reader.
Next we provide an example.
Example 1. Let D = (S; A1; A2; A3) be a cdcR(p) system where S = fa; b; cg and components A1, A2 and A3 are defined as follows:
A1 = fr1 : (fa; bg; fcg; f(a; 1); (b; 1)g)g; A2 = fr2 : (fb; cg; fag; f(b; 3); (c; 2)g);
r3 : (fa; cg; fbg; f(a; 3); (c; 2)g)g; A3 = fr4 : (fa; cg; fbg; f(a; 2); (c; 3)g);
r5 : (fb; cg; fag; f(b; 2); (c; 3)g)g:
Let D¯ 0 = (fa; bg; fb; cg; fa; cg) be the initial state of D. For component A1, it is clear from the product f(a; 1); (b; 1)g that after each transition the state does not change, it always remains fa; bg. On the other hand, states of components A2 and A3 keep changing due to the product with in-built communication.
The above example inspires us to distinguish between so-called "strong steady states" of a cdcR(p) system where the states of the components do not change or so-called "weak steady states" where the support of the entire state remain unchanged but the states of the particular components may change. The support of the state of a cdcR(p) system is the set of those elements of the background set that appear in some of the states of the particular components either as reactant or elements of a product (or both).
The study of weak steady states is an interesting open problem. Interesting questions are decidability problems as well. For example, it is known that given a reaction system A = (A; S), deciding if there exists a nonempty steady state W S is an NP-complete problem.
In the following we deal with one other important property, called mass-conservation. First, we recall some auxiliary notions.
For a reaction system A = (S; A), the support set of A is defined as supp(A ) = R [ P where R = S Rr and r2A P = S Pr .
r2A
Next we define the notion of the support set for a component of a cdcR(p) system and then for the system itself. Definition 4. The support set for a particular component Ai of a cdcR(p) system D = (S; A1; : : : ; An), 1 i n, is defined as supp(Ai) = Ri [ P¯i, where Ri = fa j a 2 Rr ; r 2 Ai; a 2 Sg and P¯i = fa j (a; j) 2 Pr ; r 2 Ai; a 2 S; 1 j ng.
For a cdcR(p) system D = (S; A1; : : : ; An), n 1 the supn port set of D is defined as supp(D) = S supp(Ai): i=1
We recall the notion of a conserved set of a reaction
system [
Definition 5. Let A = (S; A) be a reaction system, then a set M supp(A ) is conserved if for any W supp(A ), M \ W 6= 0/ if and only if M \ resA (W ) 6= 0/ :
M has a special property, namely if it has a joint subset with a state W , then it has a joint subset with the state obtained after applying all enabled reactions to W as well.
This definition cannot be directly implemented for cdcR(p) systems. Instead, we define a notion to describe conservation of sets.
Definition 6. Let D = (S; A1; : : : ; An), n 1 be a cdcR(p) system and let Mi S, 1 i n. We say that Mi supp(Ai) is a conserved set for component Ai, i; 1 i n if the following holds. For any two states D¯ = (D1; : : : ; Dn) and D¯ 0 = (D01; : : : ; D0n) where D¯ =) D¯ 0, it holds that if there exists Wi Mi such that Wi Di, then there exists Wi0 Mi such that Wi0 D0i holds.
The above way of conservation concerns a particular component. Obviously, such conserved sets can appear at several components.
As in the case of steady states, we can find a connection between conserved sets of cdcR(p) systems and their flattened reaction systems. Let D = (S; A1; : : : ; An), n 1 be a cdcR(p) system and let A = (S0; A0) be its flattened reaction system. By the construction of A it can easily be seen that if Wi Di and Wi0 D0i, then W¯ i = f[a; i] j a 2 Wig and W¯ i0 = f[b; i] j b 2 Wi0g are subsets of D¯ i = f[c; i] j c 2 Dig and D¯ 0i = f[d; i] j d 2 D0ig, respectively. It would be useful to develop such notion that describe a distributed manner of conservation in the entire system. In this paper we proposed steady states and mass conservation of communicating reaction systems by product communication. Using the concepts of the corresponding flattened reaction systems, we attempted to describe the ideas beyond the definitions. It will be a promising and useful research to study the concepts of invariants, stationary processes, elementary fluxes and periodicity of cdcR(p) systems. Another interesting research could be studying on all these bio-inspired properties for cdcR(r) (cdcR systems communicating reactions) and comparing all respective properties with cdcR(p). 6
The work of Erzsébet Csuhaj-Varjú was supported by the National Research, Development, and Innovation Office - NKFIH, Hungary, Grant no. K 120558. The work of Pramod Kumar Sethy was supported by project ” Integrált kutatói utánpótlás-képzési program az informatika és számítástudomány diszciplináris területein”, EFOP 3.6.3VEKOP-16-2017-00002, a project supported by the European Union and co-funded by the European Social Fund.