New operations in simple eco-grammar systems

New operations

In this chapter we consider simple eco-grammar systems with agents using new operations, namely insertion and replacement. These operations, motivated by genetics, became a topic in the focus of interest and have been studied intensively in formal language theory. (See [KariKari1991], [Kari and ThierrinKari and Thierrin1996] and  [Dassow and MitranaDassow and Mitrana1997].)

Combining insertion and replacement with the concept of the simple eco-grammar system, in the simple case we obtain the definition of the simple eco-grammar system of type $X$, with $X\in \{$INS$,$REP$\}$. A simple eco-grammar system of type $X$ is nothing more than a simple eco-grammar system with a slight modification: all agents are represented by sets of type $X$ rules. (According to this notation, the original model, when the agents are represented by CF rules, is a simple eco-grammar system of type CF. )

We get a more complicated model if we allow the possibility of different agents having different types of rules. In these hybrid eco-grammar systems there are agents of type INS and REP at the same time.

For hybrid systems we define two derivation modes: the derivation modes $=k$ and $(=k_1, =k_2)$. In the former case only the number of agents working in a derivation step is prescribed while in the latter case both the number of INS-type and the number of REP-type agents are determined. In the first part of the chapter the relation of language classes generated by hybrid eco-grammar systems with different parameters $n$ and $k$ (or $k_1, k_2$) is studied and it is shown that parameters $k$ and $k_1$,$k_2$ are significant, the language families defined by these restrictions with different $k$ (or $k_1, k_2$) are pairwise incomparable.

In homogeneous systems we consider the same two parameters as in Chapter 3: the number of agents being in the system and the number of agents working in a derivation step. In the second part of the chapter we examine the role of these parameters by using the same ideas as in the hybrid case. Since simple eco-grammar systems of type INS and REP are special cases of hybrid eco-grammar systems, the techniques used and the results obtained in the derivation modes $(=0,=k_2)$ and $(=k_1, =0)$ in the hybrid case can be applied for these homogeneous systems as well.

The results about simple eco-grammar systems of type INS and REP show striking similarity to the results presented in Chapter 3 about EG systems of type CF: only the value of the parameter $k$ proves to be important.

At the end of the chapter the relation between language classes generated by systems of different types (i.e. INS, REP or CF) is examined and it is shown that the corresponding language classes are pairwise incomparable. Thus we prove that the type of the rules of the agents is also an important parameter of the system.

The results about the homogeneous systems were presented in [CsimaCsima1997]. The stronger results about hybrid eco-grammar systems appeared first in [CsimaCsima1998b], then a refined and completed version was published in [CsimaCsima1999].