1 Introduction
Reaction systems, introduced in 2004, are well-known qualitative models of biochemical interactions Ehrenfeucht et al. (
2004). A reaction represents a chemical reaction and it is a triple of finite non-empty sets of objects: the set of reactants, the set of inhibitors, and the set of products. The set of reactants and the set of inhibitors are disjoint. A reaction system is a finite set of reactions.
A reaction can be performed on a set of reactants if each reactant of the reaction is present and each inhibitor is absent in the given reactant set. When a reaction is performed, then the set of its reactants is changed to the set of its products. All reactions of the reaction system that can be performed on a given set of reactants have to be performed in parallel. Those reactants that are not involved in any reaction, disappear from the set of reactants.
In the last two decades, several properties of reaction systems have been studied and several extensions have been introduced. Functions defined by reaction systems, properties of state sequences of reaction systems, the effect of bounded resources, and connections to propositional logic were examined in Ehrenfeucht et al. (
2011); Salomaa (
2013,
2012). Reaction systems can also be used as a modeling framework. For checking temporal properties of reaction systems, a temporal logic was introduced in Meski et al. (
2015). Biologically inspired properties of reaction systems have been examined in Azimi et al. (
2014,
2016); Azimi (
2017)
Reaction systems can also be organized in a distributed communication framework. In this case, reactions are located in nodes of virtual graphs or, simply, an
n-tuple of reaction systems is given. The reactions in these systems work in a synchronized manner and interact with each other by distribution and communication protocols. Such interaction can take place either by obtaining input from a separate environment or by communicating reactants, products, or reactions to each other. Examples of such constructs are distributed reaction systems Meski et al. (
2019), extended distributed reaction systems Ciencialová et al. (
2022,
2023), networks of reaction systems Bottoni et al. (
2020), and communicating reaction systems with direct communication Csuhaj-Varjú et al. (
2020). Networks of reaction systems, distributed reaction systems, and communicating reaction systems were related in Aman (
2022,
2023).
An extended distributed reaction system (the EDRS for short), introduced in Ciencialová L et al. (
2022,
2023), is a slightly modified variant of the distributed reaction system model studied in Meski et al. (
2019). An EDRS consists of a finite number of reaction systems defined over a common background set (set of objects). These reaction systems operate in a synchronized manner. In each step, a so-called context automaton provides a set of reactants for each reaction system which is added to the current reactant set (the current state) of this reaction system. This set of reactants is called a context. After that, all enabled reactions are performed on the obtained new set of reactants (the union of the original reactant set and the context) and the interactive process is going to be repeated.
In Csuhaj-Varjú et al. (
2020), two variants of communicating reaction systems with direct communication (cdcR systems for short) were introduced, namely, the cdcR(p) system where products are communicated and the cdcR(r) systems where reactions are communicated. In the case of cdcR(p) systems, after performing the enabled reactions on its current reactant set, the component sends copies of certain products to certain target components. The target nodes and the products to be communicated are given together with the reaction. Thus, a computation step consists of a reaction and after that a communication. In the case of cdcR(r) systems, if a reaction is successfully performed by a component, then its copies are sent to predefined target components. Notice that these variants of distributed reaction systems realize communication by command, i.e., by performing the reactions, the components initiate the sending of specific products/reactants to other components.
In this paper, we introduce a new variant, called a distributed reaction system with communication by request (a qDRS for short). In this case, after performing the enabled reactions, the component may request the state of some other components, given together with the reaction. This query is represented by query symbols, each component is assigned to one query symbol and vice versa. Provided that the components addressed by a query have no query symbol in their states, a copy of the products in the state of the component is sent to the component that issued the query. This communication process continues until the state of every component is query-free.
If the communication process does not end with only query-free states, then the computation aborts. This model was inspired by parallel communicating grammar systems Păun and Kari (
1989); Csuhaj-Varjú et al. (
1994), a grammatical framework for distributed communicating systems of Chomsky grammars. In the case of parallel communicating grammar systems, the state of a component corresponds to the string generated by a grammar and the performing of a reaction corresponds to the application of a production.
In this paper, we examine distributed reaction systems with communication by request and extended distributed reaction systems and their relations to each other.
We prove that every distributed reaction system with communication by request can be represented by a reaction system. More precisely, to a given qDRS we can give a reaction system such that the sequence of its query-free states can be obtained by a simple mapping from the state sequence of the reaction system. Analogous results were presented for cdcR(p) systems and cdcR(r) systems in Csuhaj-Varjú et al. (
2020). The result implies that the power of qDRS does not exceed the boundaries of the power of reaction systems.
Next, we show that to every qDRS a simulating EDRS can be given, i.e. their state sequences correspond to each other (they are almost the same). According to the reverse direction, to every EDRS of a certain restricted type, a simulating qDRS can be constructed. For the general case, such a simulation result cannot hold since, contrary to reaction systems and qDRS, extended distributed reaction systems can also be non-deterministic (when their context-automaton is non-deterministic).
In two previous papers Ciencialová L et al. (
2022,
2023), languages were assigned to extended distributed reaction systems and representations of well-known language classes were presented with these models (the class of right-linear simple matrix languages and the class of recursively enumerable languages).
In this paper, we define the agreement language of the EDRS. We show that the class of agreement languages of extended distributed systems is equal to the class of languages of multihead nondeterministic finite automata. We discuss the languages of qDRS and we state that the agreement language of any distributed reaction system with communication by request is in a certain subregular language class.
Our paper is organized as follows. In Sect.
2, we present the basic notions concerning reaction systems and distributed reaction systems. In Section 3, we present the notion of a distributed reaction system with communication by request and statements concerning qDRS, including the comparisons to extended distributed reaction systems. In Section 4, we introduce the notion of the agreement language of an EDRS and prove the equality of the class of agreement languages of extended distributed systems and the class of languages of multihead nondeterministic finite automata. We also discuss the agreement language of qDRS. We close the paper with conclusions and suggest topics for research.
3 Distributed reaction systems with communication by request
In this section we introduce the concept of the distributed reaction system with communication by request. Unlike cdcR(p) systems, where the components send copies of the obtained products to certain target components, the components of these systems receive copies of products from certain other components upon request. A request, marked by a query (symbol), means that the issuing component requests the state of the target component. The target component sends the copies of the products in its state to the querying components provided that its state does not contain a query. This communication protocol also expresses hidden coordination of the function of the components. As mentioned above, the idea was inspired by parallel communicating grammar systems Păun and Kari (
1989); Csuhaj-Varjú et al. (
1994).
If no confusion arises, we may use term reaction instead of extended reaction.
The extended reaction of the form \((R,I,\{q\})\) initiates the communication process. Notice that every such reaction introduces only one query and does not provide any product which is an element of the background set. Furthermore, self-query is not allowed.
A state of \(\Delta \) is an n-tuple \({{\bar{D}}}=(D_1,\dots , D_n)\), where \(D_i\subseteq S\cup K\) and \(D_i\) is a non-empty set called the state of component \(A_i\) in \({\bar{D}}\). The set \(D_i\) is called query-free if \(D_i\cap K=\emptyset \), \(1\le i \le n\). If every \(D_i\), \(1\le i \le n\), is query-free, then \({\bar{D}}\) is called query-free.
We define the (direct) transition between two states in \(\Delta \) as follows.
We give a short explanation to the definition. If no query occurs in the state of any component, then the components perform all of their enabled reactions. The new state of the component will be the set of the obtained products. This is the case of transition of type (a).
If there is at least one component with a query, then transition of type (b) is performed. Suppose that a component with at least one query is \(A_i\) and its state is \(D_i\). Then the new state \(D'_i\) of \(A_i\) consists of the union of the following sets: the set of reactants in \(D_i\) which are elements of S, the set of queries that request the state of such components which have non-query-free state, and the union of the states of the components with query-free state where a query to the component was issued. The states of the query-free components remain unchanged.
No transition of type (a) is possible if there exists a component with a state having a query as an element.
The transitive (and reflexive) closure of \(\rightarrow \), \(\vdash \), and \(\Longrightarrow \) is denoted by \(\rightarrow ^+\), \(\vdash ^+\), and \(\Longrightarrow ^+\) (\(\rightarrow ^*\), \(\vdash ^*\), and \(\Longrightarrow ^*\)) respectively.
A sequence of transitions is said to be a communication, if it is a sequence of communication steps. If the resulting state, \(\sigma _r\), is query-free, then the communication is successful. Since \(\Delta \) contains n components, the length of every successful communication is at most \(n-1\).
Notice that a sequence of transitions resulting in a state
\(\bar{D}_h\) is halting in the following cases:
-
The state \({\bar{D}}_h\) of \(\Delta \) is query-free and no reaction step can be performed (i.e. there is no component with an enabled extended reaction), or
-
\({\bar{D}}_h\) is not query-free and no communication step can be performed.
Note that if the transition sequence of a qDRS is halting, then it is finite. This follows from the fact that every qDRS has a finite state space, so any trajectory in it is either periodic (not halting) or finite (and halting).
A transition sequence is called terminating if it ends with a query-free state and is halting. A finite transition sequence of \(\Delta \) starting from an initial state \({{\bar{D}}}_0=(D_{0,1},\dots , D_{0,n})\) is called a computation.
Next, we show that every qDRS can be represented by a reaction system. More precisely, to the state sequence \(\gamma \) of a qDRS in the strict sense, starting from a given initial state, we can give a reaction system working without environmental influence and an initial state of this reaction system such that \(\gamma \) can be obtained as a mapping of a certain subsequence \(\kappa \) of the state sequence of the reaction system.
In order to avoid confusion, in the following theorem and in its proof, we use slightly different notations for reaction systems than usual, but their meaning is obvious from the context.
Proof
The idea of the proof is the following. The reaction system \(\mathcal{A}\) simulates each reaction step and each communication sequence in \(\Delta \) in n steps. The elements of \(\Sigma \) represent the reactants and the queries of \(\Delta \) together with their locations, i.e., with reference to the component where they are located. In addition, the current step number of the n-step simulation phase is indicated.
Let
\(\Sigma =S'\cup S'' \cup K'\cup \{X\}\) where
\(S',S'',K'\) and
X are defined as follows.
$$\begin{aligned} S'= & {} \{[a,i]\mid a\in S, 1\le i\le n\}, \\ S''= & {} \{[a,i]^{(j)}\mid a\in S, 1\le i, j\le n\}, \end{aligned}$$
where index
i refers to the number of the component where
a is located and
j refers to the number of the step in the simulating transition sequence.
$$\begin{aligned} K'=\{[Q_k,i]^{(j)} \mid 1\le i,j, k\le n, i\ne k\}, \end{aligned}$$
where reactant
\([Q_k,i]^{(j)}\) in
\({\mathcal {A}}\) represents a query of component
\(A_i\) of
\(\Delta \) that requests the state of component
\(A_k\). Index
j indicates that the simulation of the corresponding transition is in the
jth step. In addition, we also have
$$\begin{aligned} X \in \Sigma \setminus (S'\cup S''\cup K'). \end{aligned}$$
Since the maximal length of a communication in
\(\Delta \) is
\(n-1\), any reaction step and any communication in
\(\Delta \) will be simulated by
n transitions in
\({{\mathcal {A}}}\).
Reactions of \({{\mathcal {A}}}\) are given in the following manner.
If (
R,
I,
P) is a (query-free) reaction in component
\(A_i\) of
\(\Delta \), we add the following reactions to
\({{\mathcal {R}}}\):
$$\begin{aligned} (\{[a,i]\mid a\in R\} , \{[b,i]\mid b\in I\}\cup K', \{[c,i]^{(1)} \mid c\in P\}) \end{aligned}$$
(1)
if
\(P\cap K=\emptyset \). Otherwise, if
\(P\cap K\ne \emptyset \), we have
$$\begin{aligned}&(\{[a,i]\mid a\in R\} , \{[b,i]\mid b\in I\}\cup K', \nonumber \\&\quad \{[c,i]^{(1)} \mid c\in (P\cap S)\}\cup \{[Q_{k_1},i]^{(1)}, \dots , [Q_{k_l},i]^{(1)}\}) \end{aligned}$$
(2)
where
\(\{Q_{k_1}, \dots , Q_{k_l}\}=P\cap K\) and
\(i\ne k_h\),
\(1\le h\le l\).
We also add the following reactions to
\({{\mathcal {R}}}\):
$$\begin{aligned} (\{[a,i]^{(j)}\}, \{X\}, [a,i]^{(j+1)}), \end{aligned}$$
(3)
for
\(1\le j\le n-1\), and
$$\begin{aligned} (\{[a,i]^{(n)}\}, \{X\}, \{[a,i]\}), \end{aligned}$$
(4)
where
\(a\in S\).
The above reactions simulate reaction (R, I, P) of component \(A_i\) of \(\Delta \).
First, the enabled reactions are performed and the non-query products (certain elements of S) and possibly queries are indexed (see (1) and (2)). After that, a procedure consisting of n steps follows that preserves the non-query products while the communication takes place. During these n steps the non-query products (elements of S) are indexed by an increasing number until index n is obtained. After that the indexed version of the product is changed to the original one.
To simulate the communication steps, we add the following reactions to
\({\mathcal {R}}\):
$$\begin{aligned} { (\{[Q_{k},i]^{(j)}, [a,k]^{(j)}\}, \cup _{l=1}^n\{[Q_{l},k]^{(j)}\},\{[a,i]^{(j+1)}\}),} \end{aligned}$$
(5)
for
\(a\in S\),
\(1\le j\le n-1\),
\(1\le i,k\le n\), where
\(i\ne k\).
These reactions represent the case when component \(A_i\) requests the actual state of component \(A_k\) provided that its state is query-free. Such a reaction checks whether or not the query exists and the state of \(A_k\) contains an element a of S (these are the reactants). It also checks whether or not there is a query in the state of \(A_k\) (the set of inhibitors), and then adds an a to the state of \(A_i\). Notice if a is an element of the state of \(A_i\), then this reaction implies no change in the state of \(A_i\).
We also add the following reactions to
\({\mathcal {R}}\):
$$\begin{aligned} { (\{[Q_{k},i]^{(j)},[Q_{l},k]^{(j)}\}, \{X\}, \{[Q_{k},i]^{(j+1)}\}),} \end{aligned}$$
(6)
for
\(1\le j\le n-1\),
\(1\le i,k,l\le n\), where
\(i\ne k\) and
\(k\ne l\).
These reactions represent the case when component \(A_i\) requests the actual state of component \(A_k\) but the state of \(A_k\) is not query-free. These reactions check whether or not both \(A_i\) and \(A_k\) issue a query (the set of reactants), the inhibitor is irrelevant (singleton \(\{X\}\)), and then the query by \(A_i\) remains unsatisfied, thus the index of the corresponding symbol increases by 1 (the product). Notice that for a given query represented by \([Q_{k},i]^{(j)}\) either reactions from the first set of reactions or reactions from the second set of reactions are enabled, but not reactions from both sets.
Now we show that the statement of the theorem holds.
We first define mappings \(h_{i}: \Sigma \rightarrow S\cup K\), \(1\le i\le n\).
Let \(h_i([a,i])=a\) for \([a,i]\in S'\), \(h_i([a,i]^{(j)})=a\) for \([a,i]^{(j)}\in S''\), and \(h_i([Q_{k},i]^{(j)})=Q_k\), \(1\le i,j,k \le n\), \(i\ne k\).
We extend \(h_i\), \(1\le i \le n\), to subsets of \(\Sigma \) as follows. For every nonempty subset U of \(S'\) and for every nonempty subset V of \(S''\), let \(h_i(U)=\{h_i([a,i])\mid [a,i]\in U\}\) and let \(h_i(V)=\{h_i([a,i]^{(j)})\mid [a,i]^{(j)}\in V\}\). For every nonempty subset Z of \(K'\) let \(h_i(Z)= \{(h_i([Q_k,i]^{(j)}) \mid [Q_k,i]^{(j)} \in Z\}\), \(1\le i,j,k \le n\), \(i\ne k\).
Finally, let \(h_i(X)=X\), thus \(h_i(\{X\})=\{X\}\), and \(h_i(\emptyset )=\emptyset \), for \(1\le i \le n\).
Let \({{\bar{D}}}_0=(D_{0,1}, \dots , D_{0,n})\) be the initial state of \(\Delta \) and let \(W_0=\{[a,i]\mid a\in D_{0,i}, 1\le i\le n\}\) be the initial state of \({{\mathcal {A}}}\). It can immediately be seen that for every i, \(h_i(W_0)=D_{0,i}\) holds.
Suppose that the statement holds for \({{\bar{D}}}_j=(D_{j,1},\dots , D_{j,n})\), \(j\le i\) and \(D_{j,l}\subseteq S\), \(1\le l\le n\). (Note that \({{\bar{D}}}_j\) is an element of the state sequence of \(\Delta \) in the strict sense.) That is, \(h_l(W_{j(n+1)})=D_{j,l}\), where \(W_0,W_1\dots , W_r, \dots \), \(r\ge 1\) is the state sequence of \({{\mathcal {A}}}\). We show that for \({{\bar{D}}}_{i+1}=(D_{i+1,1}, \dots , D_{i+1,n})\) it holds that \(h_l(W_{(i+1)(n+1)})=D_{i+1,l}\).
Let us consider the state \({{\bar{D}}}_i=(D_{i,1}, \dots , D_{i,n})\). Since \(h_l(W_{i(n+1)})=D_{i,l}\), where \(D_{i,l}\subseteq S\), we know that \(W_{i(n+1)}\) consists of reactants of the form [a, l], \(1\le l\le n\), where \(a\in S\). The next state \({\bar{D}}'_i=(D'_{i,1}, \dots , D'_{i,n})\) in the state sequence (not in the strict sense) of \(\Delta \) will be either query-free or it will have at least one occurrence of a query. In the query-free case, starting from \(W_{i(n+1)}\), computation steps are performed with reactions of type (1), then of type (3), (4). After performing the corresponding reactions of type (1), we obtain that \(W_{i(n+1)+1}\) will consists of reactants of the form \([a,l]^{(1)}\), \(1\le l\le n\) and \(W_{i(n+1)+1}\) corresponds to \({{\bar{D}}}'_i=(D'_{i,1}, \dots , D'_{i,n})\). After this step, \(n-1\) reaction steps follow (by using reactions of type (3)), where only the upper index of the reactants is increased by one until index n is obtained. Observe that these steps are codes of \(W_{i(n+1)+1}\), thus they do not simulate any reaction or communication in \(\Delta \). In the next step, all reactants of the form \([a,l]^{(n)}\) are changed to [a, l] (by reactions of type (4), thus the simulation of the reaction step is completed.
In the non query-free case, computation steps are performed on \(W_{i(n+1)}\) with reactions of type (2), then of type (5), (6), and (3), (4) in this order. Suppose that \(W_{i(n+1)+1}\) corresponds to \({{\bar{D}}}'_i=(D'_{i,1}, \dots , D'_{i,n})\) in \(\Delta \), were at least one \(D'_l\), \(1\le l\le n\) contains a query. Then \(W_{i(n+1)+1}\) consists of reactants of the form \([a,i]^{(1)}\) and \([Q_k,i]^{(1)}\) where \([a,i]^{(1)}\) represents reactant a at component \(A_i\) and \([Q_k,i]^{(1)}\) represents a query from component \(A_i\) to component \(A_k\). By definition of the reactions of type (2), exactly the elements of \(D'_{i,l}\), \(1\le l\le n\) are represented in \(W_{i(n+1)+1}\). Suppose that the queries in \({{\bar{D}}}'=(D'_{i,1}, \dots , D'_{i,n})\) can be satisfied in l communication steps, where \(1\le l\le n\). Then, by using reactions of type (5) and (6) all communication steps in \(\Delta \) are simulated. In each communication step, if \([Q_{k},i]^{(j)}\) can be satisfied, i.e., component \(A_k\) does not contain a query, then \([Q_{k},i]^{(j)}\) is replaced by the set of all reactants of the form \([a,k]^{(j+1)}\) that are present (reactions of type (5)), if \([Q_{k},i]^{(j)}\) cannot be satisfied, i.e., the state of component \(A_k\) contains at least one query, then the upper index \([Q_{k},i]^{(j)}\), j is increased by one (reactions of type 6). The upper index of the other reactants of the form \([a,i]^{(j)}\) is also increased by one (reactions of type (3)). Then, as before, either reactions of type (5) or reactions of type (6) are performed until no reactant of the form \([Q_{k},i]^{(j)}\) is present. If the length of communication is less than \(n-1\), then as in the previous case by reactions (3) and (4), the upper indices of the reactants are increased until n is obtained and after then all reactants are changed to be of the form [a, i]. In this way the communication is simulated. We can see that any computation in \(\Delta \) is simulated by \({{\mathcal {A}}}\), and the state sequence of \(\Delta \) in the strict sense can be obtained by mappings of a certain subsequence of the state sequence of \({\mathcal {A}}\). \(\square \)
We show that to any qDRS with an initial state we can give an EDRS with an initial state such that the state sequence of the qDRS and the state sequence of the components of the EDRS coincide.
Proof
Let \(\Gamma \) have the following components: \({\Delta '}=(\Sigma ,\mathcal{A'})\) where \({{\mathcal {A}}'}=(A'_1,\dots , A'_n)\), \(n\ge 1,\) is the distributed reaction system of \(\Gamma \) and \(M=(Q,C,R, q_0,F)\) is the context automaton.
Before providing the components of \(\Gamma \), we discuss the computation in \(\Delta \). It is easy to see that for any state \((D_1,\dots ,D_n)\) of \(\Delta \), we can determine the only state \((D'_1,\dots ,D'_n)\) of \(\Delta \) where \((D_1,\dots ,D_n)\Longrightarrow (D'_1,\dots ,D'_n)\) holds. Our construction will be based on this observation.
We define the components of M together with the reaction sets \(A'_i\), \(1\le i\le n\), of \(\Delta '\) of \(\Gamma \).
For every state \((D_1,\dots ,D_n)\) of qDRS \(\Delta \), \([D_1,\dots ,D_n]\) is a state of M and M has no more elements. The initial state of M is \([D_{0,1},\dots , D_{0,n}]\), where \({{\bar{D}}}_0=(D_{0,1},\dots , D_{0,n})\) is the initial state of \(\Delta \). The set of final states F of M consists of those elements \([D_1,\dots ,D_n]\) of Q where \((D_1,\dots ,D_n)\) is a query-free state of \(\Delta \) and there is no state \((D'_1,\dots ,D'_n)\) of \(\Delta \) where \((D_1,\dots ,D_n)\Longrightarrow (D'_1,\dots ,D'_n) \) holds.
The background set
\(\Sigma \) is the union of the following disjoint sets:
$$\begin{aligned} \Sigma= & {} S \cup K\cup \{X_{[D_1,\dots , D_n]}\mid (D_1,\dots , D_n) \, \text{ is } \text{ a } \text{ state } \text{ of } \Delta \}\cup \{Z\} \end{aligned}$$
where
Z is an auxiliary element, different from all other elements of
\(\Sigma \).
Now, we define the elements of R, the set of transitions of M.
If
\((D_1,\dots ,D_n)\Longrightarrow (D'_1,\dots ,D'_n)\) is a transition in
\(\Delta \) then we add
$$\begin{aligned} ([D_1,\dots ,D_n],(X_{[D_1,\dots ,D_n]},\dots ,X_{[D_1,\dots ,D_n]}),[D'_1,\dots ,D'_n]) \end{aligned}$$
to
R. Notice that
\(X_{[D_1,\dots ,D_n]}\) is not in
\(S\cup K\);
\(\{X_{[D_1,\dots ,D_n]}\} \) is the context added to the components.
Now we define the reactions of components of \(\mathcal{A'}=(A'_1,\ldots ,A'_n)\) of \(\Gamma \).
(1) If
\((D_1,\dots ,D_n)\Longrightarrow (D'_1,\dots ,D'_n)\) is a transition in
\(\Delta \) and
\((D_1,\dots ,D_n)\) is query-free, then we add the reaction
$$\begin{aligned} (\{X_{[D_1,\dots ,D_n]}\}\cup D_i, S \setminus D_i, D'_i) \end{aligned}$$
to
\(A'_i,\ 1\le i\le n\). Since
\(D'_i=res_{A_i}(D_i)\), the above reaction simulates the transition in
\(\Delta \). Notice that symbol
\(X_{[D_1,\dots ,D_n]}\) indicates which transition is to be performed, thus transitions cannot be mixed.
(2) If
\((D_1,\dots ,D_n)\vdash (D'_1,\dots ,D'_n)\) is a transition in
\(\Delta \) where
\((D_1,\dots ,D_n)\) is not query-free, then we add the following reactions to
\(A'_i\). We add
$$\begin{aligned} (\{X_{[D_1,\dots ,D_n]}\}\cup (D_i\cap S), S \setminus D_i, D_i\cap S) \end{aligned}$$
since those elements which are reactants in
\(\Delta \) need to remain unchanged.
For all
k such that
\(D_k\cap K=\emptyset \), we also add
$$\begin{aligned} (\{X_{[D_1,\dots ,D_n]}, Q_{k}\}, \{Z\}, D_k). \end{aligned}$$
If component
i asked for the state of component
k (and
\(D_k\) is query-free), then
\(D_k\) is added to the state of component
i and the query disappears. Notice that
\(X_{[D_1,\dots ,D_n]}\) plays a crucial role in this reaction and that we can decide whether or not
\(D_k\) contains symbol representing a query.
For the case when
\(D_k\) contains at least one query, we add
$$\begin{aligned} (\{X_{[D_1,\dots ,D_n]}, Q_{k}\}, \{Z\}, \{Q_k\}). \end{aligned}$$
As in the previous case, the role of
\(X_{[D_1,\dots ,D_n]}\) is significant.
Now we prove that the state sequence of \(\Delta \) and the state sequence of the components of \(\Gamma \) coincide.
If the initial state of
\(\Gamma \) is
$$\begin{aligned} ([D_{0,1},\ldots ,D_{0,n}], (X_{[D_{0,1},\ldots ,D_{0,n}]},\ldots ,X_{[D_{0,1},\ldots ,D_{0,n}]}), (D_{0,1},\ldots ,D_{0,n})), \end{aligned}$$
then by definition, the initial state of
\(\Delta \) is equal to the initial state of (the components of)
\(\Gamma \). Assume that the equality of the two state sequences (the statement of the theorem) holds for up to the
ith pair of states, where
\(i\ge 1\). We show that the statement also holds for the
\((i+1)\)th pair.
Suppose that the ith element of the state sequence \(\kappa \) in \(\Delta \) is \((D_1,\dots ,D_n)\) and \((D_1,\dots ,D_n)\) is also the ith element of the state sequence of \(\Gamma \). Then either there exists a unique state \((D'_1,\dots ,D'_n)\) in \(\Delta \) where \((D_1,\dots ,D_n)\Longrightarrow (D'_1,\dots ,D'_n)\) holds, or the computation cannot be continued.
If \((D_1,\dots ,D_n)\) is query-free, then for \((D'_1,\dots ,D'_n)\) it holds that \(D'_j=res_{A_j}(D_j)\). Let us consider now the case where \((D_1,\dots ,D_n)\) is the ith element of the state sequence of \(\Gamma \).
In this case, there exists a transition
$$\begin{aligned}{}[D_1,\dots ,D_n],(X_{[D_1,\dots ,D_n]},\dots ,X_{[D_1,\dots ,D_n]}),[D''_1,\dots ,D''_n]) \end{aligned}$$
in the automaton
M. Then, by the construction of
M, see above,
\(D'_j=D''_j\) holds for
\(1\le j\le n\).
Let us suppose now that \((D_1,\dots ,D_n)\), the ith element of \(\kappa \) is not query-free, i.e., there exists at least one component \(A_l\) such that \(D_l\) contains a query. By definition, for every such \(D_l\), reaction \((\{X_{[D_1,\dots ,D_n]}\}\cup (D_l\cap S), S {\setminus } D_l, D_l\cap S)\) is applied, that is, those elements which are reactants in \(\Delta \) remain unchanged. Furthermore, reaction \((\{X_{[D_1,\dots ,D_n]}, Q_{k}\}, \{Z\}, D_k)\) for \(D_k\cap K\ne \emptyset \) is also applied, if possible. This means that component \(A_i\) asked for the state of component \(A_k\) provided that \(D_k\) is query-free. In this case \(D_k\) is added to the state of component \(D_l\) and the reactant representing the query disappears from the state. If \(D_k\) contains at least one query, then \((\{X_{[D_1,\dots ,D_n]}, Q_{k}\}, \{Z\}, \{Q_k\})\) is applied, i.e., \(Q_k\) remains unchanged.
The procedure is repeated until the new state will be free from reactants representing a query. Notice the synchronized behaviour of the components. Since the performed reactions simulated the communication, we obtain that the statement holds for the \((i+1)\)th pair of the two sequences as well. \(\square \)
Notice that the components of both EDRS and qDRS receive contexts (sets of reactants) from outside. The components of the EDRS obtain context from the context automaton, and the components of the qDRS obtain contexts by queries from other components. Since the context automaton can be non-deterministic, it is possible that different context sets are added to the components of an EDRS during transitions even when they start in the same configuration. In qDRS, however, this cannot happen, as the components are deterministic in the sense that the results obtained by any transition is completely determined by the starting configuration. Furthermore, in the case of the qDRS, the components are allowed to communicate with more than one component, while the components of an EDRS are in communication only with the context-automaton. In order to construct a qDRS which simulates an EDRS, we should resolve this difference.
Although we do not have a solution for the general case, we show a connection between star-type qDRS and a special simple variant of EDRSs.
A qDRS \(\Delta \) is called star-type if there is only one component to which a query can be issued.
Next we show that if an EDRS with a given initial state is very simple (in the sense defined above), then we can give a qDRS and an initial state such that the state sequence of the qDRS and the state sequence of the EDRS correspond to each other.
Proof
Let \({\Gamma }=({\Delta },M )\) be an extended distributed reaction system where \({\Delta }=(S,{{\mathcal {A}}})\), \({{\mathcal {A}}}=(A_1,\dots , A_n)\), \(n\ge 1 \), the context automaton is \(M=(Q,C,R, q_0, F)\), and let \(\sigma _0=(q_0, (C_{0,1},\dots ,C_{0,n}), (D_{0,1},\dots , D_{0,n}))\) be the initial state of \(\Gamma \).
Let
$$\begin{aligned} R=\{tr_{q}\mid tr_{q}=(q, (C_{1}\dots ,C_{n}),r)\in R \text{ for } \text{ some } q,r\in Q\} \end{aligned}$$
be the set of transitions in
M. Notice that the initial state of
M is
\(q_0\), and there is a finite set
\(F\subseteq Q\) of final states of
M. Note also, that since
\(\Gamma \) is very simple, each transition in
\(\Gamma \) either has no successor transition or it has only exactly one successor transition, so we can represent each transition in
R by its starting state.
Now we give
\(\Delta '=(S',K', A'_0, A'_1,\dots , A'_n)\), and define its initial state as
$$\begin{aligned} {{\bar{D}}}_0=(\{tr_{q_0}\}, D_{0,1},\dots , D_{0,n}). \end{aligned}$$
Notice that no query symbol appears in
\({{\bar{D}}}_0\).
The basic idea of the proof is the following: Component \(A_0'\) represents the transitions of the context automaton. To simulate a transition in \(\Gamma \), components \(A'_1, \dots ,A'_n\) request the state of \(A'_0\) and add the context provided for them to their current state. Then they perform the enabled reactions.
We define the components of \(\Delta '\) as follows.
Let
\( S'=S\cup S'' \cup S_R\cup \{X\}, \) where
$$\begin{aligned} S''= & {} \{a', a'' \mid a \in S\}, \\ S_R= & {} \{[tr_q],[tr_q]',[tr_q]''\mid tr_q\in R,\ q\in Q\}. \end{aligned}$$
Note that the short notation
\(tr_q\) in the symbols
\([tr_q], [tr_q]'\), and
\([tr_q]''\) stands for the unique transition
\((q, (C_{q,1}\ldots ,C_{q,n}),r)\in R\).
Component
\(A'_0\) contains, for each
\(tr_q=(q, (C_{q,1}\ldots ,C_{q,n}),r)\in R\), the following reactions:
$$\begin{aligned} { \begin{array}{ll} (a) &{} ( \{[tr_{q}]\},\{X\}, \{[tr_{q}]'\}), \\ (b) &{} \{[tr_{q}]'\},\{X\}, \{[tr_{q}]''\}), \\ (c) &{}\{[tr_{q}]''\},\{X\}, \{[tr_{r}]\}), \\ \end{array} } \end{aligned}$$
where
\(tr_{r}=(r, (C_{1}'\dots ,C_{n}'),s)\in R\) is also a transition in
M.
We define the reactions of the other components. Let each
\(A'_i\),
\(1\le i \le n\), have the following reactions:
$$\begin{aligned} { \begin{array}{ll} (1) &{} \{(\{a\},\{X\},\{a'\}) \mid a\in S\}\cup \{(\{a\},\{X\}, \{Q_0\})\} \mid a \in S\},\\ (2 )&{} \{(\{a'\},\{X\},\{a''\}) \mid a\in S\}\cup \{([tr_{q}]'\},\{X\}, C''_{q,i}) \mid tr_{q}\in R\},\\ (3) &{} \{U'',I,P) \mid (U,I,P) \in A_i\}, \\ \end{array} } \end{aligned}$$
where
\(U''=\{a'' \mid a\in U\}\) and
\(C_{q,i}''=\{a''\mid a \in C_{q,i}\}\) for
\(tr_q=(q,(C_{q,1},\ldots ,C_{q,n}),s)\).
Each component \(A'_i\), \(1\le i\le n\) works with the following phases of steps:
Let us consider a state \({\bar{D}}\) of \(\Delta '\) where the state \(D_i\) of component \(A'_i\) is a subset of S. The component \(A_0\) has only one reactant as its state, say, \([tr_q]\), that represents the transition in M to be performed. Then, component \(A'_i\) changes each reactant a in its current state to its primed version, \(a'\), and at the same time, by a query \(Q_0\) asks for the state of component \(A'_0\). This is performed by reactions of type (1). No more reactions can be performed in this state.
During the same step, component \(A'_0\) changes \([tr_q]\) to \([tr_q]'\), by reaction of type (a). Thus, in the next state of \(\Delta '\), component \(A'_i\), \(1\le i \le n\), has the primed version of its reactants from S together with the product \(Q_0\), while component \(A'_0\) has \([tr_q]'\).
In the following step, communication takes place, and after that in the new state of \(\Delta \), components \(A'_i\) will have as state the same elements as before, except that \(Q_0\) is changed or \([tr_q]'\). The state of component \(A'_0\) remains unchanged, \([tr_q]'\).
Then the state of component \(A'_i\), \(1\le i \le n\) changes as follows: \([tr_q]'\) is changed to \(C''_{q,i}\), the double-primed version of the context provided for component \(A_i\) by the transition \(tr_q=(q, (C_{q,1}\ldots ,C_{q,n}),r)\) in M represented by \([tr_q]\). At the same time, all reactants \(a' \) change to \(a''\). This is performed by reactions of type (2). The state of component \(A'_0\), \([tr]'\) is changed to \([tr]''\) by a reaction of type (b).
Finally, all enabled reactions of the form \((U'',I,P)\) of \(A'_i\), \(1\le i\le n\), are performed, where (U, I, P) is a reaction in \(A_i\). This is done by reactions of type (3). In the meantime, \([tr_q]''\) at \(A'_0\) is changed to \([{tr_r}]\) by reaction of type (c). Notice that \([{tr_r}]\) corresponds to the new transition to be performed, \(t_r=(r,(C_{r,1},\ldots ,C_{r,n}),s)\).
As the result, we obtain that the n-tuple of states of components \(A'_1,\dots , A'_n\) is equal to the state of the components of \(\Gamma \) obtained from the state \((D_{1},\ldots ,D_n)\) after the transition \(tr_q\) is performed in M. Notice that due to the fact that \(\Gamma \) with \(\sigma _0\) is very simple, each transition in M has only one successor transition. This property is used in the simulation.
We leave the further details of the proof to the reader. \(\square \)
We present a simple example to demonstrate how the construction in the proof works.
4 Distributed reaction systems and multihead finite automata
In this section we relate languages of distributed reaction systems to languages of multihead finite automata.
A (nondeterministic) one-way k-head finite automaton, a 1NFA(k) in short, is a construct \(M = (Q, \Sigma , k, \delta , \$, q0, F )\) where Q is the finite set of states, \(\Sigma \) is the set of input symbols, \(k\ge 1\) is the number of heads, \(S\not \in \Sigma \) is the endmarker, \(q_0 \in Q\) is the initial state, \(F \subseteq Q\) is the set of accepting states, and partial function \(\delta :Q\times (\Sigma \cup \{\lambda ,\$\})^k\rightarrow Q\) is the transition function. Whenever \(q'\in \delta (q,x_1,\ldots ,x_k)\) is defined, the state q can be changed to \(q'\) if the input contains \(x_i\in \Sigma \cup \{\$\}\) at the position of the i-th reading head for \(x_i\not =\lambda \), or if \(x_i=\lambda \), then the input might contain an arbitrary symbol from \(\Sigma \cup \{\$\},\ 1\le i\le k\). It is also assumed that in the case of \(x_i\not =\lambda \), the reading head moves one position to the right during the transition, but it does not move and stays its current position if \(x_i=\lambda ,\ 1\le i\le k\).
The configuration of a 1NFA(k) can be denoted by \((q,w_1\$,\ldots ,w_n\$)\) where \(q\in Q\) and \(w_i,\ 1\le i\le k\), are the parts of the input string which are not yet read by the corresponding heads.
In the following, we consider two possible ways of describing languages with extended distributed reaction systems. The idea is to assign symbols of an alphabet to the states of the components of the system, and to obtain this way sequences of symbols (or words) by terminating interactive processes corresponding to each of the components. The seminal variant of the concept was introduced in Ciencialová L et al. (
2022).
Notice that the mapping \(\rho \) assigns to any nonempty subset of S a letter of \(\Sigma \). Note also that \(\rho \) is a bijective mapping, thus, there is no letter in \(\Sigma \) that is the map of two different nonempty subsets of S.
The classes of concatenation and agreement languages of extended distributed reaction systems are denoted by \({\mathcal {L}}_{X}(EDRS),\ X\in \{concat,agree\}\).
In Ciencialová L et al. (
2022,
2023) concatenation languages were studied, here we focus on agreement languages.
Proof
Let
\(L=L_{agree}(\Gamma , \Sigma ,\rho )\) for some extended distributed reaction system
\(\Gamma =(\Delta ,M)\) defined as above, and let us construct the 1NFA(
k)
\(M'=(Q',\Sigma ,k,\delta ',q_0',F')\) with
$$\begin{aligned} Q'=\{q_\sigma \mid q\in Q,\ \sigma \text{ is } \text{ a } \text{ state } \text{ of } \Gamma \}\cup \{q_0'\}, \end{aligned}$$
\(F'=\{q_f\}\not \subseteq F\), and with
\(\delta '\) defined as follows.
Let
$$\begin{aligned}q_{\sigma _0}\in \delta '(q_0',\rho (d_1),\ldots ,\rho (d_n)) \end{aligned}$$
for all
\(\sigma _0=(q_0,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\) such that
\(q_0\) is the initial state of
M, and
\((c_1,\ldots ,c_n)\in C\),
\(d_i\subseteq S\),
\(1\le i\le n\).
For any
\((c_1,\ldots ,c_n)\in C\) and
\((d_1,\ldots ,d_n)\) with
\(d_i\subseteq S\),
\(1\le i\le n\), we also have
$$\begin{aligned}r_{\sigma _2}\in \delta '(q_{\sigma _1},\rho (d_1'),\ldots ,\rho (d_n')) \end{aligned}$$
if and only if
$$\begin{aligned}\sigma _1=(q,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\Longrightarrow \sigma _2=(r,(c_1',\ldots ,c_n'),(d_1',\ldots ,d_n')) \end{aligned}$$
is a possible transition in
\(\Gamma \). In addition, for all
\(q\in F\) and
\(\sigma \) being a state of
\(\Gamma \), we have
$$\begin{aligned} \delta '(q_\sigma ,\$,\ldots ,\$)=\{q_f\}. \end{aligned}$$
To see how the 1NFA(
k)
\(M'\) simulates the EDRS
\(\Gamma \), consider the following. An initial state
$$\begin{aligned} \sigma _0=(q_0,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n)) \end{aligned}$$
of
\(\Gamma \) is mapped to the symbols
\(\phi (\sigma _0)=(\rho (d_1),\ldots ,\rho (d_n))\), these will be the first symbols of the languages associated to the components during the computation that will follow. The exact same symbols are read by the multihead automaton
\(M'\) using one of its initial transitions
$$\begin{aligned} q_{\sigma _0}\in \delta '(q_0',\rho (d_1),\ldots ,\rho (d_n)). \end{aligned}$$
Now, if the initial transition of
\(\Gamma \) is
$$\begin{aligned} \sigma _0=(q_0,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\Longrightarrow \sigma =(q,(c_1',\ldots ,c_n'),(d_1',\ldots ,d_n')) \end{aligned}$$
for some
\((q_0,(c_1,\ldots ,c_n),q)\in R\) of the context automaton, then the resulting state of this transition is mapped to the symbols
\(\phi (\sigma )=(\rho (d_1'),\ldots ,\rho (d_n'))\), which will also be part of the strings associated to the components of
\(\Gamma \). The same symbols are read by
\(M'\) using one of its transitions
$$\begin{aligned} q_{\sigma }\in \delta '(q_{\sigma _0},\rho (d_1'),\ldots ,\rho (d_n')). \end{aligned}$$
Since the number of possible states
\((d_1,\ldots ,d_n),\ d_i\subseteq S,\ 1\le i\le n\), is finite, we have a corresponding transition in
\(M'\) for any possible state and transition in
\(\Gamma \). If
\(\sigma =(q,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\) is a state (with
\(\phi (\sigma )=\rho (d_1),\ldots ,\rho (d_n)\) being the last symbols of the strings associated to the components so far), then for any transition
$$\begin{aligned} t:\ \sigma =(q,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\Longrightarrow \sigma '=(r,(c_1',\ldots ,c_n'),(d_1',\ldots ,d_n')), \end{aligned}$$
we have
$$\begin{aligned} r_{\sigma '}\in \delta '(q_\sigma ,\rho (d_1'),\ldots ,\rho (d_n')) \end{aligned}$$
in
\(M'\) which reads the same symbols as the ones appended to the languages of the components by the transition
t above.
Now, if for some state
\(\sigma \),
\(\Gamma \) is able to enter a final state (a state like
\(\sigma '\) with
\(r\in F\), as below)
$$\begin{aligned}\sigma =(q,(c_1,\ldots ,c_n),(d_1,\ldots ,d_n))\Longrightarrow \sigma '=(r,(c_1',\ldots ,c_n'),(d_1',\ldots ,d_n')), \end{aligned}$$
then
\(M'\) is able to enter the state
\(r_{\sigma '}\) by
$$\begin{aligned} r_{\sigma '}\in \delta '(q_{\sigma },\rho (d_1'),\ldots ,\rho (d_n')). \end{aligned}$$
If the strings associated to the components of
\(\Gamma \) \( w_i=\phi _i(\sigma _0)\ldots \phi _i(\sigma _m) \) during the computation
\( \sigma _0\Longrightarrow \ldots \Longrightarrow \sigma _m \) coincide, that is,
\(w=w_i=w_j\) for all
\(1\le i,j\le n\), then
\(w\in L_{agree}(\Gamma ,\Sigma ,\rho )\), and in this case
\(M'\) is able to enter into its final state by the transition
$$\begin{aligned} \delta '({r_\sigma '},\$,\ldots ,\$)=\{q_f\}. \end{aligned}$$
By the construction of
\(M'\), we can also see that any state sequence of an accepting computation
\( q_0',q_{\sigma _0},\ldots ,q_{\sigma _m},q_f, \) on a string
\(w\in \Sigma ^*\) has a corresponding state sequence
$$\begin{aligned} \sigma _0\Longrightarrow \ldots \Longrightarrow \sigma _m \end{aligned}$$
in
\(\Gamma \) with
\(\sigma _0\) and
\(\sigma _m\) being an initial and an accepting state, respectively, and
w being the string associated to this computation by the mapping
\(\rho \) at all of the components.
Let us now assume that
L is accepted by a 1NFA(
k)
\(M=(Q,\Sigma ,k,\delta ,q_0,F)\), and let us construct an extended distributed reaction system
\(\Gamma =(\Delta ,M')\) where
\(\Delta =(S,{\mathcal {A}})\) with
\({\mathcal {A}}=(A_1,\ldots , A_k)\) for
\(A=A_1=\ldots =A_k\) and
$$\begin{aligned} S= & {} \Sigma \cup \bar{\Sigma }\cup \{\#,\$ \} \text{ where } \bar{\Sigma }=\{{\bar{a}}\mid a\in \Sigma \}, \\ A= & {} \{(\{a\},\{\#\},\{\bar{a}\}),(\{a,{\bar{b}}\},\{\#\},\{{\bar{a}}\}), (\{\$,\bar{a}\},\{\#\},\emptyset )\mid a,b\in \Sigma \}. \end{aligned}$$
The context automaton
\(M'=(Q,C,R,q_0,F)\) is defined as
$$\begin{aligned} C= & {} \{(\alpha _1,\ldots ,\alpha _k)\mid \alpha _i\in \{\emptyset ,\{a\}\mid a\in \Sigma \},1\le i\le k\}, \end{aligned}$$
and for all
\(q'\in \delta (q,x_1,\ldots ,x_k),\ x_i\in \Sigma \cup \{\lambda \},\ 1\le i\le k\), we have transitions
$$\begin{aligned} (q,(s(x_1),\ldots ,s(x_k)),q') \text{ where } s(x_i)=\left\{ \begin{array}{cl} \{x_i\} &{} \text{ if } x_i\not =\lambda , \\ \emptyset &{} \text{ if } x_i=\lambda , \end{array}\right. \ 1\le i\le k, \end{aligned}$$
in
R. The initial states of the EDRS
\(\Gamma \) are those with
$$\begin{aligned} (q_0,(s(x_1),\ldots ,s(x_k)),(\emptyset ,\ldots ,\emptyset )), \end{aligned}$$
such that
\(\delta (q_0,x_1,\ldots ,x_k)\not =\emptyset \), and the mapping
\(s: \Sigma \cup \bar{\Sigma }\cup \{\lambda \}\rightarrow 2^{\Sigma \cup \bar{\Sigma }}\) is defined as above. Thus, the first transitions of
\(\Gamma \) are of the form
$$\begin{aligned} (q_0,(s(x_1),\ldots ,s(x_k)),(\emptyset ,\ldots ,\emptyset ))\Longrightarrow (q,(s(y_1),\ldots ,s(y_k)),(s({\bar{x}}_1),\ldots ,s({\bar{x}}_k)), \end{aligned}$$
and they simulate the transitions
\( q\in \delta (q_0,x_1,\ldots ,x_k) \) of
M. Now, if a transition
\( q'\in \delta (q,y_1,\ldots ,y_k) \) is also a possible in
M, then we have
$$\begin{aligned}&(q,(s(y_1),\ldots ,s(y_k)),(s({\bar{x}}_1),\ldots ,s(\bar{x}_k))\Longrightarrow \\ {}&\quad (q',(\alpha _1,\ldots ,\alpha _k),(s({\bar{y}}_1),\ldots ,s({\bar{y}}_k)) \end{aligned}$$
as the next step of
\(\Gamma \) for some
\(\alpha _i\in 2^\Sigma ,\ 1\le i\le k\).
In general, we have
$$\begin{aligned} (q,(s(x_1),\ldots ,s(x_k),(\beta _1,\ldots ,\beta _k)\Longrightarrow (q',(\gamma _1,\ldots ,\gamma _k),(s({\bar{x}}_1),\ldots , s({\bar{x}}_k)) \end{aligned}$$
for some
\(\beta _i\in 2^{\bar{\Sigma }}\),
\(\gamma _i\in 2^\Sigma \),
\(1\le i\le k\), as a possible transition in
\(\Gamma \), if and only if
$$\begin{aligned} q'\in \delta (q,x_1,\ldots ,x_k) \end{aligned}$$
\(x_i\in \Sigma \cup \{\lambda \}\), is a possible transition in the 1NFA(
k)
M. Now, if we define the (partial) mapping
\( \rho :2^S\rightarrow \Sigma \cup \{\lambda \}\) for
\(\{{\bar{a}}\mid a\in \Sigma \}\cup \{\emptyset \}\) as
\(\rho (\{{\bar{a}}\})=a,\ a\in \Sigma \), and
\(\rho (\emptyset )=\lambda \), then we have
$$\begin{aligned} (x_1,\ldots ,x_k)=(\rho (s({\bar{x}}_1)),\ldots ,\rho (s({\bar{x}}_k))), \end{aligned}$$
that is, the letters associated to the components of the EDRS
\(\Gamma \) as a result of performing the state transition above are the same as the letters read by the heads of
k-head automaton
M.
Therefore, if
$$\begin{aligned} (q_0,w\$,\ldots ,w\$)\Longrightarrow \ldots \Longrightarrow (q_m,\$,\ldots ,\$)\Longrightarrow (q_f,\lambda ,\ldots ,\lambda ) \end{aligned}$$
is the sequence of configurations the 1NFA(
k)
M passes through while accepting an input string
\(w=a_1\ldots a_l\), then
$$\begin{aligned}&(q_0,\alpha _1,\ldots ,\alpha _k),(\emptyset ,\ldots ,\emptyset ))\Longrightarrow (q,\beta _1,\ldots ,\beta _k),(\bar{\alpha }_1,\ldots ,\bar{\alpha }_k))\Longrightarrow \ldots \\&\quad \ldots \Longrightarrow (q_m,\{\$\},\ldots ,\{\$\}),(\bar{\gamma }_1,\ldots ,\bar{\gamma }_k))\Longrightarrow (q_f,\delta _1,\ldots ,\delta _k),(\emptyset ,\ldots ,\emptyset )) \end{aligned}$$
is a possible computation in
\(\Gamma \) with
$$\begin{aligned} \rho (\emptyset )\rho (\bar{\alpha }_i)\ldots \rho (\bar{\gamma }_i)\rho (\emptyset )=a_1\ldots a_l=w \end{aligned}$$
being the string associated to each component
\(A_i,\ 1\le i\le k\), of the EDRS
\(\Gamma \).
By the construction of the EDRS \(\Gamma \) we can also see that any terminating interactive process where the same string is associated to each of the components is such, that a corresponding transition sequence accepting the same string exists in the k-head finite automaton M. \(\square \)
In the following we discuss the languages assigned to qDRS. By definition, it can easily be seen that the behavior of every qDRS
\(\Delta \) is deterministic, i.e., starting from a given initial state
\({{\bar{D}}}_0\), there exists only one state sequence
\({{\bar{D}}}_0, {{\bar{D}}}_1,\dots , {{\bar{D}}}_m, \dots \) of
\(\Delta \). This sequence, as in the case of reaction systems, is either finite or (infinite) ultimately periodic. In Theorem
2 we proved that to any qDRS
\(\Delta \) with an initial state we can construct an EDRS
\(\Gamma \) with an initial state such that the state sequence of the qDRS corresponds to the state sequence of the components of the EDRS. Thus, by Definitions
12 and
13, we can assign both agreement and concatenating languages to
\(\Gamma \). If we analyze the proof of Theorem
2, we can easily observe that the language assigned to each component of
\(\Gamma \), thus to each component of
\(\Delta \) is regular. Furthermore, according to the previous remarks, it is either a finite or an ultimately periodic regular language which belongs to a subregular language class. Thus, the agreement language of
\(\Delta \) is either a finite language or an ultimately periodic regular language; both languages are elements of language classes which are proper subclasses of the regular language class and the class of languages accepted by multihead nondeterministic finite automata.