Brief introduction to the colonies,the grammars systemsinteracting on common passiveenvironment with componentsindividually producing finite languages,is presented.An overview of the topic is completed by large number of references. Colony - general model A colony is a collection of (very simple) grammars operating in a common string. By "very simple" we mean a grammar producing a fi,ni,telanguage. First, we present general model of a colony. Different acting possibiiities realizedby different derivation steps,due to different motivations leaclto various variants of colonies. D e f i n i t i o n 1 . A c o l o n yC i s a S - t u p l eC : ( V , T , f ) , (i) V is arr,alphabetof the colony, and (ii) T e V is a terminal alphabetof the colony, ( i i i ) f : { ( S , , F t ) t S t e V , F i e ( V - , 5 i ) . , 4 i s f i n i t e , 1 ( i < r } . A par'r (St, Fi) i,scalled l-th componentof C, Si is r,tsstart symbol and,Fi is the languageof i-tlt component.
I(eywords:
grammar system, colony, generative power, hierarchy
Colonies were introduced in [19], where basic fact on the motivation can be
found. Overviewson the topic are in [
is alsopossible.This specialcaseis discussedin [28],
[
Generally, denote by =5 the relation on strings representingan elementary string transformation realized by components and called a derivation step. Specific types of r introduced la,terdefine various variants of colonies.
As usual, =5. stays for a reflexive anci transitive closure of =5 . It representsstring transformations, called derivation, realized by finite sequencesof elementarytransformations.
LanguageL,(C,tls) determinedby a colony C: (V,T,f) and an initial string (axiom) wo e V* by =5 derivation consistsof all terminal strings derived from the axiom, i.e.
L , ( C , u ; 0 ): { r l , o + . u , u € T " } .
By COL* w€ denote the classof all languagesgenerated by colonieswith S derivation.
The subscript tr, above, can be omitted in the case when it is clear which derivation step is considered.
Basic differencesamong various possibilities of a behaviour of a colony,
due to the number of componentsused in one step. The sequentialmodel and
parallel models discussedin the next sectionsare two examples of behaviour of
colonies.The intermediate cases,coloniesworking in teams are discussedin [
In the sequential models of a colony an elementary change of strings is realized by single conponent. Sequential colonies can differ in the amount of symbols rewritten by a component in one derivation step.
Basic derivation step =:; correspondsto rewriting a single symbol. Total derivationstep i; correspondsto a parallelbehaviourof the chosencomponent. 3.1 Sequential colonies with sequentialy acting components b mode of derivation The simplest case of rewriting in sequential colonies is the case wheu chosen component rervrites exactly one letter in a derivation step. Formally:
In accordancer,vithgeneralcase)the languageof the colony with derivationstep -!+ ir clenoteclLa(C,trs)and COLb is the correspondingclassof all languages.
Proof. Let L e C,F. There is a context free grammar G : (1V,7,P, ,S) such t h a t I : L ( G ) . T o c o n s t r u c ta c o l o n yC : ( V , T , f ) s u c ht h a t L ( G ) - L 6 ( C , r ) for some ?r) we have to determine finite Languagesof components. To do it we eliminate of all rules with direct recursion fron G. Let l/ : {Ze t A e ,A/}, wlrere Z s are new nonterminals.
lVe replace rules of the type A >()) where A occurs in a by two rules A -, aA, ZA --- A, where a4 denotes the word obtained from a by replacing all occurrencesof A by z,t.
Denote bv G resulting grammar G : (N U /V, T, P,.9). Evidently L(G) : L(G) C o n s i d e rt h e c o l o n yC : ( V , T , f ) , w h e r eV : N U , n /U ? a n d F : { ( X , F . y ) : X e l V U l / , { . v : { a : X - - a e P } .
Evidently,C is the colonyand L(G) - L6(C,,5).
It means that rules of the grammar are constructed from componentsof the colony in such a way, that they rewrite the start symbol of the component by a rvord fronr ass<-rciatcfdinitc language.In casewhen original start symbol of some ( omponent was also a terminal symbol, corresponding barred letter is used for the derivation.Evidently,L(G) - La(C,w). I llote 2. In the previous proof we presentedpossibility to transform a colony to an equivalentcontext-freegranrmar and vice versa.This makespossibleto transform many known results on context-free grammars and languagesto colonies. Normal form theorems, resuits on e-rules and many others are exampies of above mentioned properties. Descriptional complexity of colonies measured by the number of conrponentsnecessaryto produce the languageis discussedin [1e]
The case T - V and axiom is a letter, correspondsto languagesof the sententialfbrms. 3.2 Sequential colonies with parallely acting components t mode of derivation In this section we discussa sequentialmodel of colony with parallelism inside the components.Parallelism at the level of a single component, denoted here by $, rneansthat in one clerivationstep one component rewrites all appearances of its start symbol ^9;in an actual string to a (not necessarysame) word of FiDefinition 3. For a colonyC: (V,T,f) and r,A e V* u'e defi,nea terminal deriuation step &4 - y-----\t ?' iff r : r1S;r2Sir3 . . . rrrSirynart r t r z . . . r r n * r € ( V - { S , } ) . ,
. . . IrnUrnTql!t where wi € Fi, for eachj,I < j < m and for somei,l S i 1 n.
In accordancewith generalcase,a languageof a colony with derivation step t is denoted Lt(C,ur6) and COLt is the correspondingclassof all languages.
- V - { A . B , a } , - T - { a } a n d - r :
{ ( A , { B B } ) , ( 8 , { A } ) , ( 8 , { o } ) } .
A + BB + AA + BBBB J, nooo is an exanrpleof derivation in C.
L 1 ( C . A ): { o ' ' t i > 1 } .
We compare class COLt with class COLb as well as with t:lassesof languages generated by other known models of parallel grammars, nameiy L systems and Indian parallel grammars.
Proof. LeLC be a colony with b mode of derivation. Let C be a colony equivalent to C rvith all componentshaving different start symbols. We can construct such a colony by cumulating all components of C with the same start symbol .9 to one component (,5,F) of C. Set -F of new componentis the union of the original sets { of cumulated componentsfrom C.
It holds L,,(C,w) : Lr(a,u), i.e. the words producedby a colony C with b mode of derivation a,reidentical with that of t mode of derivation. The derivations of the same word in these coloniescan differ only in their length.
The inclusionin the theoremis proper. The languagein presentedin previous e x a m p l ei s i n C O L I - C O L ; . I
Furthermore we compare colonieswith t mode of derivation with languages determined by Indian parallel grammars.
An Indian parailel grammar is a quadruple G : (l/,7, P, ,S) specifiedas itr CF grammars with derivation step j4:
An ET}L systemis a quadrupleG : (V,7,P,,5), whereV'is a total alphabet, T c V i s a t e r m i n a la l p h a b e t , , S€ V , P : { P t : 1 S i < n } a n d P , : { A - + ' t D: A e V , u e V * \ .
NloreoverP, i, | < i < n containsat ieast one rule for each A e V. Derivationstep4 of I systemspecifiestotally parallel rewriting: r r + y i f f r : t r \ r 2 . . . ! x m ,' A: a t A z . . . ! J n "w, h e r er r , T 2 , . . . , T r n€ l / a n d riJ - AVJ t € P,, for somei and f.orj,l < j < m.
Theorem 4. COLI C ET}L
Proof. Strongerresult, the equality COLl - ET\Ltlj was proved in [
For a derivation in parallel model of colony is typical that several components are active in a derivation step of the colony.Parallel colonieswere introduced in the principle that componentsof a colony,which can work on the tape musf work simulttrneouslyand each component rewrites at most one occurrenceof its start symboi. To formaiize mentioned requirement the case when more components have the same associatednonterminal requires a speciai discussion: * If (S,.F,), and (S,Fi) are two componentsof a colony C and if (at ieast) two symbols 5 appear in a current string, then both thesecomponentsrnust be used,eachrewriting one occurrenceof 5.
* If only one 5 appearsin a current string, then eachcomponent canbe used. but not both in parallel, hencein such a casewe discusstrvo possibilities (i) derivation is blocked - strongly competitiueparallel way of derivation, and (ii) derivation continues and maximal number of components is used, nondeterministically chosen from all the components which can be used - weakly competiti,ueparallel way of derivation.
This correspondsto the following derivation steps: For r, A € V" define a strongly competi,tiueparallel derivation step by r ' +sp A i f f i : r r S h r z S i r . . . r t S t * ' r k + r ,
U : l t j t Z i r T 2 Z i r . . . I k Z i x t t e + t , Z i i € F l r r I < j < k , i " f i , f o r a l l u * u , L I u , u I k , (one component is allowed to rewrite at most one occurrenceof its start symbol) l"ls, > 0 implies t -- ii for some7, | < j < k (if componentF; can be used, then it must be used).
In accordancewith general case,the languageof a colony with derivation step 4 is denoteclLrr(C,tr,s) and COLre is the correspondingclassof all languages.
C : ( { A , B , C , D , 0 , 1 } ' ,{ 0 , 1 } ,F ) , w h e r e f : { ( A , { 0 8 , 1 C } ), ( A , { 0 C , i B } ) , ( 8 , { A , E } ) , ( C , { A , E } ) , ( 8 , { r } ) , ( 8 , { r } ) }
AA 4 0B0CjS oao.4j+ IICILBl5 orgorr g oror
A A + 0 B I B .
Next sentential form contains either singie occurrencecf.-.1,-..-r8. The colony ha,s
two components to rewrite A and two components to rewrite E. In both cases d e r i v a t i o ns t o p s '
L , o ( c , A A ) - { w w : u € { 0 , r } * } .
For r, A € V* define a weakly competi,ti,upearallel derivation step by r +LDp y iffr : rrS;.rrzSb...rxSt.*rtx;rt lJ: rtZ;rI2Zir...frkZixfrk+ZLii Ft,L S j S k, iu # i, for all u * u,l 1 u,,uI k, (one component is allowed to rewrite at most one occurrenceof its startsymbol) l"ls, > 0 implies St :,S1, for some j, L < j < k, k is the maximal integer with the previous properties.
In accordancewith general case,the languageof a colony with derivation step S is denoted.L-r(C , tus) and C OL-e is the correspondingclassof all languages. Erample 3. Let
C : ( { S ,A , B , C , D , E , F , a , b , c } ,{ a , b ,c } ,f ) , w h e r e f : { ( s , { A B C } ) ,( y ,{ z } ) , ( 2 , { Y } ) , ( A ,{ a D , X } ) , ( 8 , { b E , X } ) ,( C ,{ c F , X } ) , ( D , { A } ) , ( 8 , { B } ) , ( 4 { C } ) , (X, {u}),(X, {e}),(X, {)'})}.
A succesfuldl erivationin the colonyendsby rewriting all occurrenceosf X by e. There are at most three occurrenceosf X in sententialforms produced by the colonybut only wordscontainingat most two X-es canbe rewrittento terminalwords.
S ry ABC # XUncF ry bBcC$ 6yssF ry bccC jlDD fissx +IDD bcc Blocked derivation
S ry ABC3 anUncFry aAbBcC3 axuxcx 3 aby L - , ( C , S ) : { a i V c k l i , j , k ) 0 , i * j o r j + k o r i l k } .
If thc start syrnbolsof all components are different in a paralle] colony, then both 4 and i!$ clefinethe same relation denoteciby =5. For the generative power of COL, we have
b) COLp c COL"e c) COL, C COL-, Proof. a) Let L e CF, L: L(G) for a context-freegrammar G: (/V,T,P,S). Assume, that A does not appear in z for each rule A --) z € P and .A/ : { A t , 4 2 , . . . ,A , r } . C o n s i d e rt h e c o l o n y
C : ( N t ) T , T , f ) , f : { ( A t , { t ; A o - - -z+ e P } ) , f < i < n } .
Clearly,C conta,insexactly the rulesof G and Lr(C, S) S L(G).Also the converse inclusion is true. Take a derivation D ; $ 4* r tn G. The order of applying the rules in D can be modified in such a way to obtain another derivation, D', describedby the same derivation tree as D (henceproducing the same string r), but consisting of subderivationsu + r.'with respect to G such that for every Ai e IV which appears in u, exactly one occurrenceof it is rewritten. The derivation D' is a parallel derivation with respectto C, hencer e Lo(C,S). We have obtained the inclusion CF C COL,.
Conversely,let L e COL,. There is a colony C -- (V,T,f) and an a-xiom u such that tr : Lr(C,tr,'). To construct an equivalent context-free grammar we have to determine set of nonterminals l/ to be strictly disjoin with the terminal set 7. Exactly as for COLa we constructG -- ((V _ T)UV,T,P,,S). Rulesof the grammar are constructed from componentsof the colony in such a way, that they rewrite start symbol of the component by a word from associatedfinite Ianguage.In the casewhen original start symbol of some component was also a terminal symbol, correspondingbarred letter is used for the derivation.
The inclusion.Lo(C,r) e LG) is obvious,the converseinclusioncan be obtained as previously,henceLo(C,w) : L(G) and COLp e CF.
For I"o * Lsp(C,AA) from the Example 4.1 we have L,p e COL,e - COLp. For L*o: L-p(C,,5) from the Example4.2we haveL.p e COL,,,p-COLp. r To specify the generative power of parallel colonies more detailly we use matrix grammars with appearancechecking An ET\L system is a construct G (E,T,H,-), where f is a vocabulary,T g E, w e. E+, and.I/ is a finite set crftalrlcs, thalt is of firiite substitritions lr ; E* --' 2t-. For h e H and r € D* we define the l-iimited irnage l't(r) as the set of all strings in ,!* which can be obtained from r by replacing for each a e E which appears in r exactly one occurrenceby an elementof h(a). Thus, the 1-limited generatedlanguageis
L r t ( G ) : { z e T * ; z e h n ( h u - t ( . . . ( h r ( r ) ) . . . ) ) ,)r , 0 , h i € H , f o r a l l 7 } Note l. A matrir granxrnar(with appearancechecking)is a construct G : (l/,7, IuI,S,F), where l/ is a nonterminal vocabulary,? is a terminal vocabulary,,S€ .A/is the a symbol, /'f'1is a finitc sct of firritc scquerrccsclf context-frec rules ar,nd ,F is a set of occurrencesof rules in IuI. The derivations start from ,5 and consist of stepsof using matricesin fuI; when using a matrix (Ar * rr,...,-Ln - frn), all the rules are used,in this ortier, and this meansthe symbols A; arc effectivcly rewritten by ,, if they appear in the current string, with the possibility to skip the rules A; - 11 which appeerrin F but Ai does trot appear in the current strirrg. and l-lirnited ET0I systems.
We denote by IVIATo. the family of languagesgenerated by matrix grammars with appearance checking (without using e-rules) and by LIET\L the family of languages generated by 1-limited ET\L systems. It is known that C F c lvIATo" C C S, strict inclusionsfor s free grammars. IIET\L is strictly included in IvIATo".
Open problems: What is the relation betweenCOL-. and COLro.
Is the inclusion COL"e C L,IATo" proper?
What is the influence of E in components of the colony on the generative power. 5
Further Research Topics and Open Problems Large nunrbcr of problenrs were invcstigated fbr colonies.!!i: trriefly surnruarize them with referencesto the original papers.
First we mention various variants of the basic model of a colony. The choice
of tcrminal alphabets influences the generative capacity. Cases T - I/ and
V etT * 0 for sequentialcolonies\verediscussedin [
Results on parallel coloniescan be found in [
The role of e rules in different models has to be discussed.No resuit in this direction was done and at least for some types of coloniesthe absenceof E rules will reduce their generative power.
Descriptional complexity of coloniescharacterizedfor example by the number of componentswere discussedin [19],1421.
Topics like stability and inferencewere open in [19] and [a3], respectively.
There are several extensions or modifications of the basic model. Between
sequential colonies with t and b mode of derivation the colonies with k active
componentsin one step can be treated [
Consequencesof restriction of using components in the senseof frequency or
fixcd period of forbidden activity of componentswerc trcated in [19], [23],122).
Diffcrent motivations leadsto more significant modifications of the basic model.
Coloniesrvith point mutations, PNI colonies[
Symbiosisand parasitismwere inspiration for models introduced in ff fl.
Inspirations from automata theory inflrrencedpapers [
Unreliable coloniesare introduced and discussedin [
Coionieshave constant environment. I,Iodels,rvhereenvironment can be changed.
by inner rttles, namely e-coloniesand eco-coloniesw,ere also introcluced.These
models caIIIe rip comitining ideas concerning the internal behaviorrr of the
environrnentin the eco-grammarsvstems181[,29],[
A. Kelemenovd behaviour of the componentsof the colonies.[a6], [47), [48].
In last few years one very interesting type of colonieswas introduced on the base
of membrane systems.So called P coloniesare studied in [25], [21], [