ERCIM News No.28 - January 1997

Grammar Systems - A Language-Theoretic Approach to Distribution and Cooperation

by Erzsébet Csuhaj-Varjú

Grammar systems' is a recent vivid field of formal language theory modelling distributed complex systems. The theory provides highly elaborated frameworks and tools for describing various kinds of multi-agent systems at the symbolic level, from distributed and cooperative problem solving systems to artificial life systems, collective robotics, mentioning only a few. It can be used in DNA computing as well. The area has been intensively investigated by several cooperating research groups from about a dozen of countries (Europe, Canada and Japan) for years.

In present day computer science, artificial intelligence, cognitive psychology and in other related fields we have to deal with complex tasks distributed among a set of agents (processors) which work/live together in some well-defined manner. Parallel computers, computer networks, distributed databases, and knowledge sources are practical materializations of this idea. Similarly, psychologists speak about the modularity of mind, in problem solving theories many models based on cognitive agents' cooperation appear.

Since formal language theory is a well developed theoretical framework for modelling aspects the essence of which can be captured at the level of symbol systems, a challenge appears: how to describe (the behaviour of) multi-agent (complex distributed) symbol systems in terms of language identifying devices. Grammar systems theory attempts to answer this challenge. Roughly speaking, a grammar system consists of several grammars (automata, or other language identifying mechanisms) that cooperate according to some well-defined protocol in deriving sentential forms of a language (or languages). The components of the system correspond to the agents, the current string(s) in generation to a symbolic environment, and the system's behaviour is represented by the language or the string sequences identifying the current state of the system. In addition to distribution, cooperation, communi-cation, other important notions as emergent behaviour can also be formalized in this context.

We illustrate the great variety of models offered by the theory through the most important frameworks:

The investigations started in 1988 by introducing cooperating/distributed grammar systems for modelling the syntactic aspects of the blackboard model of problem solving. In this case the cooperating independent agents are represented by generative grammars which, under some cooperation strategy, derive in turn a common sentential form (the blackboard) in order to generate a common language. The achieved results demonstrate the power of cooperation showing that systems with syntactically very simple components under some appropriate cooperation strategy are able to generate complicated languages of very powerful language classes. Interesting results are, among other things, that any computation under some kind of competence-based cooperation of grammars can be performed in the same kind of system with three co-operating partners. Computation under hybrid (different) cooperation strategies does not need more than four grammars cooperating to determine the same language.

Team grammar systems with simultaneous actions of some grammars in the system (teams) which cooperate in deriving a common sentential form, demonstrate an equivalence between programming the sequence of actions and computation under some kind of competence-based cooperation of freely chosen grammar teams with a very limited number of components.

Colonies, motivated by subsumption architectures of R. Brooks, describe language classes in terms of behaviour of collections of simple, purely reactive, situated agents with emergent behaviour. In this model the agents are represented by very simple regular grammars. The basic variant characterizes the context-free language class, while the more sophisticated models (competition among the agents, timing, etc.) lead to considerably enhanced descriptive power.

Eco-grammar systems are grammatical models of ecosystems: developing grammatical agents in a (dynamically changing) population interact with each other and with their shared evolving symbolic environment. The framework provides tools for describing life-like phenomena (birth, death, hybernation, overpopulation, pollution, etc.) in terms of formal grammars and languages.

Networks of language processors form an essential part of the area. In this case each node of a virtual graph is represented by a language processor (a language identifying device). Each processor works on a string (on a collection of strings) and informs the others about its activity by communicating strings which are data and/or programs. Rewriting and communication take place alternately, the system functions (usually) in a synchronized manner. Parallel communicating grammar systems, a highly elaborated field, with Chomsky and Lindenmayer grammars at the nodes, studies networks with components communicating data strings by request. Test tube distributed systems based on splicing and that of cutting and recombination are particular cases of the model with components using variants of DNA recombination and they realize computationally complete and universal machines (in some cases with a limited number of components). Investigations have been started for implementing ideas of the Wave paradigm of active knowledge networks in this framework.

The results in the above areas address mainly theoretical problems but the research community is open to any suggestions for applications.

Please contact:
Erzsébet Csuhaj-Varjú - SZTAKI
Tel: + 36 1 1810 990

Gheorghe Pun - Mathematical Institute, Romanian Academy of Sciences
Tel: + 40 1 7256754

Arto Salomaa - University of Turku
Tel: +358 2 3335611

return to the contents page