=Paper=
{{Paper
|id=Vol-2718/invited3
|storemode=property
|title=Variants of Grammar Systems: Motivations and Problems
|pdfUrl=https://ceur-ws.org/Vol-2718/invited3.pdf
|volume=Vol-2718
|authors=Alica Kelemenová
|dblpUrl=https://dblp.org/rec/conf/itat/Kelemenova20
}}
==Variants of Grammar Systems: Motivations and Problems==
https://ceur-ws.org/Vol-2718/invited3.pdf
Variants of grammar systems: motivations and problems
Alica Kelemenová
Institute of Computer Sciemce, Silesian univerzity in Opava, Opava, Czech Republic,
kelemenova@fpf.slu.cz
Abstract: Grammar systems form an important part of in- While CD grammar systems use sequential rewriting (in
vestigation of formal aspects of multi-agent systems. Co- each derivation step only one grammar is active), parallel
operation, distribution and complexity are basic research communicating grammar systems (PC grammar systems,
topics of grammar systems. Recently the theory covers for short) introduce parallelism into grammar systems the-
different types of systems motivated by technology as well ory.
as by biology. We present some representative variants of PC grammar systems are motivated by another problem
grammar systems, e.g. CD grammar systems, PC gram- the classroom model. In this model each agent can operate
mar colonies and eco-grammar systems. We illustrate dif- only on its own „notebook” and only one component, the
ferent behavior of these systems like sequential, parallel master can use the blackboard. The agents work in par-
behavior, and their more complex combinations, based on allel and they can communicate by sending their „notes”
the motivation to introduce systems. We recapitulate some to each other. Parallel communicating grammar systems
representative research topics, typical and interesting re- (PCGS, for short) were introduced in Paun Santean in or-
sults, including provocative open problems and present der to investigate concepts like parallelism, synchroniza-
rich references. tion and data communication with formal language theo-
retic means. In this PC grammar system the components
are generative grammars working on their own strings in
1 GRAMMAR SYSTEMS parallel and communicating with each other by sending
their strings by request. The language generated by the
Grammar systems theory is a field of theoretical computer
system consists of words of the master.
science that studies systems of finite collections of formal
grammars generating a formal language. Each grammar Unfortunately, that language families introduced in this
works on a string that represents an environment. Gram- fashion are rather intricate from a formal language point of
mar systems can thus be used as a formalization of decen- view, even if one restricts oneself to right-linear grammar
tralized or distributed systems of agents in artificial intel- components. They have rather weak descriptive capacity.
ligence. In [33] a variant of PC grammar systems, called PC
Study of grammar systems started in the 90-ties of the grammar systems with terminal transmission, were intro-
last century with motivation of black board architecture. duced. Right-linear centralized version of these systems
The notion of the cooperating distributed grammar system has nice formal language theoretic properties: they are
(CD grammar system, for short) was introduced in [13] closed under union and gsm mappings (in particular, under
and in [16]. First models of grammar systems theory are intersection with regular sets and under homomorphism)
mainly motivated by distributed AI. The concept of CD slight variant is also closed under concatenation and star.
grammar systems was proposed as a syntactic model of Their power lies between that of n-parallel grammars in-
the blackboard architecture of problem solving, where sev- troduced by Wood and that of matrix languages of index n,
eral independent agents work together on the solution of a and their relation to equal matrix grammars of degree n is
problem by cooperating with each other only by modify- discussed. Membership problem and questions concern-
ing the common blackboard representing the current state ing grammatical inference of these systems are studied.
of problem solving. In version of PCGS introduced by Csima, so-called
In a CD grammar system the agents are generative query symbols are cosidered formally as terminal symbols
grammars and the global data base is represented by a (and not as nonterminal symbols). Right-linear PCGS with
string. The agents take turns in rewriting this string ac- terminal transmission have rather nice formal language
cording to a given cooperation strategy. The success- properties, including simple hierarchical relations to well-
ful problem solving is achieved by generating a terminal known regulated formal language classes and complexity
word. CD grammar systems demonstrated that complex classes.
behavior, i.e. complex languages can be generated by sim- Recently, there are many variations of GS studied. We
ple grammars using a simple cooperation strategy. For an mention for example papers [1], [2] and [4]. For further
overview about CD grammar systems see [15] and [30]. models and inspirations see references at the end of this
paper.
Copyright c 2020 for this paper by its authors. Use permitted un-
der Creative Commons License Attribution 4.0 International (CC BY While the concept of CD and PC grammar systems is
4.0). inspired by distributed AI, decentralized AI and Artificial
Life (AL) give motivations for models like colony and eco- - V is an alphabet of the colony,
grammar system. Decentralized AI deals with the study of
- T ⊆ V is a terminal alphabet of the colony,
multi-agent systems of autonomous agents. In these sys-
tems the communication and cooperation is minimized, - F = {(Si , Fi ) : Si ∈ V, Fi ⊆ (V − Si )∗ , Fi is finite, 1 ≤
there is no predefined strategy (unlike in distributed AI), i ≤ n }.
the properties of the system emerge only from the inten- A pair (Si , Fi ) is called i-th component of C , Si is its
sive interaction of the agents and the environment. AL start symbol and Fi is the language of i-th component.
studies man-made systems that exhibit behaviors charac- x
teric of natural living systems. Its models have similar - ⇒ ⊆ V ∗ ×V ∗ is a derivation step relation.
x
properties to those of decentralized AI: they consist of a A relation ⇒ on strings represents an elementary
population of simple agents reacting on a common en- string transformation realized by components and called
vironment without any master component, which would a derivation step.
direct their behaviour or coordinate their work. Life-like x ∗
As usual, ⇒ stays for a reflexive and transitive closure
features are the result only of the interaction of the com- x
of ⇒ called derivation. It represents string transformations
ponents and the environment. realized by finite sequences of derivation steps.
Language Lx (C , w0 ) determined by a colony C =
x
2 COLONIES (V, T, F , ⇒) and an initial string (axiom) w0 ∈ V ∗ con-
sists of all terminal strings derived from the axiom, i.e.
x ∗
The colony, introduced in [36] is motivated mainly by the Lx (C , w0 ) = {v| w0 ⇒ v, v ∈ T ∗ }.
behavior of reactive agents in robotics. This model re- By L (COLx ) we denote the class of all languages gen-
x
tains the idea of CD and PC grammar systems of having erated by colonies with ⇒ derivation.
grammars as components working together but in a colony In parallel colonies introduced in [29] several agents can
these grammars are simple regular grammars generating be active simultaneously according the principle: Com-
finite languages and there is no cooperation between them. ponents of a colony which can work on the actual string
The model has an environment component represented by must work simultaneously. ’Component can work’ means
a string. The state of the system can be changed only by here that the start symbol of the component is present in
the actions of the agents; the environment is passive, it the environment. Each active component has to rewrite
does not change its state autonomously. Due to the lack of one occurrence of its start symbol. No competition con-
any predefined strategy, each grammar participates in the flict occurs in derivation in the case when all components
rewriting whenever it can, conflicts are resolved nondeter- have different start symbols. In an opposite case competi-
ministically. The language generated by the colony is the tion conflict occurs when some components have identical
set of all the possible states of the environment. Several start symbols and there are not enough occurrences of that
derivation modes and acceptance styles were introduced symbol in the environment.
and studied. See [19] and [10] for formal definitions and Two ways were proposed to solve activity of compo-
sp
results. Colonies proved to show emergent behavior in- nents in this case. In strongly competitive case ⇒ the
deed: the components are very simple regular grammars, derivation is blocked for the lack of start symbols in an
but powerful, large language classes can be generated in actual string.
wp
this way. In weakly competitive case ⇒ the derivation continues
Basic differences among various possibilities of a be- and maximal number of components (nondeterministically
havior of a colony, due to the number of components chosen) is used to rewrite the string. Formally:
used in one step. The sequential model, parallel models sp
and colonies working in teams are discussed. For further Definition 2. Let C = (V, T, F , ⇒) be a colony and x, y ∈
sp
derivation modes for the original colony as well as results V ∗ . We write x ⇒ y if and only if
for different variants on terminal alphabet we refer to [19], - x = x1 Si1 x2 Si2 . . . xk Sik xk+1 ,
[41], [38].
In next section we will deal with parallel colonies in - y = x1 zi1 x2 zi2 . . . xk zik xk+1 and zi j ∈ Fi j , 1 ≤ j ≤ k,
order to discuss problem concerning equality of language where iu 6= iv for u 6= v, 1 ≤ u, v ≤ k,
classes for week and strong parallel derivation modes. (one component is allowed to rewrite at most one oc-
currence of its start symbol),
2.1 Parallel Colonies - |x|S > 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 ).
Basic ideas of the colony were formalized the following
way: To introduce weak parallelism of colony C we denote
by m(S) the number of components in C with start symbol
x
Definition 1. A colony C is a 4-tuple C = (V, T, F , ⇒), S. Maximal possible number of components will be active
where in one weak parallel derivation step.
wp
Definition 3. Let C = (V, T, F, ⇒) be a colony and x, y ∈ terminal words only if two identical "nonterminals" are in
wp
V ∗ . We write x ⇒ y if and only if all the sequential forms.
L(C¯sp , AA) = {ww : w ∈ {0, 1}+ }.
– x = x1 Si1 x2 Si2 . . . xk Sik xk+1 ,
(ii) {ai bi ci | i ≥ 0 } ∈ L (COLsp ).
– y = x1 zi1 x2 zi2 . . . xk zik xk+1 and zi j ∈ Fi j , 1 ≤ i1 , . . . ik ≤ Consider colony
n, iu 6= iv for all u 6= v, 1 ≤ u, v ≤ k, sp
Csp = ({S, A, B,C, D, E, F, a, b, c}, {a, b, c}, F , ⇒), where
(one component rewrites at most one occurrence of F = {(A, {aD, X}), (B, {bE, X}), (C, {cF, X}), (D, {A}),
its start symbol) (E, {B}), (F, {C}), (X, {ε}), (X, {ε}), (X, {ε})}.
Only possibility to derive terminal word is to use compo-
– |x|S = r ≥ 0 implies that for l = min{r, m(S)} different nents rewriting X. Three components with identical start
components (S, Fi j ), 1 ≤ j ≤ l from F chosen nonde- symbol X guarantee that terminal string is derived using
terministically, we have (S, Fi j ) = (Si j , Fi j ). these components simultaneously. Derived strings have
prescribed structure and terminal string is derived in syn-
Colonies with strongly competitive parallel derivation
chronous rewriting two occurrences of X in the first ex-
as well as colonies with weakly competitive parallel
ample and three occurrences of X in the second example.
derivation can produce some context sensitive languages.
Otherwise less occurrences of X in derived string stops
Following [15], [29] we have
derivation unsuccessfully. So L(Csp , S) = {ai bi ci | i ≥ 0 }.
Proposition L (COLsp ) ⊆ L (COLwp ), Example 2. wp mode
(i) {ww : w ∈ {0, 1}+ } ∈ L (COLwp ).
L (COLwp ) ⊆ L (ET 0L)[1] ⊂ L (M, ac) and wp
Let C = ({P, Q, R, X,Y, B, 0, 1}, {0, 1}, F , ⇒), where
L (COLsp ) ⊆ L (M, ac), F = { (P, {0QX, 1RX,Y }), (P, {0RY, 1QY, X}),
(Q, {P}), (Q, {B}), (R, {ε}), (R, {B}),
where L (ET 0L)[1] are one limited ET0L languages and (X, {ε}), (X, {B}), (Y, {ε}), (Y, {B})}.
L (M, ac) is the class of matrix languages with appearance Strings with at most one occurrence of Q, R, X,Y can be
checking. rewritten to terminal words. Pairs of these symbols pro-
An important open problem from 1998 is the equality duce non active B and block the derivation.
of the language classes L (COLsp ) and L (COLwp ). Successful derivation:
wp wp wp wp wp
To illustrate the topic we present parallel colonies for PP ⇒ 0QX0RY ⇒ 0P0P ⇒ 01RX01QY ⇒ 01P01P ⇒
wp
some non context-free languages in next examples. 01X01Y ⇒ 0101.
Blocked derivation:
Example 1. sp mode wp wp
PP ⇒ 0QX1QY or PP ⇒ 0QXX.
(i) {ww : w ∈ {0, 1}+ } ∈ L (COLsp ) .
sp Language determined by a colony is
Let C = ({A, B,C, D, X, 0, 1}, {0, 1}, F , ⇒), where Lwp (C , PP) = {ww : w ∈ {0, 1}+ }.
F = {(A, {0B, 1C}), (A, {0C, 1B}), (B, {A, X}), (C, {A, X}),
(X, {ε}), (X, {ε}). (ii) {{ai bi ci | i ≥ 0} ∈ L (COLwp ).
There are two components with start symbol A and two Consider colony
components with start symbol X in F . Derivation in C wp
C = ({A, B,C, D, E, F, X,Y, Z, H, a, b, c}, {a, b, c}, F , ⇒),
starting with AA is blocked for a string with only one A or
where
only one X. For example
sp sp F = (A, {aDXX, aY Z}), (B, {bEYY, bXZ}),
AA ⇒ 0B1B ⇒ 0A1B (C, {cFZZ, cXY }), (D, {A}), (E, {B}), (F, {C}),
An example of derivation of terminal word is (X, {ε}), (X, {ε}), (X, {H}), (Y, {ε}), (Y, {ε}),
sp sp sp sp sp
AA ⇒ 0B0C ⇒ 0A0A ⇒ 01C01B ⇒ 01X01X ⇒ 0101. (Y, {H}), (Z, {ε}), (Z, {ε}), (Z, {H}).
Colony C with axiom AA generates the language Successful derivation:
wp wp wp
Lsp (C , AA) = {ww : w ∈ {0, 1}+ }. ABC ⇒ aDXXbEYY cFZZ ⇒ aAbBcC ⇒
wp
aaY ZbbXZcXY ⇒ aabbcc
Another colony C¯sp produces the same language Blocked derivation
sp wp
C̄sp = ({A, B,C, D, X, 0, 1}, {0, 1}, F , ⇒)), where ABC ⇒ aDXXbEYY cXY
F = {(A, {0B, 1C}), (A, {0B, 1C}), (B, {A, X}), (B, {A, X}), So Lwp (C , S) = {ai bi ci | i ≥ 0}.
(C, {A, X}), (C, {A, X}), (X, {ε}), (X, {ε})}.
Derivation gives for example (iii) {ai b j ck | i, j, k ≥ 0, i 6= j, j 6= k, i 6= k} ∈ L (COLwp ).
sp sp sp sp sp
AA ⇒ 0B0B ⇒ 0A0A ⇒ 01C01C ⇒ 01X01X ⇒ 0101 Consider colony
sp wp
Let the derivation start with AA ⇒ 0B1C. Cwp = ({S, A, B,C, D, E, F, a, b, c}, {a, b, c}, F , ⇒), where
Colony has two components for B and just one B in the F = {(A, {aD, X}), (B, {bE, X}), (C, {cF, X}),
actual string so derivation is blocked. Derivation ends with (D, {A}), (E, {B}), (F, {C}), (X, {ε}), (X, {Y }), (X, {Y })}
A successful derivation in the colony ends by rewriting 1) PM-colony, original model
all occurrences of X by ε. There are at most three occur- Let agents Ai and A j appear in the string. We say that Ai
rences of X in sentential forms produced by the colony but and A j are in conflict if they have common context or one
only words containing at most one X can be rewritten to agent is a part of context of the other agent. Let Ai , A j and
terminal words. Ak be agents. If Ai and A j are in conflict and A j and Ak are
Successful derivation: in conflict at the same time, then we say that agents Ai and
wp wp wp wp wp wp
ABC ⇒ XbEcF ⇒ bBcC ⇒ bXccF ⇒ bccC ⇒ bccX ⇒ Ak are in conflict too. We say that appearance of agent Ai
bcc in context aAi b in the environment w is active, if and only
Blocked derivation if there exists some rule with left side of form (a, Ai, b) and
wp wp wp wp
ABC ⇒ aDbEcF ⇒ aAbBcC ⇒ aXbXcX ⇒ aY bY c 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 great-
L(Cwp , S) = {ai b j ck | i, j, k ≥ 0, i 6= j and j 6= k and i 6= k}. est priority. Generative power of PM colonies introduced
above was studied in [20] with following results:
PM-colonies are able to generate some context sensitive
2.2 PM-colonies languages, (L (COLPM ) - L (CF) 6= 0) / but on the other
side there are finite languages that cannot be generated by
The PM-colonies, as collection of agents located on them (L (FIN) – L (COLPM ) 6= 0). / This way of intro-
string environment with ability to change their neighbor- duction conflicts and activity of agents seems to be very
ing agents or environment, were introduced and studied in restrictive. It can occur that agents in the common envi-
[47], [48]. Introduction of a PM-colony is based on the ronment do not affect each other, but they are in the con-
following assumptions: flict caused by another agent(s). And if there is no agent
- the environment is described by a string of sym- with the greatest priority in chain of such agents, all agents
bols; names of agents are symbols appearing in this string in the string become inactive.
(agents are parts of the environment with specific places); 2) PM-colony with significant context
agents can modify symbols of the environment description Another possibility to introduce the conflict of agents in
(hence also the symbols identifying other agents, which PM colony was investigated in [5]. One can consider "sig-
means that the agents can act on each other); nificant context" of the agent. Significant context is a sub-
- agents are only able to perform point mutations (simi- string of length five, containing two letters before and two
lar to those ones appearing in the genetic area): erase one letters after the agent. It will determine conflict between
symbol, insert one symbol, substitute one symbol for an- agents and activity of agents as follows: The agent is not in
other one; conflics in the case if there is no other agent in its signifi-
- these actions take place only in the strict vicinity of cant context, or if it has the greatest priority with respect to
the symbol representing the agent; in order to allow mo- the all other agents in its significant context. AGent is ac-
bility, one also considers move actions by which the agent tive, if it is not in conflict and the is a rule to rewrite it with
symbols can be interchanged with a neighboring symbol respect to his actual left and righ neighbour.In all other
(irrespective whether or not this one is a name of another cases the agent is no active. Such attempt to the activity of
agent); agents differs from that one introduced above. For exam-
- all actions described above (point mutations and ple, consider the string AaBaA where A has greater priority
moves) depend on the smallest nontrivial neighborhood of then B. Both occurrences of agent A are active by consid-
the agent: the environment symbols adjacent to the left and ering significant context, while according to the original
to the right (the boundary markers, at the ends of the envi- definition from previous section all agents are inactive. To
ronment); actions take place simultaneously for all agents distinguish new derivation approach we will use PMs in-
present in the environment (this pair of neighboring sym- stead of PM. For the generative power od PMs colonies we
bols form the context of the agent); conflicts are solved by RE = L (COLPMs ) and L (COLPMs ) – L (COLPM ) 6= 0. /
a priority relation among agents: when two agents have a
common context or, even more, one agent is placed in the 3 ECO-GRAMMAR SYSTEMS
context of another one, then the agent with higher priority
will act; in the case of equal priority a deadlock appears; The model of an eco-grammar system was introduced in
- agents remain unchanged in all the elementary actions [17] and presented in detail in [18]. It realizes an attempt
described above (point mutations and moves), except the to create formal grammar specification for investigation of
following possibilities: an agent can remove its own name the interplay between the environment and agents in sys-
(“death”), can introduce and remove the name of another tems like ecosystems using framework of grammar sys-
agent (“birth” and “death”; thus, an agent cannot change tems [15]. Eco-grammar systems can be used to model
its own name or the name of another agent). some aspects of the behavior of cooperating communities
Two variants how to define and solve conflicts in models of agents operating in a common dynamic environment.
were discussed together with their influences to the gener- The model, an eco-grammar system, consists of the in-
ative power of the PM colonies. terconnected parts of environment and agents or compo-
nents. The environment is described by a string, devel- 2. Finite languages as well as semiunary languages are
oping in totally parallel manner according to the deriva- languages of monocultures, where a semiunary language
tion mode of an 0L system (i.e.using interactionless rules). is a language over at least binary alphabet and each word
Each agent is described by a string developing according of the language is the string of identical letters.
to the derivation mode of an 0L system as well. Moreover, 3. Eco-grammar systems with passive environment can
using specific action rules the agent can locally change be simulated by monocultures.
the environment, and the actual state of the environment 4. An equivalent weak monoculture can be constructd
can influence the development of agents and the states of to each eco-grammar system, where a weak monoculture
agents can influence the development of the environment is an EG systems with identical agents, each of which can
by choice of active action rules. start in different states.
Basic information on eco-grammar systems can be This gives rise the question what happends if we
found in overview papers [39], [38], [7]. Variants of are looking for the monocultures where components are
EG systems motivated by PM colonies were studied in started with the same axiom.
[42, 45, 44]. Eco-colonies, the variant of EG systems mo- (In)equality of the generative power of eco-grammar
tivated by colonies were studied by Š. Vavrečková. Power systems and monocultures is still an open problem. Note,
of eco-colonies were compared with that of colonies and that we put no restriction to the number of components of
EG systems in [60],[62] and [63]. monoculture which simulate the behaviour of EG system.
One of the videly investigated topic of EG systems Number of components in these systems can be different.
is their team behaviour. The concept of a team, intro- Perhaps the most interesting partial result related to it is
duced into grammar systems theory in [35], appears in that monocultures do not restrict substantially the gener-
eco-grammar systems theory in two different forms: pre- ative power of the eco-grammar systems in the following
scribed teams discussed in [3] and team derivation modes sense:
[20]. In the case of prescribed teams the system contains 5. One can add a single word to each language of an
the specification of those groups of agents which can work eco-grammar system to obtain a language of a monocul-
together in a derivation step. Derivation mode k prescribes ture.
that in each derivation step exactly k agents work. Thus, This word is the axiom of the corresponding monocul-
in this derivation mode any k agents can form a team and ture. In [40] we are looking for suitable candidates for
can work together. If we consider simple eco-grammar axiom inside the language generated by an eco-grammar
systems i.e. systems, where the agents, independently of system. If we could find such a word for each at least bi-
the actual state, can execute all possible actions on the en- nary EG languages then equality holds.
vironment we obtain different results for systems with 0L
behavior and E0L behavior of the environment. Acknowledgement
The number of the agents in the system and the number
of the agents working in a derivation step form hierarchy This work was supported by The Ministry of Education,
of language classes in non-extended case. In an extended Youth and Sports from the National Programme of Sus-
simple eco-grammar system these hierarchies collapse. tainability (NPU II) project IT4Innovations excellence in
In next part we take attention to special cases of eco- science - LQ1602.
grammar systems with identical components called mono-
cultures.
References
[1] Arthi, K., Krithivasan, K., Csuhaj-Varjú, E.: On Rule-
Monocultures
Number Complexity of Components of Probabilistic Coop-
erating Distributed Grammar Systems. Journal of Automata,
Eco-grammar systems with identical agents are called the Languages and Combinatorics 7(4): 433-446 (2002)
monocultures. Several results concerning the generative
[2] Autebert, J.-M.: Some results about centralized PC grammar
power and the hierarchy and/or incomparability of these system. Theo. Comput. Sci. 215 (1999) 383—398
systems according to the number of components were pre-
[3] ter Beek, M.H., Eco-grammar systems and colonies. In:
sented in [43], [40], [7] and [9]. Relation between EG Grammatical Models of Multi-Agent Systems, 1999
languages and languages of monocultures seems to be sur-
[4] ter Beek, M.H., Csuhaj-Varjú, E., Holzer, M., Vaszil, G.: Co-
prising. operating Distributed Grammar Systems: Components with
Typical results concerning monocultures are following: Nonincreasing Competence. Computation, Cooperation, and
1. Monocultures over unary alphabet are as powerful as Life. LNCS 6610 Springer (2011)
eco-grammar systems over unary alphabet. [5] Blažek, M.: Řešení konfliktů v PM-koloniích. Diplomová
This is a consequence of the fact that every unary lan- práce. Ústav informatiky, Slezská univerzita, Opava 2008
guage of an eco-grammar system can be generated by an [6] Bordihn, H., Dassow, J., Vaszil, G.: Grammar systems as
eco-grammar systems with one agent and therefore by a language analyzers and recursively enumerable languages.
monoculture. In: Proc. FCT’99, LNCS 1684 (1999) 136–147.
[7] Csima, J.: On Extended Simple Eco-grammar Systems. Acta communicating grammar systems: Synchronization, com-
Cybern. (1998) 359–373 munication, and normal forms. Theoret. Comput. Sci. 255
[8] Csima, J.: On Hybrid Eco-rewriting Systems. Grammars (2001) 511–538
1(1999) 239-253 [27] Csuhaj-Varju, E., Vaszil, G.: Parallel communicating gram-
[9] Csima, J.: Two remarks on variants of simple eco-grammar mar systems with incomplete information communication.
systems. Acta Cybern. 14 (2000) 569-582 Develop. Language Theory (2001), 381–392
[10] Csuhaj-Varjú, E.: Colonies: a multi-agent approach to lan- [28] Dassow, J.: On cooperating distributed grammar systems
guage generation. Extended finite state models of language. with competence based start and stop conditions. Fund. In-
Cambridge University Press (1999) 208-225 form. 76 (2007) 293–304
[11] Csuhaj-Varjú, E.: On size complexity of context-free re- [29] Dassow, J., Kelemen, J., Păun, G.: On Parallelism in
turning parallel communicating grammar systems. Where Colonies. Cybernetics and Systems 24, 37–49 (1993)
Mathematics, Computer Science, Linguistics and Biology [30] Dassow, J., Păun, G., Rozenberg, G.: Grammar systems.
Meet (2001 37-49 In: Handbook of Formal Languages, Springer, Berlin (1997)
[12] Csuhaj-Varjú, E.: CD Grammar Systems: Competence and 155–214
Confidence. Computation, Cooperation, and Life 2011: 57- [31] Dumitrescu, S., Păun, G.: On the power of parallel com-
69 municating grammar sys-tems with right-linear components.
[13] Csuhaj-Varju, E., Dassow, J.: On cooperating-distributed RAIRO Informatique th´eorique et Applications/Theoretical
grammar systems, J. Inform. Process. Cybernet. 26 (1990) Informatics and Applications 31 (1997) 331–354
49-63 [32] Fernau, F: PC grammar systems with terminal transmis-
[14] Csuhaj-Varjú, E., Dassow, J.: On the Size of Components sion. In: Proc.International Workshopon Grammar Systems,
of Probabilistic Cooperating Distributed Grammar systems. Silesian University at Opava, (2000) 229–252
Theory Is Forever 2004: 49-59 [33] Fernau, H.: Parallel communicating grammar systems with
[15] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Păun, G.: Gram- terminal transmission. Acta Inform. 37 (2001) 511–540
mar Systems. A Grammatical Approach to Distribution and [34] Fernau, H., Holzer, M.: Graph-controlled cooperating dis-
Cooperation. Gordon & Beach, London, 1994. tributed grammar systems with singleton components. In:
[16] E. Csuhaj-Varju and J. Kelemen, Cooperating grammar Proc. Third Internat. Workshop on Descriptional Complex-
systems: a syntactical framework for blackboard model of ity of Automata, Grammars, and Related Structures, Vienna
problem solving. In: Proc. AIICSR 1989 (1989) 121 –127. (2001) 79-90
[17] E. Csuhaj-Varjú, J. Kelemen, A. Kelemenovâ., G. Pâun: [35] Kari, L., Mateescu, A., Paun, G., Salomaa, A: Teams in
Eco(grammar) systems. A preview. In: Proc. 12th Euro- cooperating grammar systems. J. Exp. Theor. Artif. Intell.
pean Meeting on Cybernetics and System Research, Vienna, 7(4): 347-359 (1995)
1994, R. Trappl, ed., World Scientific, Singapore, 1994, [36] Kelemen, J.,Kelemenová, A.: A Grammar-theoretic Treat-
941–948 ment of Multiagent Systems. Cybernetics and Systems 23
[18] Csuhaj-Varjú, E., Kelemen, J., Kelemenová, A., Păun, G.: (1992) 621–633
Eco-grammar Systems. Grammatical Framework for Study- [37] Kelemen, j., Kelemenová, A., Martín-Vide, C., Mitrana,
ing Lifelike Interactions. Artificial Life 3 (1997) 1–28 Colonies with limited activation of components, Theoretical
[19] Csuhaj-Varjú, E., Kelemenová, A.: Languages of Colonies. computer science 244 (2000) 289–298.
Theoretical Computer Science 134 (1994) 119-130 [38] Kelemenová, A., Kelemen, J.: From colonies to
[20] Csuhaj-Varjú, E., Kelemenová, A.: Team behaviour in eco- eco(grammar) systems. An overview. In: Proc. Important
grammar systems. Theoretical Computer Science 209 (1998) Results and Trends in Theoretical Computer Science, Graz,
213–224 1994., Lecture Notes in Computer Science 812, Springer
[21] Csuhaj-Varjú, E., Vaszil, Gy.: On the Number of Compo- Verlag, Berlin, 1994, 211–231
nents and Clusters of Non-returning Parallel Communicating [39] Kelemenová, A.: Eco-grammar systems. In: Formal lan-
Grammar Systems. DCFS 2011: 121-134 guages and applications, Studies in Fuzziness and Soft Com-
[22] Csuhaj-Varjú, E., Vaszil, Gy.: On the Descriptional Com- puting 148. Springer, Berlin, 2004, 311–322
plexity of Context-Free Non-returning PC Grammar Sys- [40] Kelemenová, A., Bartík, T.: Monocultures in eco-grammar
tems. Journal of Automata, Languages and Combinatorics systems. AFL 2008: 208-219
15(1/2): 91-105 (2010) [41] Kelemenová, A.,Csuhaj-Varjú, E.: Languages of Colonies.
[23] Csuhaj-Varjú, E., Vaszil, Gy.: On the Size Complexity of Theoretical Computer Science 134 (1994) 119–130
Non-Returning Context-Free PC Grammar Systems. DCFS [42] Kelemenová, A., Langer, M.: Positioned Agents in Eco-
2009: 91-100 Grammar System. IJFCS 22, (2011) 237-–246
[24] Csuhaj-Varjú, E., Vaszil, Gy.: Parallel communicating [43] Kelemenová,A., Tupý, M.: Monocultures and homoge-
grammar systems with bounded resources. Theor. Comput. neous environment in eco-grammar systems. Fundamenta
Sci.276(1-2): 205-219 (2002) Informaticae 76 (2007) 349–365
[25] Csuhaj-Varjú, E., Paun, G.: Limiting the team size in coop- [44] Langer, M.: On hierarchy of the positioned eco-grammar
erating grammar systems. Bulletin of the EATCS 49: 198- systems Kybernetika 50 (5), 696-705 2 2014
201(1993) [45] Langer, M., Kelemenová, A.: Positioned agents in eco-
[26] Csuhaj-Varju, E., Vaszil, Gy.: On context-free parallel grammar systems International Journal of Foundations of
Computer Science 4(2011) 237-246
[46] Lukáš, R., Meduna, A.: Multigenerative grammar systems
and matrix grammars. Kybernetika 46 (2010) 68-82
[47] Martin-Vide, C., Paŭn, G.: PM-Colonies, Computers and
Artificial Intelligence 17 (1998)553–582.
[48] Martin-Vide, C., Paŭn, G.: New topics in colonies theory,
Grammars 1 (1999) 209–323.
[49] Mateescu, A.: Teams in cooperating distributed grammar
systems; an overview, Proc. Decentralized Intelligent and
Multi-Agent Systems, DIMAS‘95, Cracow, (1995) 309–323
[50] Meduna, A.: Two-way metalinear PC grammar systems
and their descriptional complexity. Acta Cybernet 16 (2003)
126—137
[51] Meduna, A., Lukas, R.: Multigenerative grammar systems.
Schedae Inform. 15 (2006) 175—188
[52] Paun, Gh.: On the synchronization in parallel communicat-
ing grammar systems. ActaInf 30 (1993)351–367
[53] Paun, Gh., Santean, L.: Parallel communicating gram-
mar systems: the regular case. Ann.Univ. Bucharest, Ser.
Matem.-Inform. 38 (1989) 55–63
[54] Păun,G., Salomaa, A., Vicolov, S.: On the generative ca-
pacity of parallel communicating grammar systems. Internat.
J. Comput. Math. 45 (1992) 45–59
[55] Rozenberg, G., Salomaa, A. eds.: Handbook of Formal
Languages. Springer, Berlin 1997
[56] Rovan, B., Slast’an, M.: Eliminating Communication
by Parallel Rewriting. Developments in Language Theory
(2001) 369-278
[57] Sebestyén, P., Sosík, P: Modelling Multiple Robots in
Space: An Adaptive Eco-Grammar System. Fundamenta In-
formaticae, 2007
[58] Subramanian,K. G., Venkat, I., Csuhaj-Varjú, E.: On
the power of permitting features in cooperating context-
free array grammar systems. Discrete Applied Mathematics
161(15): 2328-2335 (2013)
[59] Vaszil, G.: On simulating non-returning PC grammar sys-
tems with returning systems. Theoret. Comput. Sci. 209
(1998)
[60] Vavrečková, Š.: Eko-kolonie. In: Kognice a umělý život V,
Silesian University, Opava, (2005) 601–612
[61] Vavrečková, Š.: Eco-colonies. In:MEMICS 2006, Proc. of
the 2nd Doctoral Workshop, University of Technology, FIT,
Brno, (2006) 253–259
[62] Vavrečková, Š.: Properties of Eco-colonies. In:Information
Systems and Formal Models 2007, A. Kelemenová, Silesian
University, Opava, (2007) 235–242
[63] Vavrečková, Š, Kelemenová, A.: Properties of Eco-
Colonies. In: Proc. Automata for Cellular and Molecular
Computing, G. Vaszil (ed.), MTA SZTAKI, Budapest (2007)
129–143