When one agent is unable to perform a complex task or tackle a specific problem due to its limited capabilities, it is natural to try to solve the problem by more than one agent. This idea motivates the notion of multi-agent system, which has two different approaches in Artificial Intelligence (AI): distributed and decentralised AI.
Distributed AI is concerned with the cooperative solution of problems. Here several agents interact with each other, following a given strategy; the communication and interaction protocols of the agents are well-defined in advance.
First models of grammar systems theory are mainly motivated by distributed AI. The idea of cooperating grammars was first presented in [Meersman and RozenbergMeersman and Rozenberg1978], but the development of this area started only in 1988, when the notion of the cooperating distributed grammar system (CD grammar system, for short) was introduced in [Csuhaj-Varjú and DassowCsuhaj-Varjú and Dassow1990] and in [Csuhaj-Varjú and KelemenCsuhaj-Varjú and Kelemen1989].
The concept of CD grammar systems was proposed as a syntactic model of the blackboard architecture of problem solving (see [NiiNii1989]), where several independent agents work together on the solution of a problem by cooperating with each other only by modifying the common blackboard representing the current state of problem solving.
In a CD grammar system the agents are generative grammars and the global data base is represented by a string, called sentential form. The agents take turns in rewriting the sentential form according to a cooperation strategy, called derivation mode. The successful problem solving is achieved by generating a terminal word. CD grammar systems were the first formal language theoretical models formalising distributed computation. It demonstrated that complex behaviour, i.e. complex languages can be generated by simple grammars using a simple cooperation strategy. For an overview about CD grammar systems see [Csuhaj-Varjú, Dassow, Kelemen, and PaunCsuhaj-Varjú et al.1994] and [Dassow, Paun, and RozenbergDassow et al.1997].
While CD grammar systems use sequential rewriting (in each derivation step only one grammar is active), parallel communicating grammar systems (PC grammar systems, for short) introduce parallelism into grammar systems theory, thus providing theoretical models for parallel, distributed computation. PC grammar systems are motivated by another problem solving model of distributed AI, the classroom model. In this model each agent can operate only on its own ``notebook'' and only one component, the master can use the blackboard. The agents work in parallel and they can communicate by sending their ``notebooks'' to each other.
In a PC grammar system (introduced in [Paun and SânteanPaun and Sântean1989]) the components are generative grammars working on their own sentential forms in parallel and communicating with each other by sending their sentential forms by request. The language generated by the system consists of those words which can appear as the sentential form of the master. A good overview on PC grammar systems and several of the most important results about the role of synchronisation, different ways of communication, generative capacity, and size complexity can be found in [VaszilVaszil2000], [Csuhaj-Varjú and SalomaaCsuhaj-Varjú and Salomaa1998] and [Csuhaj-VarjúCsuhaj-Varjú1999].
Based on the general idea of grammar systems theory, several other models have been introduced and studied, for a short overall review see [VaszilVaszil2000] and [Csuhaj-VarjúCsuhaj-Varjú2000]. We presented here the above two fundamental models, CD and PC grammar systems specially because eco-grammar systems, the subject of our study, can be viewed as a generalisation of both of them.
While the concept of CD and PC grammar systems is inspired by distributed AI, decentralised AI and Artificial Life (AL) give motivations for models like colony and eco-grammar system. Decentralised AI deals with the study of multi-agent systems of autonomous agents. In these systems the communication and cooperation is minimised, there is no predefined strategy (unlike in distributed AI), the properties of the system emerge only from the intensive interaction of the agents and the environment. AL studies man-made systems that exhibit behaviours characteric of natural living systems (see [LangtonLangton1989]). Its models have similar properties to those of decentralised AI: they consist of a population of simple agents reacting on a common environment without any master component, which would direct their behaviour or coordinate their work. Life-like features are the result only of the interaction of the components and the environment.
The idea of emergence, that is, when intelligent, complex behaviour is resulted from the interaction of the agents with their shared environment, is common in these approaches and it is this paradigm, together with the general concept of grammar systems theory, that leads to models of colony and eco-grammar system.
The colony, (introduced in [Kelemen and KelemenováKelemen and Kelemenová1992]), which is the first model describing the above ideas within formal language theory, is motivated mainly by reactive agents studied in robotics (see [KelemenKelemen1998] and [BrooksBrooks1999]). This model retains the idea of CD and PC grammar systems of having grammars as components working together but in a colony these grammars are simple regular grammars generating finite languages and there is no cooperation between them. The model also has an environment component, which is represented by a string. The state of the system can be changed only by the actions of the agents; the environment is passive, it does not change its state autonomously. The agents can alter the string representing the environment by sequential rewritings. Due to the lack of any predefined strategy, each grammar participates in the rewriting whenever it can, conflicts are resolved nondeterministically. The language generated by the colony is the set of all the possible states of the environment.
Several derivation modes and acceptance styles were introduced and studied (see [Csuhaj-Varjú and KelemenováCsuhaj-Varjú and Kelemenová1994], [Dassow, Kelemen, and PaunDassow et al.1993] and [Csuhaj-VarjúCsuhaj-Varjú1999] for formal definitions and results) and colonies proved to show emergent behaviour indeed: the components are very simple regular grammars, but powerful, large language classes can be generated in this way.
Although the colony formalises several features of multi-agent systems, for better understanding agents behaving in a dynamic environment this model is not suitable because its environment component is quite passive. To eliminate this shortcoming, a new model was created, the eco-grammar system, which is provided with an active environment component as well. The original eco-grammar system differs from colonies in the nature of the agents, too: here the agents are not purely reactive entities, they have an inner representation both for the environment and also for themselves. Eco-grammar systems are introduced in detail in the next section.
Grammar systems theory provides and studies several different models. It proves that language can be considered a collective product of several components and that key notions of present-day computation, like cooperation, communication and emergent behaviour can be formalised within its framework. By studying its models we obtain a better understanding of the phenomena of distributed computation and distributed systems. See [Dassow, Paun, and RozenbergDassow et al.1997] for an overview of the theory until 1996 and [Csuhaj-VarjúCsuhaj-Varjú2000] for a more recent, short summary. The reader interested in the motivations of grammar systems theory is referred to [KelemenKelemen1999].