next up previous contents
Next: Watson-Crick complementarity Up: Structure of the dissertation Previous: Team behaviour of variants   Contents

Generative power of some variants of simple eco-grammar systems

While in Chapter 3 and Chapter 4 we study generative power by comparing language classes generated with different parameters, in Chapter 5 we introduce two variants of the original model and we show that the generative power of Turing machines can be achieved in both cases.

In Chapter 3 we found that the hierarchy of extended simple eco-grammar language classes collapses into one language class, but the place of this language class remained an open problem. From [Dassow and MihalacheDassow and Mihalache1995] we know that it is between two well-known language classes, the class of languages generated by extended Lindenmayer systems (E0L) and the class of languages generated by matrix grammars with appearance checking with $ \lambda$-rules. It is also known from an example that this language class contains at least one non-E0L language.

While trying to determine the generative power of this language class more precisely, we found two different modifications of simple eco-grammar systems which have universal generative power. Our achievements improve the results of [ter Beekter Beek1999], where the generative power of extended tabled simple eco-grammar systems with prescribed teams was examined in two different derivation modes. By the strong derivation all the agents of a team must work in a derivation step, by the weak rewriting only those agents of the team have to work which have rules applicable for the sentential form. Extended tabled simple eco-grammar systems with teams of agents with prescribed members and operating according to a weak derivation mode proved to be very powerful devices: it was proved in [ter Beekter Beek1999] that they can generate all recursively enumerable languages. As far as the strong derivation mode is concerned, it was stated as an open problem whether universal power can be achieved in this case, too.

In Chapter 5 we consider two variants of extended simple eco-grammar systems, neither of which contain prescribed teams: extended tabled simple eco-grammar systems and weak extended simple eco-grammar systems. In an extended tabled simple eco-grammar system the environment can be represented by more than one set of rules, called tables, thus the environment can vary its behaviour step by step. In weak extended simple eco-grammar systems the definition of the derivation step is modified: during the computation the derivation is not blocked if some of the agents cannot perform any action on the sentential form.

We solve the open problem presented in [ter Beekter Beek1999] in a stronger form by proving that extended tabled simple eco-grammar systems without prescribed teams can generate all recursively enumerable languages by using the original, i.e. the strong derivation mode. We also prove that weak extended simple eco-grammar systems (without tables and without prescribed teams) achieve the same generative power.


next up previous contents
Next: Watson-Crick complementarity Up: Structure of the dissertation Previous: Team behaviour of variants   Contents
Csima Judit 2002-01-04