Eco-coloniesare new grammar systems with very simple regular glarrunars called agents. Every agent gerreratesits own finite language, all agents cooperate on the shared environment. The environment is not changed only by agents, but it can develope itself. The generating power of eco-colonieswas discussed in several papers, eco-colonieswere compared especially with various types of colonies,but not all relations were proved. In this paper we summarize the published results and we present some other non-published results about the generating power of eco-colonies. I{eywords: Eco-colony,0L eco-colony,EOL eco-colony,property, colony, agent, component, grammar system
Colonies were introduced in [ ] as collections of simple grammars (called components) working on common environment. A component is specifiedby its start symbol (an object or another symbol from the environment, the component can find its start symbol in the environment and processit) and by its finite language. This language determines actions to do with the start symbol, it is usually a list of words, the component substitutes its start symbol by some of these words. The environment is static, only the components can modify it.
There are several variants of colonies with various types of derivation. The original model was sequential(only one component works in one derivation step), the other basic types of derivation are sequentialwith parallely working components or parallel. Parallel colonieswere introduced in [3], parallel behaviour of a colony meansworking all the componentsthat can work (the component whose start symboi is in the environment and no other component is occupying tiris symbol for the actual derivation step), one component processesone occurrence of its start symboi.
Eco-colonieswere first studied in 17],their EOL form in [5,6]. trco-colonies are colonieswith developingenvironment. The concept of developingof the environment is inspired by another type of grammar systems,eco-grammar systems (t2]) The environment is not specifiedonly by its aipliabets I/ and ? but as 0L (one alphabet) or EOL (two alphabets) scheme.Every symbol of the environment not processedby agents (components) is overwritten by some of the developing rules of this scheme.
Eco-coloniesare useful for modelling some simple processesin nature and it is not so hard to programme the model. Here are some elementary examples of models: - rabits (agents) on a meadow (environment), the developementof the environment means growth of grass,the piecesof soil without grass are (or are not) replaced by the grass-blades,the grass-bladesnot eaten by rabbits can grow, colony of ants (the ants * agents- work on the shared environment - ant-hill and its neighbourhood), drug (agents) acting on a bacterial cuiture.
In this section we define colonies,two types of eco-coloniesand then two types of derivation in eco-colonies.
Definition 1. A colonyi,san /1-tupleC: (V,T,R,ws), where
V is a finite non-emptg alphabetof the colony, - T is a non-ernpty termi,nal alph,abeotf the colony, T C V, - R i,s a fi"nite (multi)set of components,
R : { ( ^ 9 , F ) l S e ( V - T ) , F g V - { ^ 9 } ) . , F ' i s f t n ' i t ea n d n o ' n - e m p t y } , S is the start symbol of the coTnponen(.9,.F) and F ts the finite languageof th'is component, - us is the atiom.
We know severaltypes of derivations for colonies,here are tire ba-sictypes:
The exact definitionsof basic types of derivation in coloniesare in 1I,3,4,7., 5], definitions of an eco-gralnmar system and its type of derivation are in [2]. Deflnition 2. LetC be a colonUC,: (V,T,R). The languagegeneratedby the deriuat'ionstepr,r e {b,t,wp,sp} in C i,s
L ( C , r ) : { w e T * | u s $ r y Definition 3. An E7L eco-colony of degreen, n E : ( E , A t , A z , , . . . , A n , w o ) ,w h e r e - E - (V,7, P) i,sE}L scheme,wltere c V is a fini,te non-empty alphabet, o T 'is a non-empty termi,nal alphabeLT g V, . P 'is a fin"ite set of E}L rew'nting 'rulesouer V , - Ai: (S,, Ft), L < i 1n, 'isthe i,-th agent,where o ,.9t€ V i.sthe start symbol of the agent, . Fi Q (V - {5r}). is a finite set of action rules of the agent (tlte language of the agent), - ws i,sthe ariom.
An 0L eco-colongis defined similarly, only the environment is 0L scherne E: (V,P), P is a finite set of 0L rewriting rules over I/.
As we can see, agents are defined such as components in colonies, an environment is determined by the alphabets in coionies,and by EOL or 0L scheme in eco-colonies.
\AIedefine two derivation modes for eco-colonies - the first one, tlp, is inspired by the urp mode for coionies,we only add possibility of developing for the environment. In every derivation step each agent (S, .F) looks for its start symbol ,5. If it finds some occurrenceof this symbol not occupied by any other agent, the agent becomesactive, occupies this symbol and rewrites it by some of words of its IanguageF.
Definition 4. We d,efi"nae weaklqcompeti,tiueparallel deriuation step in an ecoc o l o n yD : ( E , A t , A z , . . . , ,A n , w o ) b y a 3 1 p , w l t , e r e - a - ? o S r r l r S U ^ / 2... ^ 1 , - t 5 i l " 1 , , r ) 0 , - P : l ' o f i r l l f i r l z " t ' r - t f + l ' , , A i u : ( S r * , F t * ) , f t o € F i u , 1 < k 1 r ( t h e ugentA;u r,sactive in this deriuation step), - { i t , i 2 , . . . , ' i , l q { 1 , 2 , . . . , n } , i r * i , n f o r e u e r yk * m , I ( k , m 1 r , - fo, euer?JsymbolS e V t llo^tt...^t,ls > O then euery agent wi,thth'estart symbolS must be actiue (i,f agents can work tltey must work), - ^yx& -.rf, ^{t,€V*, 0 < k < r, is tlte d,eriuat,iosntep of the schemeE.
The second type of derivation step, ap, means that all agents must work in every derivation step and if some agent is not able to work (there is not any free occurrenceof its start symbol), the derivation is blocked.This type of derivation is inspired by the basic type of derivation in eco-grammar systems. Definition 5. We def,ne o, deri,uationstep ap (all are work'ingparallely) in an e c o - c o l o nDA : ( 8 , A r , A 2 , . . . , A n , w o ) b y a + p , w h e r e - o - 7oSi,^ltSU^lz. . . ^ln-rSi-^ln, - B - ^ r ' o f i r ' i f u 1 z " ' ^ r ' r - t h - 1 ' n , A i o : ( S 0 . ,F t u ) ,f u e F i o , l S k S n , { 1 , 2 , . . . , n } ( e u e r ga g e n tw o r k s ' i ne u e r yd e r i u a t i o ns t e p ) , - { i r , i 2 , . . . , i n } : - ^lt 4 il, jt" € V* ,, 0 < k < n, is the d,eriuationstep of the schemeE. D e f i n i t i o n 6 . L e t D b e a n 0 L e c o - c o l o n yD, - ( E , A t , A 2 , . . . , A n t l o ) . T h e languagegeneratedby the deri,uattonstep r,,r e {wp,ap} i'n D i,s
L ( E , r ) : { , e V * | * o 4 . } Erample /. We createan EOL eco-colonyD : (E,Ar,A2,AbB), where E - - ( { A , B , a , b } , { o ,b } , { o , e , , ,-b- b b } ) ,A r : ( A , { a B , e } ) , A z - ( 8 , { a A , e } )
Let us construct derivations with ap and tlp types of derivations: A b B 4 a B b 2 a A 4 a z A b a a 2 B$ q s g 6 8 a 3 A $ q + n 6 r 6 o a g4 . . . AbB 4 aBbzaA ry a2Abaa2B 3 a2b8a4s $ o26r6oaBry . . .
The wp derivation allowes "resting" of non-active agents. If we use the ap type of derivation, a terminal word is generated only if the both agents use the E-rule in the same derivation step, otherwise the derivation is blocked without creating thc final word.
\Aiegenerate these languages:
L ( E , a p ) :
{ a ' b 2 - a n I n > 0 }
L ( D , w p ) : { o t u z ^a i I n > o , o < i , i = " } 3
We compare the generating power of eco-coloniesand colonies, eco-grammar systems and a special type of colonieswith the terminai alphabet equal to the alphabet of the system. We use this notation: \EC, EEC, r e {up,op} classof 0L eco-colonieswith r type of derivation r Q {up,op} classof EOL eco-colonieswith r type of derivation COL, r e {b,t,wp,sp} classof colonieswith the r type of derivation COLT r e {b,t,up,sp} classof colonieswith the r type of derivation,V -T EG class of eco-grammar systems Properties of Eco-Colonies 3.1 Known results
COL-e c EEC-e }EC-e c EEC-e E E C - e - E G + A
E E C * T - C O L I + a
C O L Tc C O L * , r e { b , t , w p , s p }
jECoe+ \EC-e
C O L Tc T E C - , , r e { b , - p }
aEcoe- COLT*A, * e {b,wp)
} E C a C E G , y e { a p , w p }
(
Theorem 1.
}ECoe c EECoe ( 11 ) Proof. 0L eco-coloniesare special types of trOI, eco-colonieswhere V : T , so the relation 1EC"e g EEC"e is trivial.
To prove the proper subset we use the language
L t : { o 'L" ' ) l n > 1 } This languageis generatedby the EOL eco-colonyE: (E,At,A2,(JVa), where E : ( { o , U , V } , { o } , { o - - a a , ( J' - n( J , V - - +V } ) , A t - ( U , { V , r } ) , A z : ( V ,{ U , e } ) .
UVa 4 Vfla2 + UVaa $ yuq8 -sg UVal6 g ... $ oz"
The agentsdo not generateany word, they exist only becausethe number of agentsmust be greater than 0, and with using the ap derivation all agents must work in every derivation step, so the agents A1 and A2 work with the symbols LI,V untll the final word is gcnerated.
Supposethat this languagecan be generatedby some 0L eco-colonyrvith op derivation. We need at least one agent and this agerrt rnust be active in every derivation step. We have orrly one alphabet V : {a}, so the start symboi of this agent is o. But the agent generatesonly a finite language,so the symbol a is not aiowedin the set of action rules,the agent is definedas.4.: (o, {u}).
The language is exponential and the agent(-s) does not help with growing of the language,so the rule a ---+aa is in the environment. It can generate the language,but the agent "eats" one symbol a in every derivation step and the environment cannot correct it (it is only 0L scheme,any other correcting rule such as a '---Q,aawould be used freely any times and anywhere in one derivation step), so the languageZ1 would not be generated,Lt f \ECoe. tr
I E C , - C O L " * A 0 2 ) w h e r e r e { 0 , - E } , y e { w p , , a p } ,z e { b , t , w p , s p } .
Proof. In this proof we use the languagesimiiar to L1,
L z : {Lc d . a z 'b" " " 'l n -) - )0 ) o- t {- a r o ' 2 n * tU 2 2 n +lt,'t" ->" )o }
T h i s l a n g u a g e c a n b e g e n e r a t e d b y t h e e c o . c o l o n y r w h e r eE : ( { a , b , c , d } , { o- * a a , b- - b b , c- , c , d - - -d } ) , A r : ( c , { d } ) , Az : (d,{.}). cdab+ dca2bz+ cdaaba+ d,ca8b+8 cd,arobro+ .. .
Two agentswork in every derivation step and we use only one alphabet, so it may be EOL as well as 0L eco-colonyand the derivation step may be tlp or ap.
The languageL2 LSnot context-free,so L2 f COL;, and it grows exponentially so L2 f COL-e and L2 4 COL,e (proved in [O]and [5]).
Colonieswith t type of derivation can generate some exponentially growing languages,but only one component work in one derivation step. This component rewrites all occurrencesof its start symbol, and there is only one start symbol in one component. So we can rewrite a or b in one derivation step, but not both. There is not any way to control generating the same exponential number of o-s and b-s,so L2 e COLI. tr
L E C | - C O L T * A w h e r er € { 0 , 8 } , , y e { w p , a p } , z e { b , t , w p , s p } . Proof. Follows from Theorem 2 and Equation (6).
COL, - }EC-e + A, r e {b,t,wp, sp} L s : { a r 5 - 2 n 6 n c b "ld0 ( n I T , n i s e v e n }
( 1 3 )
tr (14) is not in}EC-o. It is a finite language,so.L3e CoL, fbr r € tb, t,wp,sp\. r
Corollary 2. The set of languages}EC-o i,s i,ncomparableto the sets of languagesCOL6, COLI, COL-, o,ndCOL,r.
Corollary 3.
Theorem 4.
CO L, - \ECoe * A, r e {b,t,rup, sp}
L+ : {a, aa}
is not generatedby any 0L eco-colony.But this languageis finite, so La e COL" f"orr € {b, t,wp, sp}. ! Theorem 5.
Proof. We have a colony with the b mode of derivation C - (V,T,R,tus) and we createan EOL eco-colonywith the ap derivationD: (E,At,Az,BC otlo).
The agents ,41 and A2 work very simply - they rewrite onlv one symbol to another one: ,41 : (B,{C,u}), A2 : (C,{B,,e}), such as in the proof of the Theorem 1.
We create rules of the environment from the components of. R. Suppose that all components in R have various start symbol, there is not any couple of componentswith the same start symbol.
For everycomponent(cl,{a1,e2,...,(tk}) *" createdevelopingrulesfor the environment: androreverysymboblwhicht:;i't1'llj], ,r',l1",inanycomponewnetcreate one rule b --- b.
So the environment simulates working of the components in the colony. To simulate the sequential derivation we must allowe to rewrite every symbol to itself. tr Erample 2. We demonstrate the construction of the proof on tire colony generating this language:
L s : { w a w R a i l u e { 0 ,1 } " , i > 0 }
We havea colonyC : ({S,H,H' , A, A' ,0, 1,o}, {0, 1,a},R,S) generatin gthe language,the set of conrponentsR is n : { ( s , u / A i ) , ( H , t 0 . H ' 0L,H ' r , a } ) ,( H " { H } ), ( A , { o A ' , . t r } )( ,A " { A i ) } ! (15)
n (16) (17) B C S4 C p n A 4 4 CntlHlrA4 $ lgsglsq B C S4 C A n A I B C r H , r a H4 4 C a t o H o r a a g l g s g l s s
Now we create an EOL eco-colony with op derivation X : ( E , A t , A z , B C S ) , E : ( { B , C , S , H , H ' , A , A ' , 0 , 1 , o } , { 0 ,1 , a } , P ) , A t : ( B, { C ,e } ) , A z : ( C ,{ 8 , e } ) , the set of rulesP in the environmenits P : { H - - H l 0 H ' 0 l I H ' I l A , H ' - - H ' I H , 1 _ , 1 ,
A -, AlaA'la, A' -. A'IA, 0 -- 0, A - + Q t S - , S I H A |
s,4 na 4 rH,LA+ :HLA4 roa,oL+A r0H0rA4rooora4 4 toootoA' + roaoLaA4 roootoo
Two of possible derivations of the same word in I:
B C T H , L A4 nCtlalrA9
C n t H r A 4 CntlalraA, g s C t l v , l r A g
nCtlalraAJ4 C B r H r a Ag
B c r y H , l r a a4
Proof. Follows from Theorem 5 and Equation (6). (18) ! This work has beensupportedby Grant Agency of CzechR,epublic the grant IVo. 201/ 06/0 56T, "Bzo,inforntat'ika a biouypoit'y:so'u'u'islostm'i,odely, aplikace".