Grammar system

The theory of grammar systems is a recent branch of formal language theory (cf. Formal languages and automata) aimed at modeling distributed computing (more generally, architectures occurring in multi-agent systems).

Roughly speaking, a grammar system consists of several grammars which work together, in a well specified way, and generate a unique language (contrast this with the classic case of formal language theory where one grammar/automaton generates/recognizes one language). The main focus is not on the generative power of such devices, but on the influence of the cooperation protocol on the power, the complexity, and the properties of grammar systems and of the generated languages.

There are two basic classes of grammar systems: sequential grammar systems and parallel grammar systems.

Of the first type are the cooperating distributed grammar systems (CD grammar systems), introduced in [a1], with motivations from the blackboard model in problem solving: several grammars work together on the same sentential form; at each moment one grammar only is active; the sequence of active grammars, the start/stop conditions for each grammar enabling, are specified by the cooperation protocol. The language generated by the system consists of all terminal strings generated in this way.

In parallel communicating grammar systems (PC grammar systems), introduced in [a8], several grammars work simultaneously, synchronously, each one on its sentential form; at each time unit each grammar uses a rewriting rule. The component grammars communicate on request or by command. In the first case, special query symbols are considered, associated in a one-to-one manner with the system components. When a query symbol $Q_i$ is introduced by a component $j$, then the current sentential form of the component $i$ is communicated to the component $j$, where it replaces the occurrence(s) of the symbol $Q_i$ in the sentential form of the component $j$. The language generated in this way by a specified component of the system (the master) is the language of the system. In the case of parallel communicating grammar systems with communication by command, the communication is started by the senders, as in the WAVE paradigm of communication in parallel computing; the communicated strings are accepted by the receivers only when these strings fit certain patterns associated with the components of the system (these types of parallel communicating grammar systems were introduced in [a4]).

A series of classes of CD and PC grammar systems can be considered, depending on the cooperation protocol, additional controlling mechanisms, the communication protocol, the type of the components, etc.

In general, the power of a grammar system is larger than the power of the grammars (of the type) used as components. For instance, PC grammar systems with regular components can generate non-context-free languages, PC grammar systems with context-free components used in a left-most manner characterize the recursively enumerable languages, etc.

Details can be found in [a3] and [a5]. As applications one can consider the so-called eco-grammar systems [a2] and the distributed "test tube systems" in DNA computing, see [a6], [a7].

References

[a1]	E. Csuhaj-Varju, J. Dassow, "On cooperating distributed grammar systems" J. Inform. Process. Cybern., EIK , 26 (1990) pp. 49–63
[a2]	E. Csuhaj-Varju, J. Kelemen, A. Kelemenova, Gh. Păun, "Eco-grammar systems: a framework for studying life-like interactions" Artificial Life , 3 : 1 (1997) pp. 1–28
[a3]	E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. Păun, "Grammar systems. A grammatical approach to distribution and cooperation" , Gordon&Breach (1994)
[a4]	E. Csuhaj-Varju, J. Kelemen, Gh. Păun, "Grammar systems with WAVE-like communication" Computers and AI , 15 : 4 (1996) pp. 419–436
[a5]	J. Dassow, Gh. Păun, G. Rozenberg, "Grammar systems" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , Springer (1996)
[a6]	Gh. Păun, "Five (plus two) universal DNA computing models based on the splicing operation" , Second Ann. Meeting on DNA Based Computers , Princeton Univ. Press (1996) pp. 67–86
[a7]	Gh. Păun, A. Salomaa, "DNA computing based on the splicing operation" Math. Japon. , 43 (1996) pp. 607–632
[a8]	Gh. Păun, L. Sântean (now Kari), "Parallel communicating grammar systems: the regular case" Ann. Univ. Buc., Mat.-Inform. Series , 38 (1989) pp. 55–63