We study sequential colonies introduced in [5], [9] from the point of view of their environmental structures. We give expressions for the languages Life, Garden-of-Eden, Doomsday and Non-life and we present conditions for the emptinessof these languagesfor the sequential colonies with basic and terminal mode of the derivation. I{eywords: b mode colony, t mode colony, garden of Eden, life, doomsday and nonlife states and languages,characteristic vector of the environment
Grammars and grammar systemscan be treated not oniy as languagegenerative devices,but also as rewriting systemsfor the states of the environment, which are rcprescnted by strings over the fixed alphabets. From this point of view, the ruies of the system and the way how are they applied are important for the development of the environment, while the starting string and the terminal alphabet play no role. Typical states of the environment, the garden-of-Eden, life, doomsdayand non-life, we will deal with, are knorvn from the investigation of ttreory of cellular autornata. This classificationof the statesof the environmerrt is determined by (im)possibility of each state to produce next state as well as by (im)possibility of eachstate to be produced by another state.
A state is called a garden of Eden, if it cannot be derived from another state and it can produce next state. A state is cailed a doomsdayif it is derived from another sta,teand it cannot produce any other state. A state li,fecan be derived from another state and can produce a new state and a state nonlife neither can be derived nor can produce any new state.
In the present paper we study the above mentioned states and their sets (languages)for grammar systems l2),[4),namely for their special casecalled the colon'iesB.y u colony we mean a grammar system with simple components,introduced in [5]. The componentsof the colony,eachof whic]r is able to produce only the finite language, rewrite the common string by given protocol of the cooperation. The study of the states garden-of-Eden,life, doomsday and non-Ii,fe and, their sets was for colonies initiatized and motivated in [9], [10], where colonies with point mutation, PM colonies for short, \Mereintroduced and studied. Results presented in [9] include among the others also the regularity of the above languagesfor PM colonies.Environmentai structures are studied more detaily in [7], namely conditions for emptinessand finitenessof languagesare discussed.
In the present paper the sequentr,acloloni,eswill be investigated from the same view point. So we will continue the study of the structure and properties of the garden-of-Eden, life, doomsday and non-life for sequential colonies.We will discussboth b and I mode of the derivation in colonies.We wili characterize languages of these structures of the environment, discuss their emptiness, (in)finiteness. We present new results for b mode of derivation. Results for I mode are revised and extended version of our results from [8].
In Section 2 we introduce the languages Garden-of-Eden, Life, Doomsday and Non-life generally, for any string rewriting systems, and the characteristic vector of the structure of the environment of the rewriting system. Some basic properties of these notions are included.
In Section 3 we turn to coloniesand discussabove mentioned topics in detail first for b-mode coloniesand then for f-mode colonies. 2 states of the environment and their dvnamical properties Assume the states of the environment to be given by V*, the set of all strings over fi.xed alphabet V. Let a binary relation on I/*, the d.erivation step :;, defines global transformation of the states of the environnrent d.eterrninedby local rewriting rules P. Let S: (7.,P,=+) determine the rewriting system.
To charactefize some low level dynamic of 5 we will study following sets of states: A state w QV* is said to be aliuein S if there is a state z e V*,2 * u.rsuch that u.'+ z. A state which is not alive is said to be d,ead.
A state tt e V* is said to be reachablein5 if there is astate z eV*,zf w such that z + u. A state which is not reachableis said to be unreachabtein S.
We denoteby Ali,ue(S),Dead(S), Reachabie(S)and (Inreachable(St)he languagesof all alive, dead, reachableand unreachablestates, respectively.By intersecting the classesin the two classificationsabove,we get four ianguages:the Garden-of-Edenof s - GE(s), the Life of S - LF(S), the Doomsday of S DD(S) and the Non-life of 5 - ,^/I,(S).
GE(S) : Unreachable(S)n Ali.ue(S), LF (S) - Reachable(S)n Aliue(S), DD(S) : Reachable(S)n Dead(S),
NL(S) : Unreachable(S)n Dead(S).
To study the emptiness of the above languagesfor a given rewriting system 5 we will use a characteristic function 1 of the language .L defined as Structuresof the Environment in Colonies The characteristic vector X(S) of the environment of 5 is defined as x ( s ): ( y ( G E ( s ) )x, ( r r ( s ) ), y ( D D ( S ) )x, ( l / r ( s ) ) ) Directly from the definitions we have
Corollary 1. For arb'itrary S
X ( S ) e { (
Proof. DD(S),GE(S),If(S),i\fr(S) form the partition on I/*, so at least one
componentof the 1(S) is equal 1 and X(S) : (0,0,0,0) for no ,S.
The condition y(Gn@)) : t from Lemma 1 givesX(S) : (
T h e c o n d i t i o nX @ D ( S ) ) : 1 f r o m L e m m a l g i v e sX ( S ) : (
Colonies rtu'ereintroduced in [5] as grammar systems [2],[4] consisting of a finite collection of very simple grammars rewriting symbols on common string environtnent. Each agent is allowed to trasform its start symbol into finite set of words.
Definition 2. A colo'nyC i,s?-tupl,eC: (V,T,R), where
V is a finite non-empty alphabetof the colony, T c V i,sa non-empty terminal alphabet,
R : { ( S , r ) | S e V , F e V - { S } ) . , Ff i n i , t eF, * A } i,,sa fi,ni,temulti,set of component.s(,5,.F), where S i,sa start symbol of the component (S, .F) and F r,sa fi,nite languagegeneratedby the cotnpo,nen(t.9,F). Note /. Terminal alphabet T, which plays basic role in the definition of the languagedetermined by a colony will play no role in our considerations.Nevertheiess,we decided to present here the original, i.e. grammar system, definition of tlre colony rartherthen grarnrnar schemeversion C - (V,R). F o r C - ( V , T , R ) a n d R : { t r , . . . , c n } , w h e r e c i : ( S i , , Q ) f o r | < i ( n w e f i x the notations:
Dom ci : St
Val c6 - Ft rL D o m ( : { D o m c i : l < i < r } Val C: LJ,:r Val ci
Depending on the motivation, severalways were consideredto introduce the derivation step :=v in coloniesC: (V,T,R). This led to the different variants of coloniesintroducede.g.in [3], [9],etc.
In next sectionwe will considersequentialcoloniesC : (V,T,R) with basic and terminai modes of the derivation, where the derivation stepswiil be denoted by 4 f.orr € {b,l}. Correspondingrewriting systemsspecifiedby (V. ,R,+) will be denoted as C, f.orr € {b, r}.
In a sequential colony, there is active exactly one component, in each derivation step. In a basic mode the active component is ailowed to rewrite one occurrenceof its start symbol in an actual string - we speakon b -mode derivation and b -mode colony. In a terminal mode the active component has to rewrite all the occurrencesof its start symbol in an actual string - we speak on f -mode derivation and t -mode colony. In next subsections,formal definitions of the rewriting steps and the characterization of structures of these colonieswill be presented.
For the sequential colony we first recall the definition of the basic mode of derivation.
D e f i n i t i o n 3 . L e t C : ( V , T , R ) b e a c o l o n ya n d , R - { ( ^ g , F ) | S e V , F e ( V - { S } ) . , F f i n i t e , F * A } . T h e n , 4 y iff r : tr15r2, a : rtwr2 for son'Lceornponenf(^9F,) e 7? and w € F. We denote by C6 the rewriting system determined by the colony C : (V,T,R) and by the derivationstep -5, i.e. C6: (V*,,R,4) and we denoteby COL6 the collectionof all rewriting systemsC6.
To expresslanguagesof environment for C6we have directly from the definition
Dead(C6): (V - Dom C6)* Reachable(Ca:) V* V al C6V" (Jnreachable(C6: ) V* - V*Val C6V*
This leads to the following expressionsfor our languages.
G E ( C ; ) - V * D o m C a V *- V * V a l C 6 V * DD(C;) : (V - Dom.C).(Val C6-V* Dom C6V*)(V - Dom C)" NL(Cb): (V - Dom Ca)--V'Val CoV*
Each word in LF(C6) h* to contain an element of Dom Cu and a subword from V al Ca.
Each word in GE(C6) h* to contain an element of.Dom C6 and no subword from Val C6.
Each word in DD(C6) has to contain subword from VaI Cu and no element of Dom C6.
Each word in IYL(C6) has to contain no element of.Don't C6 neither a subword from Val C6. tr Depending on the mutual position of symbols from Dom C6 and words from VaL Cawe can expressthe iife states as follows C o r o l l a r y 2 . L F ( C ; ) : V * V a l C 6 V * D o mC a V * U V " D o m C aV " V a l C 6 V * l) V* (V* Dom CaV* i V aI Co)V*
For (non)emptinessof the languagesabove we obtain following conditions:
b) GE(C;) + A ffi V" Dom CuV* - V'FVaI C6V. I A c) DD(C6) + A i,ff Val C6- V" Dom CbV- + A d) I,lL(Cb) + A iff V - Dom Ca)"- V*VaI C6V- l0 Proof. a) By the definition we have ,S€ Dom C6and w e F for some (5, F) e R rvhich givesSw e LF(C;). c) Evidently VaI C6-V* Dom C6V* c DD(CI). On the other sideif w e DD(C6), then trr € (V - Dom Cu)*, and u,' : lDruu2 f.or some u e Val Ca. This gives u e Val Cu- V" Dom C6V*.
Points b) and d) foilow directly from the Theorem 2. n
b) If DD(Cb) l0 tlrcn it i,sinfi'nite.
Proof. a) For the string ^9tufrom the proof of Theorem 2 we haveS+w C LF(Cb). b) For u € DD(C6) we have also u* e DD(C).
I'{ote2. Nonempty GE(C6) and nonemptyM(Cb) can be either finite or infinite. Denote by y(COtr6) the set of all characteristic vectors of C6.
T h e o r e m 3 . y ( C O L ) : { (
y ( C O L 6 ) C { (
All these vectors can be reached.
x ( c o ) : (
a* c GE(C;), (bb)+ c LF(C), (r")* c DD(C;), c* c IIL(C;).
X ( C a ): (
X(Ca): (
GE(CI) : A, at c LF(CI), cc* c DD(cb), c € Iv L(Cb).
X ( C a ): (
G E ( C b ) : $ , a * c L F ( c b ) , c * c D D ( c b ) , I v L ( C b ) : A .
X G u ) - (
GE(Cb): A, a+ c LF(CI), c* c IVL(C6), DD(CI) - 0.
X ( C a ): (
Colonies with t-mode derivation Another possibility to define a derivation step in a sequential colony is that an active component is allowed to rewrite all occurrencesof its start symbol in an actual string. We speak on a terminal mode of derivation (t-mode for short). D e f i n i t i o n 4 . L e t C - ( V . , T , R ) b e a c o l o n y a n d R ( V - { S } ) . , F f i n ' i t e , F + 0 } . T h e n i ( S , f ) l S e V , F C r 1 A i , f f r : r 1 S r 2 S r z . . . r * S f r r n t r , r r z 2 . . . r m . * r e ( V - { , 5 } ) . , a : !XyW1I2IX2T3 . . . ImUrnTrn*l t f o r s o m e ( S , l r ) € R a n d u j e f ' , 1 < j < m .
We denote by Ct the rewriting system determined by the colony C : (V,T,R) and by the derivationstep i;, i.e. C1: (V*,R,+) and we denoteby COLI the collectionof all rewriting systemsC1.
To expresslanguagesof environmerrt for C1we have directly from the definition: Note that C6 and Ct differs in the sets .Reachableand Unreachable but not in Aliue and Dead.
Structureosf theEnvironrnenint Colonies
tr
b) LF(C;)+ 0 ''tr lDomCtl> 2 c) DD(C1+) A tff (ValC1- V"DomCtV")+ 0 d) I{ L(Ct)+ 0 iff (V - Dom Cr)"- V*Val Cy. + A Proof. a) Let Dom C1- {51, . . . , ^9"}.Then (Sr 52... S,)+ C GE(CI). It foliows from the condition that F e V - {S})* for (^9.,F) €R. b) Let lDom Ctl > 2 and Sr,,9z e Dom Ct. Let u e F for (,51-,F) e R. Then (.Sr)* c LF(Ct).
Let Dom q: {S}. Then words containing ,Scannot be derived and words not containing ,9 do not produce any word. Therefore LF(C1) : A.
Points c) and d) follow from definitions. tr 'i#i;)t?,'\ff\':,'ffi; Corollary 4. GE(Ct) is infirtzte.
Proof. Results for GE and LF follows from the previous proof.Let DD(C.) *0 and u e Val Ct - V* Dom C1V*. Then u+ C DD(CI).
D IVote3. I.{onemptyM(Ci) can be either finite or infinite.
Denote by y(COLl) the set of all cha;'acteristicvectors of C1.
T h e o r e m 6 . y ( C O L t ) : { ( t , 0 , 1 , 0 ) ,(
x ( C O L t ) q { (
X ( C t ) : (
G E ( C . ) : { a , b } + - 6 + , L F ' ( C ; - A , D D ( C ) : b * , I V L ( C ) : A .
XQt) : (
{ o , b } * - b + c G E ( C I ) , L F ( C I ) : 0 , b + c D D ( C ) ,
X G t ) : (
G E ( C t ) : { a , b } * - c r *- b * , L F ( C t ) : a * u b + , D D ( C t ) : 0 , N L ( C ) : A .
X ( C t ): (
( a b 1 +c G E ( C I ) , b + c L F ( C I ) , D D ( C I ) : 0 , c * c M ( C t ) . ! 4
C o n c l u s i o n s Structures of the environment of the b-mode coloniesand l-mode coloniesdiffer in some aspects.According to the presentedresults we have
I) LF(Cb) is infinite for every Caand GE(Ct) is infinite for every C1. 2) Nonempty DD(C6) implies that DD(C6) is infinite, while nonempty GE(Cb) and ,n/tr(C6)can be either finite or infinite.
Nonempty LF(C) and nonempty DD(C1) imply that these languagesare infinite, while nonempty l,l L(Cb) can be either finite or infinite.
3) The set of characteristic vectors of COLb consistsof 9 vectors, while the set of characteristic vectors of COLt consistsof 6 vectors.
The topic studied in this paper is applicable to all other variants of colonies [61 as well as for the other types of rewriting systems.