Grammar systems form an important part of investigation of formal aspects of multi-agent systems. Cooperation, distribution and complexity are basic research topics of grammar systems. Recently the theory covers different types of systems motivated by technology as well as by biology. We present some representative variants of grammar systems, e.g. CD grammar systems, PC grammar colonies and eco-grammar systems. We illustrate different behavior of these systems like sequential, parallel behavior, and their more complex combinations, based on the motivation to introduce systems. We recapitulate some representative research topics, typical and interesting results, including provocative open problems and present rich references.
Grammar systems theory is a field of theoretical computer science that studies systems of finite collections of formal grammars generating a formal language. Each grammar works on a string that represents an environment. Grammar systems can thus be used as a formalization of decentralized or distributed systems of agents in artificial intelligence.
Study of grammar systems started in the 90-ties of the
last century with motivation of black board architecture.
The notion of the cooperating distributed grammar system
(CD grammar system, for short) was introduced in [
In a CD grammar system the agents are generative
grammars and the global data base is represented by a
string. The agents take turns in rewriting this string
according to a given cooperation strategy. The
successful problem solving is achieved by generating a terminal
word. CD grammar systems demonstrated that complex
behavior, i.e. complex languages can be generated by
simple grammars using a simple cooperation strategy. For an
overview about CD grammar systems see [
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.
PC grammar systems are motivated by another problem 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 „notes” to each other. Parallel communicating grammar systems (PCGS, for short) were introduced in Paun Santean in order to investigate concepts like parallelism, synchronization and data communication with formal language theoretic means. In this PC grammar system the components are generative grammars working on their own strings in parallel and communicating with each other by sending their strings by request. The language generated by the system consists of words of the master.
Unfortunately, that language families introduced in this fashion are rather intricate from a formal language point of view, even if one restricts oneself to right-linear grammar components. They have rather weak descriptive capacity.
In [
In version of PCGS introduced by Csima, so-called query symbols are cosidered formally as terminal symbols (and not as nonterminal symbols). Right-linear PCGS with terminal transmission have rather nice formal language properties, including simple hierarchical relations to wellknown regulated formal language classes and complexity classes.
Recently, there are many variations of GS studied. We
mention for example papers [
While the concept of CD and PC grammar systems is inspired by distributed AI, decentralized AI and Artificial Life (AL) give motivations for models like colony and ecogrammar system. Decentralized AI deals with the study of multi-agent systems of autonomous agents. In these systems the communication and cooperation is minimized, 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 behaviors characteric of natural living systems. Its models have similar properties to those of decentralized 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. 2
The colony, introduced in [
Basic differences among various possibilities of a
behavior of a colony, due to the number of components
used in one step. The sequential model, parallel models
and colonies working in teams are discussed. For further
derivation modes for the original colony as well as results
for different variants on terminal alphabet we refer to [
In next section we will deal with parallel colonies in order to discuss problem concerning equality of language classes for week and strong parallel derivation modes. 2.1
Basic ideas of the colony were formalized the following way: Definition 1. A colony C is a 4-tuple C = (V; T; F ; )x), where - V is an alphabet of the colony, - T
- F = f(Si; Fi) : Si 2 V; Fi (V Si) ; Fi is finite; 1 i n g.
A pair (Si; Fi) is called i-th component of C , Si is its start symbol and Fi is the language of i-th component. - )x
A relation )x on strings represents an elementary string transformation realized by components and called a derivation step.
As usual, )x stays for a reflexive and transitive closure of )x called derivation. It represents string transformations realized by finite sequences of derivation steps.
Language Lx(C ; w0) determined by a colony C = (V; T; F ; )x) and an initial string (axiom) w0 2 V consists of all terminal strings derived from the axiom, i.e. Lx(C ; w0) = fvj w0 )x v; v 2 T g:
By L (COLx) we denote the class of all languages generated by colonies with )x derivation.
In parallel colonies introduced in [
Two ways were proposed to solve activity of composp nents in this case. In strongly competitive case ) the derivation is blocked for the lack of start symbols in an actual string.
In weakly competitive case )wp the derivation continues and maximal number of components (nondeterministically chosen) is used to rewrite the string. Formally: sp Definition 2. Let C = (V; T; F ; )) be a colony and x; y 2 sp V . We write x ) y if and only if - x = x1Si1 x2Si2 : : : xkSik xk+1; - y = x1zi1 x2zi2 : : : xkzik xk+1 and zi j 2 Fi j ; 1 where iu 6= iv for u 6= v; 1 u; v k; (one component is allowed to rewrite at most one occurrence of its start symbol), - jxjS > 0 implies that for each component (S; F) in F ; there is i j; 1 i j k such that (S; F) = (Si j ; Fi j ): To introduce weak parallelism of colony C we denote by m(S) the number of components in C with start symbol S. Maximal possible number of components will be active in one weak parallel derivation step. j k; Definition 3. Let C = (V; T; F; )wp) be a colony and x; y 2 wp V : We write x ) y if and only if – x = x1Si1 x2Si2 : : : xkSik xk+1; – y = x1zi1 x2zi2 : : : xkzik xk+1 and zi j 2 Fi j ; 1 n; iu 6= iv for all u 6= v; 1 u; v k, i1; : : : ik (one component rewrites at most one occurrence of its start symbol) – jxjS = r 0 implies that for l = minfr; m(S)g different components (S; Fi j ); 1 j l from F chosen nondeterministically, we have (S; Fi j ) = (Si j ; Fi j ):
Colonies with strongly competitive parallel derivation
as well as colonies with weakly competitive parallel
derivation can produce some context sensitive languages.
Following [
L (COLwp);
L (ET 0L)[
L (M; ac);
where L (ET 0L)[
An important open problem from 1998 is the equality of the language classes L (COLsp) and L (COLwp).
To illustrate the topic we present parallel colonies for some non context-free languages in next examples.
(i) fww : w 2 f0; 1g+g 2 L (COLsp) . sp
Let C = (fA; B;C; D; X ; 0; 1g; f0; 1g; F ; )); where F = f(A; f0B; 1Cg); (A; f0C; 1Bg); (B; fA; X g); (C; fA; X g); (X ; feg); (X ; feg): There are two components with start symbol A and two components with start symbol X in F . Derivation in C starting with AA is blocked for a string with only one A or only one X : For example
sp sp
AA ) 0B1B ) 0A1B An example of derivation of terminal word is
sp sp sp sp sp
AA ) 0B0C ) 0A0A ) 01C01B ) 01X 01X ) 0101: Colony C with axiom AA generates the language
Lsp(C ; AA) = fww : w 2 f0; 1g+g: Another colony C¯sp produces the same language ¯ sp
Csp = (fA; B;C; D; X ; 0; 1g; f0; 1g; F ; ))), where F = f(A; f0B; 1Cg); (A; f0B; 1Cg); (B; fA; X g); (B; fA; X g), (C; fA; X g); (C; fA; X g); (X ; feg); (X ; feg)g.
Derivation gives for example
AA )sp 0B0B )sp 0A0A )sp 01C0s1pC )sp 01X 01X )sp 0101 Let the derivation start with AA ) 0B1C.
Colony has two components for B and just one B in the actual string so derivation is blocked. Derivation ends with terminal words only if two identical "nonterminals" are in all the sequential forms.
L(C¯sp; AA) = fww : w 2 f0; 1g+g: (ii) faibici j i 0 g 2 L (COLsp).
Consider colony sp Csp = (fS; A; B;C; D; E; F; a; b; cg; fa; b; cg; F ; )), where F = f(A; faD; X g); (B; fbE; X g); (C; fcF; X g); (D; fAg); (E; fBg); (F; fCg); (X ; feg); (X ; feg); (X ; feg)g. Only possibility to derive terminal word is to use components rewriting X . Three components with identical start symbol X guarantee that terminal string is derived using these components simultaneously. Derived strings have prescribed structure and terminal string is derived in synchronous rewriting two occurrences of X in the first example and three occurrences of X in the second example. Otherwise less occurrences of X in derived string stops derivation unsuccessfully. So L(Csp; S) = faibici j i 0 g:
(i) fww : w 2 f0; 1g+g 2 L (COLwp).
Let C = (fP; Q; R; X ;Y; B; 0; 1g; f0; 1g; F ; )wp); where F = f (P; f0QX ; 1RX ;Y g); (P; f0RY; 1QY; X g); (Q; fPg); (Q; fBg); (R; feg); (R; fBg); (X ; feg); (X ; fBg); (Y; feg); (Y; fBg)g.
Strings with at most one occurrence of Q; R; X ;Y can be rewritten to terminal words. Pairs of these symbols produce non active B and block the derivation.
Successful derivation:
wp wp wp wp wp PP ) w0pQX 0RY ) 0P0P ) 01RX 01QY ) 01P01P ) 01X 01Y ) 0101:
Blocked derivation:
wp wp PP ) 0QX 1QY or PP ) 0QX X : Language determined by a colony is
Lwp(C ; PP) = fww : w 2 f0; 1g+g: (ii) ffaibici j i 0g 2 L (COLwp).
Consider colony C = (fA; B;C; D; E; F; X ;Y; Z; H; a; b; cg; fa; b; cg; F ; )wp), where F = (A; faDX X ; aY Zg); (B; fbEYY; bX Zg); (C; fcFZZ; cXY g); (D; fAg); (E; fBg); (F; fCg); (X ; feg); (X ; feg); (X ; fHg); (Y; feg); (Y; feg); (Y; fHg); (Z; feg); (Z; feg); (Z; fHg).
Successful derivation: ABC )wp aDwXp X bEYY cFZZ )wp aAbBcC )wp aaY ZbbX ZcXY ) aabbcc Blocked derivation
wp
ABC ) aDX X bEYY cXY So Lwp(C ; S) = faibici j i 0g: (iii) faib jck j i; j; k 0; i 6= j; j 6= k; i 6= kg 2 L (COLwp): Consider colony Cwp = (fS; A; B;C; D; E; F; a; b; cg; fa; b; cg; F ; )wp), where F = f(A; faD; X g); (B; fbE; X g); (C; fcF; X g); (D; fAg); (E; fBg); (F; fCg); (X ; feg); (X ; fY g); (X ; fY g)g A successful derivation in the colony ends by rewriting all occurrences of X by e. There are at most three occurrences of X in sentential forms produced by the colony but only words containing at most one X can be rewritten to terminal words.
Successful derivation: ABC ) X bEcF ) bBcC ) bX ccF ) bccC ) bccX )wp wp wp wp wp wp bcc Blocked derivation
wp wp wp wp ABC ) aDbEcF ) aAbBcC ) aX bX cX ) aY bY c L(Cwp; S) = faib jck j i; j; k 0; i 6= j and j 6= k and i 6= kg: 2.2
The PM-colonies, as collection of agents located on
string environment with ability to change their
neighboring agents or environment, were introduced and studied in
[
- the environment is described by a string of symbols; names of agents are symbols appearing in this string (agents are parts of the environment with specific places); agents can modify symbols of the environment description (hence also the symbols identifying other agents, which means that the agents can act on each other);
- agents are only able to perform point mutations (similar to those ones appearing in the genetic area): erase one symbol, insert one symbol, substitute one symbol for another one;
- these actions take place only in the strict vicinity of the symbol representing the agent; in order to allow mobility, one also considers move actions by which the agent symbols can be interchanged with a neighboring symbol (irrespective whether or not this one is a name of another agent);
- all actions described above (point mutations and moves) depend on the smallest nontrivial neighborhood of the agent: the environment symbols adjacent to the left and to the right (the boundary markers, at the ends of the environment); actions take place simultaneously for all agents present in the environment (this pair of neighboring symbols form the context of the agent); conflicts are solved by a priority relation among agents: when two agents have a common context or, even more, one agent is placed in the context of another one, then the agent with higher priority will act; in the case of equal priority a deadlock appears; - agents remain unchanged in all the elementary actions described above (point mutations and moves), except the following possibilities: an agent can remove its own name (“death”), can introduce and remove the name of another agent (“birth” and “death”; thus, an agent cannot change its own name or the name of another agent).
Two variants how to define and solve conflicts in models were discussed together with their influences to the generative power of the PM colonies.
1) PM-colony, original model
Let agents Ai and A j appear in the string. We say that Ai
and A j are in conflict if they have common context or one
agent is a part of context of the other agent. Let Ai; A j and
Ak be agents. If Ai and A j are in conflict and A j and Ak are
in conflict at the same time, then we say that agents Ai and
Ak are in conflict too. We say that appearance of agent Ai
in context aAib in the environment w is active, if and only
if there exists some rule with left side of form (a, Ai, b) and
it holds that Ai is not in conflict with any other agent, or it
is in conflict with one or more agents but it has the
greatest priority. Generative power of PM colonies introduced
above was studied in [
PM-colonies are able to generate some context sensitive languages, (L (COLPM) - L (CF) 6= 0/ ) but on the other side there are finite languages that cannot be generated by them (L (FIN) – L (COLPM) 6= 0/ ). This way of introduction conflicts and activity of agents seems to be very restrictive. It can occur that agents in the common environment do not affect each other, but they are in the conflict caused by another agent(s). And if there is no agent with the greatest priority in chain of such agents, all agents in the string become inactive.
2) PM-colony with significant context
Another possibility to introduce the conflict of agents in
PM colony was investigated in [
The model of an eco-grammar system was introduced in
[
The model, an eco-grammar system, consists of the interconnected parts of environment and agents or components. The environment is described by a string, developing in totally parallel manner according to the derivation mode of an 0L system (i.e.using interactionless rules). Each agent is described by a string developing according to the derivation mode of an 0L system as well. Moreover, using specific action rules the agent can locally change the environment, and the actual state of the environment can influence the development of agents and the states of agents can influence the development of the environment by choice of active action rules.
Basic information on eco-grammar systems can be
found in overview papers [
One of the videly investigated topic of EG systems
is their team behaviour. The concept of a team,
introduced into grammar systems theory in [
The number of the agents in the system and the number of the agents working in a derivation step form hierarchy of language classes in non-extended case. In an extended simple eco-grammar system these hierarchies collapse.
In next part we take attention to special cases of ecogrammar systems with identical components called monocultures.
Eco-grammar systems with identical agents are called the
monocultures. Several results concerning the generative
power and the hierarchy and/or incomparability of these
systems according to the number of components were
presented in [
Typical results concerning monocultures are following: 1. Monocultures over unary alphabet are as powerful as eco-grammar systems over unary alphabet.
This is a consequence of the fact that every unary language of an eco-grammar system can be generated by an eco-grammar systems with one agent and therefore by a monoculture.
2. Finite languages as well as semiunary languages are languages of monocultures, where a semiunary language is a language over at least binary alphabet and each word of the language is the string of identical letters.
3. Eco-grammar systems with passive environment can be simulated by monocultures.
4. An equivalent weak monoculture can be constructd to each eco-grammar system, where a weak monoculture is an EG systems with identical agents, each of which can start in different states.
This gives rise the question what happends if we are looking for the monocultures where components are started with the same axiom.
(In)equality of the generative power of eco-grammar systems and monocultures is still an open problem. Note, that we put no restriction to the number of components of monoculture which simulate the behaviour of EG system. Number of components in these systems can be different.
Perhaps the most interesting partial result related to it is that monocultures do not restrict substantially the generative power of the eco-grammar systems in the following sense:
5. One can add a single word to each language of an eco-grammar system to obtain a language of a monoculture.
This word is the axiom of the corresponding
monoculture. In [
This work was supported by The Ministry of Education, Youth and Sports from the National Programme of Sustainability (NPU II) project IT4Innovations excellence in science - LQ1602.