Hybrid eco-grammar systems

In the definition of a simple eco-grammar system the agents have context-free rules; now we modify this condition and we use new operations, insertion and replacement.

An insertion rule (an INS-type rule, for short) over an alphabet $V$ is an ordered triple $(u,z,v)$, where $u,z,v\in V^+$. We derive $y$ from $x$ by applying the insertion rule $(u,z,v)$ if $x=x_1x_2$, $y=x_1zx_2$, and $u\preceq x_1$, $v\preceq x_2$, with $x_1,x_2\in{V}^*$.

By a replacement rule (a REP-type rule, for short) over an alphabet $V$ we mean a rule in the form of $(a,b,c)\ensuremath{\rightarrow}(a,d,c)$, where $a,b,c,d\in V$. We derive $y$ from $x$ by the replacement rule $(a,b,c)\ensuremath{\rightarrow}(a,d,c)$ if $x=x_1abcx_2$, $y=x_1adcx_2$, and $x_1,x_2\in{V}^*$.

By an insertion rule we can insert a new sub-word into the sentential form, while by a replacement rule we can change only one letter. We can see that there is also a difference between the context restrictions in the two definitions. When applying an INS-type rule, the two parts of the context condition, $u$ and $v$, must be present in the sentential form in the same order as presented in the rule, and the position of the insertion can be anywhere between them. In a REP-type rule the restriction is more strict: the close contexts (that is, the neighbouring letters) are prescribed by the rule. This difference is motivated by the properties of DNA strands: local point-mutations are determined by the close context of the position where the mutation happens, while a global change in the DNA strand (e.g. an insertion) is directed by the presence or absence of some substrings in the strand.

We study two different models using these new operations. The first type of models is the simple eco-grammar system of type INS or REP, where all the agents are of the same type. We study these systems in Section 4.2.

In the other model, in the hybrid eco-grammar system, there can be agents of both type.

Definition 4.1  
A hybrid eco-grammar system is a construct $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$, where

• $V_E$ is a finite, non-empty alphabet,
• $P_E$ is a complete set of CF rules over $V_E$,
• $1\leq n$, $0\leq n_1\leq n$,
• $R_i$ is a set of INS-type rules for $1\leq i\leq n_1$ and $R_i$ is a set of REP-type rules for $n_1+1\leq i\leq n$,
• $\omega\in {V_E}^*$.

In this construct $V_E$, $P_E$, and $\omega$ are defined in the same way as in the original definition of a simple eco-grammar system. The first $n_1$ sets, $R_i$, $1\leq i \leq n$, represent the agents of type INS, the others represent the agents of type REP. Notice that $n_1=0$ or $n_1=n$ are also allowed, that is, the system can contain only REP-type or only INS-type agents, which gives that simple eco-grammar systems of type INS or REP are special hybrid eco-grammar systems.

We study different derivation modes in hybrid eco-grammar systems. The difference lies in the restrictions prescribed for the number of agents being active in a derivation step. One of these possibilities is the derivation mode $(=k_1, =k_2)$, defined below.

Definition 4.2  
Consider a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$. We say that $x$ directly derives $y$ in $\Sigma$ in the derivation mode $(=k_1, =k_2)$, (with $x,y\in {V_E}^*$, $0\leq k_1\leq n_1$, $0\leq k_2\leq n-n_1$, and $1\leq k=k_1+k_2$, written as $x\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}y$), if

• there exists a word $\ensuremath{{{\overline{x}}}}=x_1o_1x_2o_2\cdots x_ko_kx_{k+1}$ over $V_E\cup \{I\}$, $I\not \in V_E$, such that ${x_t}\in {V_E}^*$, $o_j\in V_E\cup \{I\}$ for $1\leq t\leq k+1$, $1\leq j\leq k$,
  $\vert\{j\;\vert\;1\leq j\leq k, o_j=I\}\vert=k_1$, $\vert\{j\;\vert\;1\leq j\leq k, o_j\in V_E\}\vert=k_2$, and $f(\ensuremath{{{\overline{x}}}})=x$, where f is the homomorphism defined over $V_E\cup \{I\}$ as follows:
  $$f(z) = \left \{ \begin{array}{ll} z & \mbox{if $z\in V_E$} \\ \lambda & \mbox{if $z=I$} \end{array}\right.$$

• $y=y_1{\gamma}_{1}y_2{\gamma}_{2}y_3\cdots{\gamma}_{k} y_{k+1}$, with $y_t,{\gamma}_{j}\in {V_E}^*$ for $1\leq t\leq k+1, 1\leq j\leq k$,

• there exist k different agents $R_{i_1},\ldots,R_{i_k}$, such that
  
  if $o_j=I$, then there exists an INS-type rule $({\alpha}_{j},{\gamma}_{j}, {\beta}_{j})\in R_{i_j}$, such that ${\alpha}_{j}\preceq f(x_1o_1\cdots o_{j-1}x_j)$ and ${\beta}_{j}\preceq f(x_{j+1}o_{j+1}\cdots o_k x_{k+1})$,
  
  if $o_j\in V_E$, then there exists a REP-type rule $(a_{j},o_j,b_{j})\ensuremath{\rightarrow} (a_{j},{\gamma}_{j},b_{j})\in R_{i_j}$, such that $f(x_1o_1\cdots o_{j-1}x_j)=ua_{j}$ and $f(x_{j+1}o_{j+1}\cdots o_k x_{k+1})=b_{j}v$, where $u,v\in {V_E}^*$, and
• $x_1x_2\cdots x_{k+1}=y_1y_2\cdots y_{k+1}=\lambda$ or $x_1x_2\cdots x_{k+1}\ensuremath{{\stackrel{\text{0L}}{\Longrightarrow}}_{E}}y_1y_2\cdots y_{k+1}$, where $E=( V_E, P_E, \omega )$ is the 0L system of the environment.

Informally speaking, a derivation step goes in the following way. We choose $k$ different agents and $k$ sites in the sentential form, $k_1$ sites for insertion, $k_2$ sites for replacement, $k_1+k_2=k$. The positions where insertions are to be performed are marked by $I$, the positions chosen for replacements are marked by the letter to be replaced. These positions must be compatible with the corresponding operations: for each position there must be a chosen agent which is of the corresponding type and which has a rule applicable at that position. When the agents have applied the chosen rules, the environment rewrites the remaining letters.

We emphasise the following consequences of the definition: more than one agent can use the same context to apply an insertion and the contexts of several replacements can be overlapping, too. That is, for example in a sentential form $a_1a_2a_3a_4$ (where the $a_i$'s are letters) the following two insertion rules and the following two replacement rules can be used in the same derivation step: $(a_1, {\alpha}_1, a_2)$ and $(a_1, {\alpha}_2, a_2)$, $(a_1,a_2,a_3)\ensuremath{\rightarrow}(a_1,d_1, a_3)$, and $(a_2,a_3,a_4)\ensuremath{\rightarrow}(a_2,d_2, a_4)$. If the environment does not change the letters, with these four rules we obtain either the word $a_1{\alpha}_1{\alpha}_2d_1d_2a_4$ or the word $a_1{\alpha}_2{\alpha}_1d_1d_2a_4$.

The above definition also implies that if we consider the derivation mode $(=k_1, =k_2)$ in a hybrid EG system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$, then $0\leq k_1\leq n_1$, $0\leq k_2\leq n-n_1$ and $1\leq k_1+k_2$ hold, where $n_1$ is the number of INS-type agents in the system.

In a derivation step $(=k_1, =k_2)$ we prescribe how many INS-type and how many REP-type agents work in a derivation step. If we prescribe only the total number of agents working in a derivation step, then we obtain derivation mode $=k$.

Definition 4.3  
Consider a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$. We say that $x$ directly derives $y$ in $\Sigma$ in the derivation mode $=k$, (with $x,y\in {V_E}^*$ and $1\leq k\leq n$, written as $x\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}y$), if $x\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}y$ for some $0\leq k_1\leq n_1$, $0\leq k_2\leq n-n_1$, where $k_1+k_2=k$.

We denote the transitive and reflexive closure of $\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}$ and $\ensuremath{\stackrel{ =k}{{\Longrightarrow}_{\Sigma}}}$ by $\ensuremath{\stackrel{(=k_1,=k_2)} {{\Longrightarrow}_{\Sigma}^{*}}}$ and $\ensuremath{\stackrel{=k} {{\Longrightarrow}_{\Sigma}^{*}}}$ .

Definition 4.4  
Consider a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$. The languages generated by $\Sigma$ in the derivation modes $(=k_1, =k_2)$ and $=k$ are the following:

$$L(\Sigma,=k_1,=k_2)= \{ v\in \ensuremath{{V_E}^*}\vert\;{\omega}\ensuremath{\stackrel{(=k_1,=k_2)} {{\Longrightarrow}_{\Sigma}^{*}}}v \},$$

$$L(\Sigma,=k)= \{ v\in \ensuremath{{V_E}^*}\vert\; {\omega}\ensuremath{\stackrel{= k} {{\Longrightarrow}_{\Sigma}^{*}}}v \}.$$

The class of languages which can be generated by hybrid eco-grammar systems is denoted by ${\mathcal L}(E_H)$; in the two special cases, when the agents are of the same type, the language classes are denoted by ${\mathcal L}(E_{INS})$ and ${\mathcal L}(E_{REP})$. The class of languages generated by hybrid EG systems containing $n$ agents and operating in the derivation mode $(=k_1, =k_2)$ or in the derivation mode $=k$ is denoted by ${\mathcal L}(E_H(n,=k_1,=k_2))$ and ${\mathcal L}(E_H(n,= k))$. We replace the subscript $H$ by INS or REP in the case of homogeneous INS- or REP-type EG systems.

We present an example, which shows how a hybrid eco-grammar system works and which proves to be useful in the proofs of the chapter, too.

Example 4.5  
Let $0\leq k_1,k_2$ and $1\leq n$, such that $1\leq k_1+k_2\leq n$ and let $\Sigma=(\:V_E,P_E,k_1,R_1,\ldots,R_n,\omega\:)$ be the following hybrid eco-grammar system:

• $V_E=\{a_1,a_2,c_1,\ldots,c_n\}$,
• $P_E=\{a_1\ensuremath{\rightarrow}{a_2},a_2\ensuremath{\rightarrow}{a_1}^2 \} \cup\:{\bigcup}_{1\leq j \leq n}\{c_j\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{(a_1,c_i,a_1),(a_2,a_1,a_2)\}$ for $1\leq i \leq k_1$,
• $R_i=\left\{(a_1,a_1,a_1)\ensuremath{\rightarrow}(a_1,c_i,a_1)\right\}\cup \left\{ (e,c_i,f)\ensuremath{\rightarrow}(e,a_1,f)\;\vert\;e,f\in \{a_2,c_1,\right.$
  $\left. \ldots,c_n\}\right\}$ for $k_1+1\leq i \leq n$,
• $\omega={a_1}^{2+k_2}$.

In this way we define a hybrid eco-grammar system for any $0\leq k_1,k_2$, $1\leq n$, where $1\leq k_1+k_2\leq n$ holds. For each such system we consider two derivation modes, the derivation modes $(=k_1, =k_2)$ and $=k$ with $k=k_1+k_2$. The generated languages $L(\Sigma,=k_1,=k_2)$ and $L(\Sigma,= k)$ are denoted by $L_H(n,=k_1,=k_2)$ and $L_H(n(k_1), =k)$ and proves to be useful in several proofs of the chapter.

The parameters $n$, $k$ and $k_1, k_2$ in the notations $L_H(n,=k_1,=k_2)$ and $L_H(n(k_1), =k)$ refer to the following: these languages are generated by a hybrid EG system defined in Example 4.5, in the derivation mode $(=k_1, =k_2)$ or $=k$. The generating system contains $n$ agents, $k_1$ agents of type INS, $n-k_1$ agents of type REP and the length of the axiom is equal to $k_2+2$, where $k_2=k-k_1\leq n-k_1$.

Having examined the system defined in Example 4.5 and the derivation process, we can see that both generated languages, $L_H(n,=k_1,=k_2)$ and $L_H(n(k_1), =k)$, contain two types of words: ${a_1}^+$ (the shortest word of this type is the axiom, ${a_1}^{2+k_2}$) and $a_2{[c_1,c_2,\ldots, c_{k_1}, c_{j_1}, \ldots, c_{j_{k_2}}, a_2,\ldots, a_2]}^Pa_2$, that is, words containing the first $k_1$ letters $c$ and more $k_2$ different letters $c$, besides some letters $a_2$. In this latter type of words the symbols $c$ can stand anywhere except the first and the last position of the word.

In the following we present some auxiliary statements which are used in the chapter. In these lemmas we use the following notions:

Definition 4.6  
If $a\in$   alph$(L)$ for a language $L$ and for any $K_0>0$ there exists a word $w\in L$ with ${\vert w\vert}_{a}\geq K_0$, then the symbol $a$ is said to be a letter with unbounded occurrence, otherwise $a$ is said to be a letter with bounded occurrence.

Lemma 4.7  
Let $L$ be a language with the following properties:

(i)

$L=L_1\cup L_2$, where both $L_1$ and $L_2$ are infinite languages and their alphabets, alph$(L_1)$ and alph$(L_2)$, are disjoint sets.

(ii)

For any letter $a\in$   alph$(L_i)$ with unbounded occurrence ( $i=1,2$), for any $w\in L_i$, and for any $K>0$ there exists a word $w'\in L_i$, such that $w\preceq w'$ and ${\vert w'\vert}_a> K$.

If $L$ has these properties and $L=L(\Sigma,=k)$ or $L=L(\Sigma,=k_1,=k_2)$ with a hybrid EG system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$, then for each $u,v\in L$ the facts that $v\in L_i$ and $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$ implies that $u\in L_j$ and $i\not = j$.

Informally speaking, this lemma says that if a language has the above properties and it can be generated by a hybrid eco-grammar system, then the words following each other in a derivation sequence are over different sub-alphabets.

In this section, when applying this lemma to a language $L$, the division $L=L_1\cup L_2$ will be always straightforward, in general the letters of alph$(L_1)$ and the letters of alph$(L_2)$ will be the letters with subscript $1$ and $2$, respectively.

PROOF.
First we prove a slightly weaker statement: we show that there exists a positive integer $N$, such that for $u,v\in L$ if $v\in L_i$, $\vert v\vert>N$, and $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$, then $u\in L_j$ and $i\not = j$. That is, first we show that words over one of the sub-alphabets and being longer than $N$ can be derived only from words being over the other sub-alphabet.

Let us define $N$ as follows:

• in derivation mode $=k$ let $N=k\cdot{\max}_{1\leq l \leq n_1} {\max}_{(u,z,v)\in R_l}\vert z\vert+k+M\cdot{\max}_{s\ensuremath{\rightarrow}t\in P_E}\vert t\vert$, where $M$ is the maximum number of letters with bounded occurrence in a word of $L$;
• in derivation mode $(=k_1, =k_2)$ let $N=k_1\cdot{\max}_{1\leq l \leq n_1} {\max}_{(u,z,v)\in R_l}\vert z\vert+k_2+M\cdot{\max}_{s\ensuremath{\rightarrow}t\in P_E}\vert t\vert$, where $M$ is the same as above.

Suppose on the contrary that there exist words $u,v\in L$ such that $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$, $\vert v\vert>N$ and $u,v\in L_i$ (for $i=1$ or $i=2$).

Since $\vert v\vert>N$, it is sure that in the step $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$ the system $\Sigma$ uses at least one production in the form of $a\ensuremath{\rightarrow}w_1$ from $P_E$, where $a\in$   alph$(L_i)$ is a letter with unbounded occurrence and $w_1\in {(\text{alph}(L_i))}^+$ is a non-empty word being over alph$(L_i)$ (otherwise $\vert v\vert\leq N$ would hold because of the definition of $N$).

The existence of such a rule implies that $\Sigma$ cannot perform any derivation step $u_1\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v_1$ or ${u_1}\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}{v_1}$, where $u_1\in L_i$ and $\lambda\not=v_1\in L_j$, $i\not = j$, that is, such a derivation step where from a word over alph$(L_i)$ a non-empty word over the other sub-alphabet would be derived. This is true because in this case, by combining the above rule $a\ensuremath{\rightarrow}w_1$ of $P_E$ and the rules used in the step $u_1\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v_1$ or $u_1\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v_1$, we would be able to derive words in which letters from both sub-alphabets occur. (Here we use condition (ii), which guarantees that there is a word in $L_i$ in which $u_1$ is a sub-word and $a$ occurs at least once.)

Therefore the words over alph$(L_j)$ can be derived only from words over the same sub-alphabet, which is also true for those words over alph$(L_j)$ which are longer than $N$. Since we know that such words exist ($L_j$ is an infinite language) we can conclude that there exists a rule in $P_E$ in the form of $b\ensuremath{\rightarrow}w_2$, where $b\in$   alph$(L_j)$ is a letter with unbounded occurrence and $w_2\in {(\text{alph}(L_j))}^+$.

The existence of such a rule implies that $\Sigma$ cannot perform any derivation step where from a word over alph$(L_j)$ a non-empty word over the other sub-alphabet alph$(L_i)$ would be derived because in this case, combining this derivation step with the application of the above rule $b\ensuremath{\rightarrow}w_2$, we could generate words in which letters from both sub-alphabets occur.

Hence we have obtained that words over one of the sub-alphabets can be derived only from words over this sub-alphabet, which is a contradiction because in this way only the words of $L_i$ or only the words of $L_j$ could be derived, depending on the alphabet of the axiom.

Thus we have proved that words longer than $N$ being over one of the sub-alphabets can be derived only from words being over the other sub-alphabet.

Now we prove the statement of the lemma. Let us suppose that there exists a derivation step $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$, such that $u,v\in {(\text{alph}(L_i))}^+$. Since we have seen that sufficiently long words over alph$(L_j)$ can be derived only from words over alph$(L_i)$ and since $L_i$ and $L_j$ are infinite languages, there must be at least one rule in $P_E$ in the form of $a\ensuremath{\rightarrow}w_1$, where $a\in$   alph$(L_i)$ is a letter with unbounded occurrence, $w_1\in {(\text{alph}(L_j))}^+$ and $i\not = j$. Combining this rule with the derivation step $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ or $u\ensuremath{\stackrel{(=k_1,=k_2)}{{\Longrightarrow}_{\Sigma}}}v$, we could derive words in which symbols from both sub-alphabets occur.height 5pt width 5pt depth 0pt

In Section 4.2 we use a modified version of the above lemma for simple eco-grammar systems of type CF.

Lemma 4.8  
Let $L$ be a language with properties $(i)$ and $(ii)$ mentioned in Lemma 4.7. If $L=L(\Sigma,=k)$ with a simple eco-grammar system of type CF , then for each $u,v\in L$ the facts that $v\in L_i$ and $u\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}v$ imply that $u\in L_j$ and $i\not = j$.

PROOF.
The proof uses analogous arguments to the ones presented in the proof of Lemma 4.7. There is only one difference, namely that $N$ is defined as $N:=k\cdot{\max}_{1\leq l \leq n} {\max}_{A\ensuremath{\rightarrow}z\in R_l}\vert z\vert+M\cdot{\max}_{s\ensuremath{\rightarrow}t\in P_E}\vert t\vert$, where $M$ is the maximum number of letters with bounded occurrence in a word of $L$.height 5pt width 5pt depth 0pt

The following lemma proves to be useful when proving incomparability of language classes defined with different parameters.

Lemma 4.9  
Let $L$ be a language with properties $(i)$ and $(ii)$ mentioned in Lemma 4.7.
Moreover, let $L$ have the following properties, too: there exist two positive integers $k$ and $n$, such that $2\leq k\leq n$ and

(iii)

there exist $n$ different letters $c_1,\ldots,c_n\in$   alph$(L_2)$, such that for every $w\in L_2$:

• ${\sum}_{i=1}^{n}{\vert w\vert}_{c_i}=k$,
• ${\vert w\vert}_{c_i}\leq 1$ for $1\leq i \leq n$,

(iv)

for any $i,j$, $1\leq i,j, \leq n$, $i\not = j$ and for any $M_0>0$ there exists a word $w'$ in $L_2$, such that $w'=x_1c_ix_2c_jx_3$, with $x_1,x_2,x_3\in {(\text{\upshape alph}(L_2))}^*$ and $\vert x_2\vert> M_0$, and

(v)

$\vert$alph$(L_1)\vert=1$.

If $L=L(\Sigma, =\ell)$ or $L=L(\Sigma,={\ell}_1,={\ell}_2)$ with a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,m_1,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$, then $m\geq n$ and $\ell\geq k$ or ${\ell}_1+{\ell}_2\geq k$, respectively.

PROOF.
Let us consider the rules whose application can introduce letters $c$ into the strings of $L_2$. These rules are either from $P_E$ or are rules of the agents, that is, (see Lemma 4.7) they are in the form of $(\alpha, \beta,\gamma)$, where $\alpha, \gamma\in {(\text{alph}(L_1))}^+$, $\beta\in {(\text{alph}(L_2))}^+$ or in the form of $(a,b,e)\ensuremath{\rightarrow}(a,d,e)$, where $a,b,e\in$   alph$(L_1)$, $d\in$   alph$(L_2)$.

1. Rules of $P_E$ cannot introduce letters $c$ because in this case it would be possible to generate words with more than $k$ letters $c$ (see condition (v), which gives that the only one letter in alph$(L_1)$ is a letter with unbounded occurrence).
2. If $\ell<k$ or ${\ell}_1+{\ell}_2<k$ or if $m<n$, then there must be at least one agent $R_{i_1}$ in $\Sigma$ which is able to introduce two different letters $c$: $c_i$ and $c_j$ (otherwise words of $L_2$ would contain at most $k-1$ letters $c$ or there would be at most $n-1$ different letters $c$ in alph$(L_2)$). Since the distance between the occurrences of $c_i$ and $c_j$ is unbounded (see condition (iv)), there must be at least one more agent $R_{i_2}$ in ${\Sigma}$ which can also introduce $c_i$ or $c_j$ and we can use these two agents, $R_{i_1}$ and $R_{i_2}$, together in the same derivation step. But in this case we could derive words with two $c_i$ or $c_j$ (see condition (v)), which is not possible in the generated language.

height 5pt width 5pt depth 0pt

In the following we present results concerning the relations of language classes ${\mathcal L}(E_H(n,= k))$ and ${\mathcal L}(E_H(m,=k_1,=k_2))$. To begin with, we examine the relation between language classes ${\mathcal L}(E_H(n,= k))$ defined with different $k$ or $n$. The following theorem says that if the second parameter, $k$, is fixed, then there is a hierarchy according to the number of agents, but the language classes generated with different parameters $k$ are incomparable.

Theorem 4.10  
For $1\leq k\leq n$ and $1\leq \ell\leq m$

1. ${\mathcal L}(E_{H}(n,=k))\subset {\mathcal L}(E_{H}(m,=k))$ if $k\geq 2$ and $m>n$,
2. ${\mathcal L}(E_{H}(1,=1))\subset{\mathcal L}(E_{H}(2,=1))$,
3. ${\mathcal L}(E_{H}(n,=1))={\mathcal L}(E_{H}(m,=1))$ if $n,m\geq 2$,
4. otherwise ${\mathcal L}(E_{H}(n,=k))$ and ${\mathcal L}(E_{H}(m,=\ell))$ are incomparable.

PROOF.
1.
For a language $L=L(\Sigma,=k)$ generated by a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$, we construct the following hybrid EG system $\ensuremath{\ensuremath{{{\overline{\Sigma}}}}= (\:\ensuremath{{{\overline{V_E... ...,\ldots,\ensuremath{{{\overline{R_m}}}}, \ensuremath{{{\overline{\omega}}}}\:)}$:

• $\ensuremath{{{\overline{V_E}}}}=V_E\cup \{K\}$, where $K\not \in V_E$,
• $\ensuremath{{{\overline{P_E}}}}=P_E\cup \{K\ensuremath{\rightarrow}K\}$,
• $\ensuremath{{{\overline{m_1}}}}=n_1$,
• $\ensuremath{{{\overline{R_i}}}}=R_i$ for $1\leq i \leq n$,
• $\ensuremath{{{\overline{R_j}}}}=\{(K,K,K)\ensuremath{\rightarrow}(K,K,K)\}$ for $n+1\leq j\leq m$, and
• $\ensuremath{{{\overline{\omega}}}}=\omega$.

We have $L(\ensuremath{{{\overline{\Sigma}}}},=k)=L(\Sigma,=k)$ because the agents $\ensuremath{{{\overline{R_{n+1}}}}},\ldots,\ensuremath{{{\overline{R_m}}}}$ can never participate in any derivations of $\ensuremath{{{\overline{\Sigma}}}}$. This gives the inclusion ${\mathcal L}(E_{H}(n,=k))\subseteq {\mathcal L}(E_{H}(m,=k))$ if $m>n$.

To complete the proof, we show that the inclusion is proper if $k>1$. $L_H(m(k),=k)$ (see Example 4.5) has the properties required by Lemma 4.9 if $k\geq 2$, thus the lemma proves that it cannot be generated by a hybrid eco-grammar system containing less than $m$ agents.

$2.$
It follows from the above proof that ${\mathcal L}(E_{H}(1,=1))\subseteq {\mathcal L}(E_{H}(2,=1)$. The following example shows that the inclusion is proper.
Let $\Sigma=(\:V_E,P_E,1,R_1,R_2,\omega\:)$ be the following hybrid eco-grammar system:

• $V_E=\{a_1,a_2,b_1,b_2,c,d\}$,
• $P_E=\{a_1\ensuremath{\rightarrow}{a_2},a_2\ensuremath{\rightarrow}{a_1},b_1\en... ...ightarrow}{b_1}^2, c\ensuremath{\rightarrow}a_1,d\ensuremath{\rightarrow}a_1 \}$,
• $R_1=\{(a_1,c^2,a_1),(a_2,a_1,a_2)\}$,
• $R_2=\{(a_1,a_1,b_1)\ensuremath{\rightarrow}(a_1,d,b_1), (a_2,d,b_2)\ensuremath{\rightarrow}(a_2,a_1,b_2)\}$, and
• $\omega={a_1}^2b_1$.

In mode $=1$ we have two possibilities for the first two steps:

$${a_1}^2b_1\ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}a... ...a_2{b_2}^2 \ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}{a_1}^5{b_1}^4$$

or

$${a_1}^2b_1\ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}a_2d{b_2}^2 \ensuremath{\stackrel{=1}{{\Longrightarrow}_{\Sigma}}}{a_1}^2{b_1}^4.$$

The generated language contains only words of type ${a_1}^+{b_1}^+$, ${a_2}^+c^2{a_2}^+{b_2}^+$ or ${a_2}^+d{b_2}^+$.

Let us suppose that $L(\Sigma, =1)=L(\ensuremath{{{\overline{\Sigma}}}},=1)$ with a hybrid eco-grammar system $\ensuremath{{{\overline{\Sigma}}}}=(\ensuremath{{{\overline{V_E}}}},\ensuremat... ...{P_E}}}},1, \ensuremath{{{\overline{R_1}}}},\ensuremath{{{\overline{\omega}}}})$ containing only one agent.

We can apply Lemma 4.7 to $L(\Sigma,=1)$, with $L_1=L(\Sigma, =1)\cap {\{a_1,b_1\}}^*$, $L_2=L(\Sigma, =1)\cap {\{a_2,b_2, c,d\}}^*$, therefore words containing letters $c$ or $d$ must be derived in $\ensuremath{{{\overline{\Sigma}}}}$ from words in the form of ${a_1}^+{b_1}^+$.

By the rules of $\ensuremath{{{\overline{P_E}}}}$ we cannot introduce letters $c$ or $d$ because in this case the number of letters $c$ or $d$ would not be bounded in the generated words.

If $a_1\ensuremath{\rightarrow}\alpha$ and $b_1\ensuremath{\rightarrow}\beta$ are rules of $\ensuremath{{{\overline{P_E}}}}$, then $\alpha\in {a_2}^*$ and $\beta\in {b_2}^*$, otherwise words with mixed occurrences of letters $a_2$ and $b_2$ or words starting with $b_2$ or ending with $a_2$ would be in the generated language. Moreover, there must be at least one rule in $\ensuremath{{{\overline{P_E}}}}$ in the form of $a_1\ensuremath{\rightarrow}\alpha$ and $b_1\ensuremath{\rightarrow}\beta$ with $\alpha\not =\lambda$ and $\beta\not =\lambda$, otherwise $a_2$ or $b_2$ would be letters with bounded occurrence, which is not the case.

The only possibility to generate words with a sub-word $c^2$ is to use insertion rules because neither $\ensuremath{{{\overline{P_E}}}}$ nor a replacement rule can generate it. In $\ensuremath{{{\overline{\Sigma}}}}$ there is only one agent and so this agent must be an INS-type one, that is, the letter $d$ is also generated by an insertion rule. This rule is in the form of $({a_1}^{i_1},\gamma d\delta,{a_1}^{i_2}{b_1}^{i_3})$, $({a_1}^{i_1},\gamma d\delta,{a_1}^{i_2})$, $({a_1}^{i_1},\gamma d\delta,{b_1}^{i_2})$, $({a_1}^{i_1}{b_1}^{i_2},\gamma d\delta,{b_1}^{i_3})$, or $({b_1}^{i_1},\gamma d\delta,{b_1}^{i_2})$, where $\gamma, \delta\in {\{a_2,b_2\}}^*$ and $i_1,i_2,i_3\geq 1$. But none of these insertion rules is able to determine the exact position of the letter $d$: using the non-erasing rules of $\ensuremath{{{\overline{P_E}}}}$, we could generate words where the letter $d$ occurs at a wrong position, in the middle of a sequence of letters $a_2$ or $b_2$.

$3.$
We have to prove that ${\mathcal L}(E_{H}(m,=1))\subseteq {\mathcal L}(E_{H}(n,=1))$ if $m\geq n\geq 2$, since the other direction follows from the proof of part 1.
Let us suppose that $L=L(\Sigma, =1)$ with a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,m_1,R_1,\ldots,} \ensuremath{R_m,\omega\:)}$. Then let $\ensuremath{\ensuremath{{{\overline{\Sigma}}}}= (\:\ensuremath{{{\overline{V_E... ...},\ldots,\ensuremath{{{\overline{R_n}}}},\ensuremath{{{\overline{\omega}}}}\:)}$ be the following system:

• $\ensuremath{{{\overline{V_E}}}}=V_E$,
• $\ensuremath{{{\overline{P_E}}}}=P_E$,
• $\ensuremath{{{\overline{n_1}}}}=1$ if $m>m_1>0$, $\ensuremath{{{\overline{n_1}}}}=0$ if $m_1=0$, and $\ensuremath{{{\overline{n_1}}}}=n$ if $m_1=m$,
• $\ensuremath{{{\overline{R_1}}}}={\bigcup}_{1\leq i\leq m_1}R_{i}$ if $m_1>0$, otherwise $\ensuremath{{{\overline{R_1}}}}={\bigcup}_{1\leq j\leq m}R_{j}$,
• $\ensuremath{{{\overline{R_i}}}}={\bigcup}_{m_1+1\leq j\leq m}R_{j}$ if $m_1<m$, otherwise $\ensuremath{{{\overline{R_i}}}}={\bigcup}_{1\leq j\leq m}R_{j}$, for $2\leq i\leq n$,
• $\ensuremath{{{\overline{\omega}}}}=\omega$.

It is clear that $L(\Sigma, =1)=L(\ensuremath{{{\overline{\Sigma}}}},=1)$ because the derivations are the same in the two systems, the only difference is that in $\ensuremath{{{\overline{\Sigma}}}}$ both the INS-type rules and the REP-type rules of $\Sigma$ are contracted into one set.

$4.$
We have to show that two language classes ${\mathcal L}(E_{H}(n,=k))$ and ${\mathcal L}(E_{H}(m,=\ell))$ are incomparable if $k\not = \ell$.

If $k>\ell\geq 1$, then $L_H(n(k),=k)\in {\mathcal L}(E_{H}(n,=k))\setminus {\mathcal L}(E_{H}(m,=\ell))$ holds by Lemma 4.9 (for the definition of the language $L_H(n(k),=k)$ see Example 4.5).

On the other hand, first we deal with the case $2\leq \ell< k$ and we prove that $L_H(m({\ell}),={\ell})\in {\mathcal L}(E_{H}(m,={\ell}))\setminus {\mathcal L}(E_{H}(n,=k))$ if $2\leq {\ell}<k$. First we show that if $L_H(m({\ell}),={\ell})=L(\Sigma,=k)$ with a hybrid eco-grammar system $\ensuremath{\Sigma=(\:V_E,P_E,n_1,R_1,\ldots,R_n, \omega\:)}$, then $P_E$ does not contain the rule $a_1\ensuremath{\rightarrow}\lambda$.

If $P_E$ has this rule, then the REP-type agents could not introduce letters $c$, since by using a replacement rule which introduce a letter $c$ and the erasing rule of $P_E$ for all letters preceding the first letter $c$, we would generate a word whose first symbol is a letter $c$. (Here we use that Lemma 4.7 can be applied for $L_H(m({\ell}),={\ell})$ with $L_1=L_H(m({\ell}),={\ell})\cup{\{a_1\}}^*$ and hence words containing letters $c$ can be derived only from words being over ${\{a_1\}}^*$).

Because of the same reason, all insertion rules introducing a letter $c_i$ must be in the form $({a_1}^{i_1},{a_2}^{j_1}\gamma {a_2}^{j_2},{a_1}^{i_2})$ (with $i_1,i_2,j_1,j_2\geq 1$, $c_i\preceq\gamma$), so that we could avoid the letters $c_i$ as the first or as the last symbol of the words.

Since the environment cannot introduce letters $c$ ($a_1$ is a letter with unbounded occurrence), the only possibility to introduce them is to use these insertion rules. But with these rules we cannot introduce sub-words $c_ic_j$, which is a contradiction. (It is not possible either to produce these sub-words by one agent; we can see this by using the same idea as the one used in Lemma 4.9.) Thus we have proved that $a_1\ensuremath{\rightarrow}\lambda$ is not a possible rule in $P_E$.

In $L_H(m({\ell}),={\ell})$ the shortest word containing letters $c$ is in the form of $a_2{[c_1,c_2,\ldots, c_{\ell}]}^Pa_2$. This word must be derived in ${\Sigma}$ from the word ${a_1}^2$ because this is the only shorter word in the set $L_H(m({\ell}),={\ell})\cap {a_1}^*$ (here we use again the fact that we can apply Lemma 4.7 to the language $L_H(m({\ell}),={\ell})$).

We know that $P_E$ cannot use erasing rule during this step and we also know that REP-type agents cannot perform any actions on ${a_1}^2$ because it contains only two symbols. It means that in this step at most ${\ell}$ (INS-type) agents can work, that is, $k\leq {\ell}$, which is a contradiction because we supposed that $k>{\ell}$.

To complete the proof, we show that if $2\leq k$, then $L=\{a^2,b\}\in {\mathcal L}(E_{H}(m,=1)\setminus {\mathcal L}(E_{H}(n,=k))$.
It is clear that $L$ can be generated by the following hybrid EG system $\Sigma=(\;V_E, P_E, m, R_1, \ldots, R_m, \omega\;)$ in mode $=1$:

• $V_E=\{a,b\}$,
• $P_E=\{a\ensuremath{\rightarrow}\lambda,b\ensuremath{\rightarrow}\lambda\}$,
• $R_i=\{(a,b,a)\}$ for $1\leq i\leq m$, and
• $\omega=a^2$.

On the other hand, if $L$ is generated by a hybrid EG system $\ensuremath{{{\overline{R_1}}}},\ldots,\ensuremath{{{\overline{R_n}}}},\ensuremath{{{\overline{\omega}}}}\:)$ in mode $=k$, then $a^2$ must be the axiom in $\ensuremath{{{\overline{\Sigma}}}}$ because agents cannot apply rules to words consisting of one letter. Thus $a^2\ensuremath{{\Rightarrow}_{\ensuremath{{{\overline{\Sigma}}}}}}b$ is a derivation step in $\ensuremath{{{\overline{\Sigma}}}}$. But in this step at most one agent can be active, which gives $k\leq 1$, a contradiction with the supposition $k\geq 2$.height 5pt width 5pt depth 0pt

Now we turn our attention to language classes ${\mathcal L}(E_H(n,=k_1,=k_2))$ generated with different $n$, $k_1$ and $k_2$. The results are similar to the $=k$ case: there is a hierarchy according to the number of the agents if $k_1$ and $k_2$ are fixed, otherwise the language classes are incomparable.

Theorem 4.11  
For $0\leq k_1,k_2,{\ell}_1,{\ell}_2$, $1\leq k_1+k_2\leq n$ and $1\leq {\ell}_1+{\ell}_2\leq m$

1. ${\mathcal L}(E_{H}(n,=k_1,=k_2))\subset {\mathcal L}(E_{H}(m,=k_1,=k_2))$ if $k_1+k_2\geq 2$ and $m>n$,
2. ${\mathcal L}(E_{H}(n,=1,=0))={\mathcal L}(E_{H}(m,=1,=0))$,
3. ${\mathcal L}(E_{H}(n,=0,=1))={\mathcal L}(E_{H}(m,=0,=1))$,
4. otherwise ${\mathcal L}(E_{H}(n,=k_1,=k_2))$ and ${\mathcal L}(E_{H}(m,={\ell}_1,={\ell}_2))$ are incomparable.

PROOF.
$1.$
Using the same construction as in part 1 of Theorem 4.10, we obtain that ${\mathcal L}(E_{H}(n,=k_1,=k_2))\subseteq {\mathcal L}(E_{H}(m,=k_1,=k_2))$ if $k_1+k_2\geq 1$ and $m>n$. Applying Lemma 4.9 to $L_H(m,=k_1,=k_2)$, we can see that the inclusion is proper if $k_1+k_2\geq 2$ and $m>n$ (for the definition of the language $L_H(m,=k_1,=k_2)$ see Example 4.5).

$2.$ and $3.$
These parts can be proved by using constructions similar to the ones used in the proof of part 3 of Theorem 4.10: we can contract all the REP-type rules and all the INS-type rules into one set.

$4.$
We have to prove that the two language classes ${\mathcal L}(E_{H}(n,=k_1,=k_2))$ and ${\mathcal L}(E_{H}(m,={\ell}_1,={\ell}_2))$ are incomparable if $k_1\not = {\ell}_1$ or $k_2\not = {\ell}_2$. For any $0\leq k_1,k_2,n$, $1\leq k_1+k_2\leq n$ we present a language which cannot be derived by any hybrid eco-grammar system in mode $(={\ell}_1,={\ell}_2)$ if ${\ell}_1\not =k_1$ or ${\ell}_2\not =k_2$.

First we consider the case when $k_1+k_2\geq 2$. Applying Lemma 4.9 to $L_H(n,=k_1,=k_2)$ (see Example 4.5), we obtain that if $L_H(n,=k_1,=k_2)=L(\Sigma,={\ell}_1,={\ell}_2)$ with a hybrid eco-grammar system $\Sigma=(\:V_E,P_E,m_1,R_1,\ldots,$ $R_m,\omega\:)$, then ${\ell}_1+{\ell}_2\geq k_1+k_2$. Since $k_1+k_2\geq 2$, we can use the same idea as in part 4 of Theorem 4.10 and we can conclude that $P_E$ cannot contain the rule $a_1\ensuremath{\rightarrow}\lambda$. Using this fact and examining the rules used in the derivation step ${a_1}^{k_2+2}\ensuremath{\stackrel{(={\ell}_1,={\ell}_2)}{{\Longrightarrow}_{\Sigma}}}{a_2} {[c_1,\ldots,c_{k_1},c_{i_1},c_{i_2},\ldots,c_{i_{k_2}}]}^Pa_2$ (which is the only possibility to derive the latter word in $\Sigma$) we obtain that ${\ell}_2\leq k_2$ and ${\ell}_1\leq k_1$. Since $k_1+k_2\leq {\ell}_1+{\ell}_2$, we have ${\ell}_1=k_1$ and ${\ell}_2=k_2$. This gives that $L_H(n,=k_1,=k_2)\in {\mathcal L}(E_{H}(n,=k_1,=k_2))\setminus {\mathcal L}(E_{H}(m,={\ell}_1,={\ell}_2))$, if $k_1+k_2\geq 2$ and ${\ell}_1\not =k_1$ or ${\ell}_2\not =k_2$.

For completing the proof, we construct two languages which show the incomparability when $k_1+k_2=1$.

In the case $k_1$=1, $k_2=0$ $L=\{a^2,b\}\in {\mathcal L}(E_{H}(n,=1,=0))\setminus {\mathcal L}(E_{H}(m,={\ell}_1,={\ell}_2))$ holds if ${\ell}_1\not = 1$ or ${\ell}_2\not =0$ by the same reason as in part 4 of Theorem 4.10.

In the other case, that is, when $k_1$=0 and $k_2$=$1$, the language generated by the following hybrid EG system $\Sigma$ in mode $(=0,=1)$ shows the incomparability: this language cannot be generated by hybrid EG systems in mode $({\ell}_1,{\ell}_2)$ if ${\ell}_1\not =0$ or ${\ell}_2\not = 1$.

Let $\Sigma=(\:V_E,P_E,0,R_1,\ldots,R_n, \omega\;)$ be the following hybrid EG system:

• $V_E=\{a_1,a_2,b_1,b_2,d\}$,
• $P_E=\{a_1\ensuremath{\rightarrow}{a_2}^2,a_2\ensuremath{\rightarrow}{a_1}^2,b_... ...rrow}{b_2}^2, b_2\ensuremath{\rightarrow}{b_1}^2,d\ensuremath{\rightarrow}a_1\}$,
• $R_i=\{(a_1,a_1,b_1)\ensuremath{\rightarrow}(a_1,d,b_1), (a_2,d,b_2)\ensuremath{\rightarrow}(a_2,a_1,b_2)\}$ for $1\leq i \leq n$,
• $\omega=a_1a_1b_1$.

It is clear that the generated language in derivation mode $(=0,=1)$ is

$$L_{REP}(=1):=L(\Sigma, =0,=1)= \{{a_1}^{4^k}a_1{b_1}^{4^k}, {a_2}^{2\cdot4^k}d{b_2}^{2\cdot4^k}\;\vert\;0\leq k\;\}.$$

Let us suppose that $L(\Sigma, =0,=1)=L(\ensuremath{{{\overline{\Sigma}}}},={\ell}_1,={\ell}_2)$ with a hybrid EG system $\ensuremath{\ensuremath{{{\overline{\Sigma}}}}= (\:\ensuremath{{{\overline{V_E... ...,\ldots,\ensuremath{{{\overline{R_m}}}}, \ensuremath{{{\overline{\omega}}}}\:)}$. By Lemma 4.7 we can say that in $\ensuremath{{{\overline{\Sigma}}}}$ the words in a derivation sequence are alternately over $\{a_1,b_1\}$ and $\{a_2,b_2,d\}$.

$\ensuremath{{{\overline{P_E}}}}$ cannot introduce the letter $d$, because in this case more than one letters $d$ would be in some words (since $a_1$ and $b_1$ are letters with unbounded occurrence). Moreover, for all the rules $a_1\ensuremath{\rightarrow}\alpha$ and $b_1\ensuremath{\rightarrow}\beta$ of $\ensuremath{{{\overline{P_E}}}}$ $\alpha={a_2}^{i_1}$ and $\beta={b_2}^{i_2}$ hold, otherwise words with mixed letters $a$ and $b$ or words starting with a letter $b$ or ending with a letter $a$ would be in the generated language. $\ensuremath{{{\overline{P_E}}}}$ cannot contain rules in the form of $a_1\ensuremath{\rightarrow}\lambda$ or $b_1\ensuremath{\rightarrow}\lambda$ because in this case the number of letters $a_2$ or $b_2$ would be bounded in the generated words. Similarly, for all rules $a_2\ensuremath{\rightarrow}\alpha$ or $b_2\ensuremath{\rightarrow}\beta$ of $\ensuremath{{{\overline{P_E}}}}$ $\alpha\in {a_1}^*$ and $\beta\in {b_1}^*$ must hold and $\ensuremath{{{\overline{P_E}}}}$ cannot contain the rules $a_2\ensuremath{\rightarrow}\lambda$ and $b_2\ensuremath{\rightarrow}\lambda$.

Since $\ensuremath{{{\overline{P_E}}}}$ cannot contain erasing rules, the only possibility to derive the word ${a_2}^2d{b_2}^2$ is the derivation step ${a_1}^2b_1\ensuremath{{\Rightarrow}_{\Sigma}}{a_2}^2d{b_2}^2$.

Considering the lengths of these two words, there are five possibilities for $({\ell}_1,{\ell}_2)$:

1. ${\ell}_1=0,\; {\ell}_2=1$
2. ${\ell}_1=1,\; {\ell}_2=0$
3. ${\ell}_1=1,\; {\ell}_2=1$
4. ${\ell}_1=2,\; {\ell}_2=0$
5. ${\ell}_1=2,\; {\ell}_2=1$.

Case ${\ell}_2=0$ is not possible, i.e. at least one REP-type agent must apply a rule in each derivation step, because otherwise we could not determine the exact position of the letter $d$ and we could derive words where the letter $d$ does occur in the middle of a sequence of letters $a$ or $b$. This excludes cases $2$ and $4.$

In case 5 the replacement rule used in the derivation step must be $(a_1,a_1,b_1)\ensuremath{\rightarrow}(a_1,d,b_1)$. (The letter $d$ cannot be introduced by insertion because in this case we could not determine the exact position of it.) It is also sure that we have to use the rule $(a_1,b_2,b_1)$ or $(a_1a_1,b_2,b_1)$ for introducing a letter $b_2$. But with this last insertion rule we could also insert a letter $b_2$ in the middle of a sequence of letters $a_2$, which is a contradiction.

In case 3 when ${\ell}_1={\ell}_2=1$, we have two possibilities for the rules in the derivation step ${a_1}^2b_1\ensuremath{{\Rightarrow}_{\Sigma}}{a_2}^2d{b_2}^2$. The letter $d$ is introduced by a replacement and either the environment uses the rule $a_1\ensuremath{\rightarrow}{a_2}^2$ and one INS-type agent introduces a $b_2$ by a rule of type $(a_1,b_2,b_1)$, $(a_1a_1,b_2,b_1)$ or the environment uses the rule $a_1\ensuremath{\rightarrow}{a_2}$ and one INS-type agent uses the rule $(a_1,a_2,a_1)$, $(a_1,a_2,b_1)$, or $(a_1,a_2,a_1b_1)$.

The first case is not possible because of the same reason as in case 5. The second case implies that $a_1\ensuremath{\rightarrow}{a_2}$ is the only rule in $\ensuremath{{{\overline{P_E}}}}$ to rewrite $a_1$, otherwise more then one word in the form of ${a_2}^id{b_2}^2$ could be generated. But in this case for all derivation steps ${a_1}^{4^k}a_1{b_1}^{4^k}\ensuremath{{\Rightarrow}_{\ensuremath{{{\overline{\Sigma}}}}}} {a_2}^{2\cdot4^j}d{b_2}^{2\cdot4^j}$ the difference $2\cdot4^j-4^k$ would be bounded, which is impossible. Thus the only possibility is ${\ell}_1=0, {\ell}_2=1$. height 5pt width 5pt depth 0pt

Finally, we show that hybrid EG systems are more powerful than homogeneous INS- or REP-type systems.

Remark 4.12  
${\mathcal L}(E_I)\cup {\mathcal L}(E_R)\subset{\mathcal L}(E_H)$

PROOF.
The inclusion holds by definition. On the other hand, using the same language and the same idea as in the proof of part 2 of Theorem 4.10, we obtain that the language defined there cannot be generated by a hybrid EG system which contains only INS- or only REP-type agents.height 5pt width 5pt depth 0pt