next up previous contents
Next: Generative power of some Up: Structure of the dissertation Previous: Structure of the dissertation   Contents

Team behaviour of variants of simple eco-grammar systems

As presented in the previous section, the original eco-grammar system model proved to have universal generative power. Simple eco-grammars systems were also examined from this point of view, one of the first works in this field was the study of the so called ``team behaviour''.

The concept of a team, which was introduced into grammar systems theory in [Kari, Mateescu, Paun, and SalomaaKari et al.1995], appears in eco-grammar systems theory in two different forms. Prescribed teams are discussed in [ter Beekter Beek1999]: in this case the definition of the system contains the specification of those groups of agents which can work together in a derivation step. This team concept is discussed later.

Another approach is to consider team derivation modes. In the original definition of simple eco-grammar systems all the agents have to work, otherwise the derivation is blocked. Derivation mode $ =k$ modifies this definition in a natural way: it prescribes that in each derivation step exactly $ k$ agents work. Thus, in this derivation mode any $ k$ agents can form a team and can work together.

The first investigations concerning the derivation mode $ =k$ were done about non-extended systems where all the generated words are in the corresponding language. The results appeared in [Csuhaj-Varjú and KelemenováCsuhaj-Varjú and Kelemenová1998] and showed that the parameters, the number of the agents in the system and the number of the agents working in a derivation step, are very important. In Chapter 3 first we review these results, then we deal with the extended case, which was examined in [CsimaCsima1998a]. In an extended simple eco-grammar system the generated strings are filtered: only words over a distinguished sub-alphabet are in the corresponding language. It is proved that, unlike the non-extended case, in the extended case the parameters are not important: we obtain a collapsing hierarchy.

In Chapter 4 we continue our investigations on the team behaviour but we consider simple eco-grammar systems with agents using new operations, motivated by genetics: insertion and replacement. An insertion rule can insert a word into the sentential form if both the left and the right context is present somewhere in the string. By a replacement rule, the agent can change a letter if the prescribed neighbouring context is present.

We combine these operations with the concept of simple eco-grammar systems in two different ways. We can consider simple eco-grammar systems of type INS and REP, where the agents are homogeneous or we can study a more complicated model by allowing the possibility of different agents having different types of rules. These models intend to examine nature-motivated decentralised systems.

For hybrid eco-grammar systems we define the derivation modes $ =k$ and the $ =k_1, =k_2$ . In the $ =k$ case we prescribe how many agents (chosen freely without any further restriction) have to work in one derivation step, while in the derivation mode $ (=k_1, =k_2)$ the number of INS-type and REP-type agents is also specified.

In the first part of Chapter 4 the relation of language classes generated by hybrid eco-grammar systems with different parameters is studied as presented in [CsimaCsima1999]. It is proved that the number of agents working in one step is a significant parameter, while the number of agents being in the system is not.

Simple eco-grammar systems of type INS and REP are special cases of hybrid eco-grammar systems, therefore some techniques used for hybrid systems can be applied to homogeneous systems as well. Although in this way the results about INS- and REP-type systems can be obtained easily, in the second part of the chapter we present these results in detail. The reason to do this is to emphasise the striking similarity between the original case, i.e. when the agents are represented by CF rules and this case, when the agents use insertions and replacements.

At the end of Chapter 4 we compare language classes generated by homogeneous CF-, INS-, or REP-type simple EG systems and we prove that these language classes are pairwise incomparable.


next up previous contents
Next: Generative power of some Up: Structure of the dissertation Previous: Structure of the dissertation   Contents
Csima Judit 2002-01-04