Summary

Eco-grammar systems are formal language theoretical models, introduced to formalise the concept of eco-systems consisting of several agents which share a common environment. In this model, the string describing the environment can be changed by sequential rewritings done by the agents and a parallel evolution performed by the environment itself. The complexity of the system can be described by the generated language, which is the set of all strings representing the environment during the derivations.

In this work, we examine how the changes in the derivation mode, in the nature of the agents, and in other parameters affect the generative capacity of simple eco-grammar systems.

First we investigate team behaviour of the agents and we determine the important parameters of teams both in the original case and also in the case when the agents are represented by sets of nature-motivated rules, insertion and replacement.

Next, we study the generative capacity of two variants of simple eco-grammar systems. We prove that all recursively enumerable languages can be generated in both cases.

Finally, we investigate standard Watson-Crick eco-grammar systems, where Watson-Crick complementarity, one of the crucial features of DNA computing, is introduced into the original concept of eco-grammar systems. We show that these systems also have universal generative power.