Generative power of variants of simple eco-grammar systems

Generative power of some variants

In Chapter 3 results about team behaviour of extended simple eco-grammar systems were collected (see Figure 3.2). There we found that in the general case (i.e. when $\lambda$-rules are allowed) the hierarchy of extended simple eco-grammar language classes is a collapsing one: all the language classes are equal to ${{\mathcal L}}({EE}^{\lambda}(1,= 1))$.

The place of this language class remained an open problem, the only known result is that it is strictly larger than the class of languages generated by extended 0L systems (see Example 2.7) and that it is included in the class of languages generated by matrix grammars with appearance checking with $\lambda$-rules ( ${\mathcal{M}}_{ac}^{\lambda}$) (see [Dassow and MihalacheDassow and Mihalache1995]).

The aim of our research was to determine more precisely the generative power of extended simple eco-grammar systems. By examining this question we found two variants of the original model which have universal generative power: the extended tabled simple eco-grammar system and the weak extended simple eco-grammar system.

In an extended tabled simple eco-grammar system instead of only one 0L system, the environment can be represented by more than one set: these 0L systems are called tables. In weak extended simple eco-grammar systems the derivation is different from the original model: in the weak derivation mode the derivation is not blocked if some agents cannot perform any action on the sentential form.

By showing that both models reach the generative power of Turing machines, we solve an open problem in a stronger form as stated in [ter Beekter Beek1999]. The results appeared in [CsimaCsima2000].

At the beginning of the chapter, first we summarise some preliminaries about random-context grammars which we use in the following constructions.