Definitions and previous results in the non-extended case

The first team derivation mode which was studied for simple eco-grammar systems is the derivation mode $=k$, where in each step exactly $k$ agents have to work.

Definition 3.1  
Consider a simple eco-grammar system .
We say that $x$ directly derives $y$ in $\Sigma$ in 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=x_1Z_1x_2Z_2\cdots x_kZ_kx_{k+1}$, with $Z_i\in V_E$, $x_j\in {V_E}^*$, $1\leq i\leq k$, and $1\leq j\leq k+1$,
• $y=y_1w_1y_2w_2\cdots y_kw_ky_{k+1}$, with $y_i, w_j\in {V_E}^*$, $1\leq i\leq k$, and $1\leq j\leq k+1$,
• there exist $k$ different agents in $\Sigma$, namely $R_{j_1},R_{j_2},\ldots,R_{j_k}$, such that
  $Z_i\ensuremath{\rightarrow}w_i\in R_{j_i}$ for $1\leq i\leq k$, and
• $x_1\cdots x_{k+1}=y_1\cdots y_{k+1}=\lambda$ or $x_1\cdots x_{k+1}\ensuremath{{\Rightarrow}_{E}}y_1\cdots y_{k+1}$, where $E=( V_E, P_E, \omega )$ is the 0L system of the environment.

We denote the transitive and reflexive closure of $\ensuremath{\stackrel{=k}{{\Longrightarrow}_{\Sigma}}}$ by $\ensuremath{\stackrel{=k} {{\Longrightarrow}_{\Sigma}^{*}}}$. The generated language consists of those words which can be generated from the axiom in some derivation steps.

Definition 3.2  
Consider a simple eco-grammar system . The generated language in the derivation mode $=k$ is the following:

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

In the following theorem, we summarise the results which are presented in [Csuhaj-Varjú and KelemenováCsuhaj-Varjú and Kelemenová1998] and [CsimaCsima1997], where relations between language classes generated by simple eco-grammar systems with different parameters $n$ and $k$ were examined. (The results of [Csuhaj-Varjú and KelemenováCsuhaj-Varjú and Kelemenová1998] are summarised and completed in [CsimaCsima1997].) Let $\mathcal{L}(E(n,=k))$ denote the class of languages generated by a simple EG system containing $n$ agents and working in the derivation mode $=k$.

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

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