Eco-grammar systems

Eco-grammar systems (EG systems, for short), as presented in [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1994] and  [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997], were introduced to formalise the concept of ecosystems consisting of several agents living together in a common environment. The model assumes that both the agents and also the environment evolve, the environment independently of the agents, the agents dependently on the environment. Moreover the agents can sense the environment and can change it.

The original model was based on the following six postulates:

1. An ecosystem consists of an environment and a set of agents. Both the state of the environment and the states of the agents are described by strings of symbols.
2. In an ecosystem there is a synchronised universal clock, which divides the time in units. In each time unit the environment and the agents together perform a derivation step.
3. Both the environment and the agents have evolution rules, which are rules of Lindenmayer systems, hence are applied in a parallel manner to all the symbols describing the states of the agents and of the environment; such a (rewriting) step is done in each time unit.
4. The evolution rules of the environment are independent of the agents and of the state of the environment itself. The evolution rules of the agents depend on the state of the environment (at a given moment, a subset of the rules is chosen from a general set associated to each agent).
5. The agents act on the environment according to action rules, which are rewriting rules used in context-free manner. In each time unit, each agent uses one action rule, chosen from a set depending on the current state of the agent.
6. The action (of agents on the environment) has priority over the evolution of the environment; in a given time unit, those symbols of the environment which are not affected by the actions of the agents are rewritten (in parallel manner) by the evolution rules.

According to these postulates, an eco-grammar system can be imagined as presented in Figure 1.2.

Figure 1.1: Original version of eco-grammar systems

The environment is described by a string $w_E$ and evolves according to a set of rules $P_E$ of a Lindenmayer system. The agent $A_i$ is described by a string $w_i$ and evolves according to the rules of the set $P_i$. At every moment, only a subset of these rules is active, this subset is chosen by $\varphi_i$ depending on $w_E$, the string of the environment. Each agent $A_i$ is provided by a set $R_i$ of rewriting rules, too, by which it can modify the environment in a sequential manner. At each step, only a subset of $R_i$ is active, depending on the current state of the agent. This subset is chosen by the function ${\psi}_i$.

The life of the system is governed by a universal clock, dividing the time in unit intervals: in each step first the agents act on the environment (each agent rewrites one of the symbols), then the evolution rules of the environment rewrites in parallel all the remaining symbols of the string of the environment. The strings of the agents are also rewritten in a parallel way, according to the chosen subsets of the sets $P_i$.

In this model both the environment and the agents have inner representations and the interaction is quite sophisticated between the different components. The difference between action and evolution (presented as sequential and parallel rewriting in the model) is due to the fact that evolution is a global, parallel process, while the actions of the agents are local. The behaviour of the whole system is represented by the environment's sentential form, thus the generated language consists of these strings.

Although motivated mainly by the ecosystem concept of Artificial Life, the eco-grammar system is a formal language theoretical model, being within the framework of grammar systems theory. Not only this model is a developed variant of colonies (as presented in the previous section), but it keeps some properties of both CD and PC grammar systems. It has only one sentential form (the string of the environment is the only one which determines the generated language) and this word can be changed by the component grammars like in a CD grammar system. However, the components can evolve in parallel, which is a feature common with PC grammar systems.

In [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997] eco-grammar systems were studied from different points of view. It was found there that from artificial life point of view, i.e. when the life-cycle and the derivation sequences are investigated, the evolution of the system can be extremely complex. From generative point of view it was proved that all recursively enumerable languages can be generated by eco-grammar systems with a very simple choice of the functions ${\varphi}_i$ and ${\psi}_i$. These two facts together pointed in the direction of simplifying the original definition and led to simple eco-grammar systems.

The simple eco-grammar system model preserves the dynamic environment from the original definition, but otherwise the concept of the agent is similar to the one presented in colonies: the agents do not evolve and their acting on the environment is independent of the state of the system. This means that the functions ${\varphi}_i$, ${\psi}_i$ and the inner representations of the agents can be omitted, thus getting the picture represented in Figure 1.2.

Figure 1.2: Simple eco-grammar system

Briefly, a simple eco-grammar system consists of several agents, represented by sets of context-free rules and an environment, given by a set of rules of a Lindenmayer system. The state of the system is described by the state of the environment, which is a string over the alphabet of the system. The environmental state changes by derivation steps. In a derivation step the agents act on the string by applying one of their context-free rules--each agent rewrites one letter--and the environment replaces those symbols where the agents do not perform any action, according to its set of rules, in a parallel way.

The advantages of simple eco-grammar systems are two-fold: on the one hand, simple eco-grammar systems have a closer connection with the ideas which motivate colonies, thus by examining it we better understand the ideas of emergent computations, while on the other hand we have a model which is not too strong in the generative sense but at the same time provides interesting features.

The subject of this dissertation is the study of simple eco-grammar systems. In the next section we summarise our results and settle them among the other works done on this field. Before doing so, we mention some models and fields grown from the original definition of eco-grammar system.

At the beginning, besides the study of generative power, eco-grammar systems were examined from artificial life point of view (see [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997] and [Csuhaj-VarjúCsuhaj-Varjú1995]). Developed models such as symbiotic eco-grammar systems, stratified eco-grammar systems, and reproductive eco-grammar systems were proposed to formalise the notions of population dynamics: symbiosis, parasitism, competition and reproduction.

Recently, eco-grammar systems have been also used to model natural languages (see [Csuhaj-VarjúCsuhaj-Varjú1996]) and to describe phenomenon of linguistics (see [Csuhaj-Varjú, Jiménez-López, and Martín-VideCsuhaj-Varjú et al.1999] and [Csuhaj-Varjú and Jiménez-LópezCsuhaj-Varjú and Jiménez-López1998]). For a thorough study of this subject, the reader is referred to  [Jiménez-LópezJiménez-L´opez2000], which well demonstrates how grammar systems theory and especially eco-grammar systems can be used to model natural languages.

There is another variant of the model, which was studied intensively from formal language theoretical point of view, the conditional tabled eco-grammar system. It was intended to describe the interplay between an environment and some agents with non-local influence. In this model not only the evolution of the agents depend on the environment but the evolution of the environment depends on the agents as well. For technical details and result see [Csuhaj-Varjú, Paun, and SalomaaCsuhaj-Varjú et al.1995] and [SosikSosik1999].