Structures of the Environment                          in Colonies

                    Alica Kelemenov6l'2    and Adam KoZany3

         Institute of Computer Science,Faculty of Philosophy and Science,
                     Silesian University in Opava, Czech Republic
               Department of Computer Science, Faculty of Pedagogy,
                      Catolic University in RuZomberok, Slovakia
       Institute of the Public Administration and Regional Policy, Faculty of
       Philosophy and Science, Silesian University in Opava, Czech Republic
                     a1ica. kelemenova,adam.kozany@fpf . s1u. cz




      Abstract.    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 emptiness of these languages for the sequential
      colonies with basic and terminal mode of the derivation.


      I{eywords:  b mode colony, t mode colony, garden of Eden, life, dooms-
      day and nonlife states and languages, characteristic vector of the envi-
      ronment



    Introduction

Grammars and grammar systems can be treated not oniy as languagegenerative
devices, but also as rewriting systems for 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, doomsday and non-life, we will deal with, are knorvn from the investigation
of ttreory of cellular autornata. This classificationof the states of the environmerrt
is determined by (im)possibility of each state to produce next state as well as
by (im)possibility of each state 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,fe can 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'ies.By u colony we mean a grammar system with simple components,intro-
duced in [5]. The components of the colony, each of whic]r is able to produce only
 190      A. Kelemenovdand A. Koiani


 the finite language, rewrite the common string by given protocol of the cooper-
 ation. 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. Re-
sults presented in [9] include among the others also the regularity of the above
languages for PM colonies. Environmentai structures are studied more detaily
in [7], namely conditions for emptiness and finiteness of languagesare discussed.
     In the present paper the sequentr,alcoloni,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 discuss both b and I mode of the derivation in colonies. We wili character-
ize 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 colonies and discussabove mentioned topics in detail
first for b-mode colonies and 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 s ta te w Q V * i s s a i d to b e al i uei n S i f there i s a state z e V * ,2 * u.rsuch
that u.'+    z. A state which is not alive is said to be d,ead.
A sta te tt e V * i s s a i d to b e re a chabl ei n5 i f there i s astate z eV * ,zf w such
that z +     u. A state which is not reachable is said to be unreachabtein S.
    We denoteby Ali,ue(S),Dead(S), Reachabie(S)and (Inreachable(S)the lan-
guages of all alive, dead, reachable and unreachable states, respectively. By in-
tersecting 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).
De fi n i ti o n   1.   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 languages for a given rewriting system 5
we will use a characteristic function 1 of the language .L defined as
                                                          Structuresof the Environment in Colonies                         l9l


                                             XQ):0                 forL-A
                                             XQ) : I              otherwise'

The characteristic vector X(S) of the environment of 5 is defined as

                 x(s) : ( y(GE(s)),x(rr(s)), y(DD(S)),x(l/r(s)) )
Directly from the definitions we have

Le mma 1 . A t l e a s t o n e o f th e sets GE (S ) ,LF(S ),D D (S ) and IY L(S ) i ,s i ,nfi -
ni,tefor any S.
           I f y ( G E ( S ) ) : I t h e ny ( L F ( S ) ) : 1 o r y ( D D ( S ) ) : 1 .
           I f y ( D D ( 5 ) ) : I t h e nx Q F ( s ) ) :    I or x(GE(s)) : 1.

Corollary 1. For arb'itrary S
   X ( S ) e { ( 0 ,1 , 0 ,1 ) ,( 0 ,1 , 1 , 1 ) ,( 1 , 0 ,1 , 0 ) ,( 1 , 0 ,1 , 1 ) ,( 1 ,1 , 0 , 0 ) ,( 0 ,1 , 1 , 0 )
                ( 1 ,1 , 0 ,1 ) ,( 0 ,1 , 0 , 0 ) ,( 0 , 0 , 0 ,1 ) ,( 1 ,1 , 1 , 0 ) ,( 1 ,1 ,1 , 1 ) ) .

Proof. DD(S),GE(S),If(S),i\fr(S)                    form the partition on I/*, so at least one
c o mp o n e n to f th e 1 (S) i s e q u a l 1 and X (S ) : (0,0,0,0) for no ,S .
T h e c o n d i ti o n y (G n @ )) : t from Lemma 1 gi ves X (S ) : (1,0,0, 1) for no 5
a n d 1 ( 5 ) : ( 1 , 0 , 0 , 0 )f o r n o 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 ) : ( 0 , 0 ,1 , 0 ) f o r n o 5
an d X (5 ) : (0 ,0 , 1 , 1 ) fo r n o 5 .                                                                 f,

In this paper we will discussvectors X(S) for rewriting systems called colonies.


       Colonies

Colonies rtu'ere
               introduced in [5] as grammar systems [2],[4] consisting of a finite
collection of very simple grammars rewriting symbols on common string envi-
rontnent. 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,s a 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,s a start symbol of the com-
ponent (S, .F) and F r,sa fi,nite languagegeneratedby the cotnpo,nent(.9,F).

Note /. Terminal alphabet T, which plays basic role in the definition of the
language determined by a colony will play no role in our considerations.Never-
theiess, we decided to present here the original, i.e. grammar system, definition
of tlre colony rarther then grarnrnar schemeversion C - (V,R).
192      A. Kelemenovdand A. Koiani


ForC -(V,T,R) andR:              {tr,.. .,cn}, where ci:            (Si,,Q) for | <i   ( n we fix
the notations:
   Dom ci : St                                    Val c6 - Ft
                                                               rL
    Dom(:{Domci:l<i<r}                                         Val C: LJ,:r Val ci
    Depending on the motivation, several ways were consideredto introduce the
derivation step :=v in coloniesC: (V,T,R). This led to the different variants
of c o l o n i e si n tro d u c e d e .g . i n [3 ], [9], etc.
    In next section we will considersequentialcoloniesC : (V,T,R) with basic
and terminai modes of the derivation, where the derivation steps wiil be denoted
by 4       f.o rr € { b ,l } . C o rre s p ondi ngrew ri ti ng systemsspeci fi edby (V . ,R ,+ )
will be denoted as C, f.orr € {b, r}.
    In a sequential colony, there is active exactly one component, in each deriva-
tion step. In a basic mode the active component is ailowed to rewrite one occur-
rence of its start symbol in an actual string - we speak on 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 deriva-
tion and t -mode colony. In next subsections,formal definitions of the rewriting
steps and the characterization of structures of these colonies will be presented.


3.1     Colonies with b-mode derivation

For the sequential colony we first recall the definition of the basic mode of
derivation.

Definition 3. LetC:    ( V , T , R ) b e a c o l o n ya n d , R -        {(^g,F) | S e V,F e
(V - {S}).,Ffinite, F *A}. Then
, 4     y iff r :   tr15r2, a : rtwr2 for son'Le
                                               cornponenf(^9,F) e 7? and w € F.

We denote by C6 the rewriting system determined by the colony C : (V,T,R)
an d b y th e d e ri v a ti o n s te p -5 , i .e. C 6: (V * ,,R ,4) and w e denote by C OL6
the collection of all rewriting systemsC6.
    To express languagesof environment for C6 we have directly from the defini-
tion

Lemma 2. Aliue(Co) : V" Do,m CuV*
         Dead(C6): (V - Dom C6)*
         Reachable(Ca): V* V al C6V"
         (J n re a c h a b l e (C 6: ) V * - V * V al C 6V *

      This leads to the following expressionsfor our languages.

T h e o re m 1 . L F (C ;) : V * D o m C aV " )V " V al C 6V *
                 G E ( C ; ) - V * D o m C a V *- V * V a l C 6 V *
                 D D (C ;) : (V - Dom. C ).(V al C 6-V * D om C 6V * )(V - D om C )"
                 N L ( C b ) : ( V - D o m C a ) -- V ' V a l C o V *
                                                            Structuresof theEnvironment
                                                                                      in Colonies                     193


 Proof. Follows from the definitions and Lemma 2.
 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
 Do m C 6 .
 Each word in IY L(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 Ca we can express the iife states as follows

Corollary 2. LF(C;):V*Val     C 6 V * D o m C 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)emptiness of the languagesabove we obtain following conditions:

Theorem 2. a,)LF(C6) * A for any C6
           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 gives Sw e LF(C;).
c ) E v i d e n tl y Va I C 6 -V* D o m C 6V * c D D (C I). On the other si dei f w e D D (C 6),
then trr € (V - Dom Cu)*, and u,' : lDruu2 f.or some u e Val Ca. This gives
u e Va l C u- V" D o m C 6 V * .
Points b) and d) foilow directly from the Theorem 2.                                          n

Corollary          3. a) LF(C6) i,s infi,nite for any C6.
                      b) If DD(Cb) l0 tlrcn it i,s infi'nite.

Proof. a) For the string ^9tufrom the proof of Theorem 2 we have S+w C LF(Cb).
b) For u € DD(C6) we have also u* e DD(C).

I'{ote2. Nonempty GE(C6) and nonempty M(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 ) : { ( 1 , 1 , 0 ,1 ) ,( 1 , 1 , 1 , 0 )(, 1 ,1 , 1 , 1 ) ,( 1 , 1 , 0 , 0 ) ,
                                  ( 0 ,1 , 1 , 1 ) (, 0 ,1 , 1 , 0 ) ,( 0 ,1 , 0 ,1 ) ,( 0 ,1 , 0 , 0 ) i .

Proof. By Coroilary 1 and Theorem 2 we have
      y ( C O L 6 ) C { ( 1 , 1 , 0 ,1 ) ,( 1 , 1 , 1 , 0 )(, 1 , 1 ,1 , 1 ) ,( 1 , 1 , 0 , 0 ) (, 0 ,1 , 1 , 1 ) ,
                           ( 0 ,1 , 1 , 0 ) ,( 0 ,1 , 0 ,1 ) ,( 0 ,1 , 0 , 0 ) ) .
All these vectors can be reached.
x ( c o ) : ( 1 , 1 , 0 , 1 ) f o r C 1w , i t h R : { ( o , { b , c b } ) ,( b ,{ r } ) , ( d , { o } ) , } a n d
      d + c G E (C ;), a t c L F (C ),                     D D (C a) : A , c* C N L(C ).
194      A. Kelemenovd
                    andA. Koiani



X G a ) : ( 1 , 1 , 1 , 0 ) f o r C 6w i t h R : { ( o , { b , d . } ) ,( b ,{ o } ) , ( . , { o } ) } a n d
   c+ c GE(C;), b* c LF(C;), d* c DD(C;), M(Cb) - A.

x p a ) : ( 1 , 1 , 1 , 1 ) f o r C ow i r h R : { ( a , { b b } ), ( b ,{ c e } ) } a n d
     a * c G E (C ;), (b b )+ c L F ( C ), (r" )* c D D (C ;), c* c IIL(C ;).

X ( C a ): ( 1 , 1 , 0 , 0 ) f o r C 6w i t h R : { ( o , { b b } ) ,( b ,{ " } , ( c , { b } ) } a n d
     a * c GE (C ;), (b b )+ c L F (C ), D D (C ) : A , N L(C ) : A .

X (C a ): (0 , 1 , 1 , 1 ) fo r C 6 w i th R : {(o, {b,,cc}),(b, {o,cc})} and
    GE (C I) : A , a t c L F (C I) , cc* c D D (cb), c € Iv L(C b).

X ( C a ): ( 0 , 1 , 1 , 0 ) f o r C 6w i t h R : { ( o , { b } ) , ( b ,{ o , c } ) i a n d
     GE(Cb):$,               a* c LF(cb), c* c DD(cb), IvL(Cb):A.

X G u ) - ( 0 , 1 , 0 , 1 ) f o r C 6w i t h R : { ( o , ,{ b , c b } ) ,( b ,{ o } ) } a n d
   GE (C b ) : A , a + c L F (C I) , c* c IV L(C 6), D D (C I) - 0.

X ( C a ): ( 0 , 1 , 0 , 0 ) f o r C 6 w i t h R : { ( r r ,{ b } ) , ( b ,{ o } ) } a n d
     {o,b}* : LF(Ca) and all the other sets are empty.                                                               tr


3.2      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).

Definition4. LetC - (V.,T,R)beacolony andR-                                               i(S,f)       lS      e V,F C
(V - {S}).,Ffin'ite, F +0}. Then

       r 1A          i,ffr: r1Sr2Srz...r*Sfrrntr, rrz2...rm.*r e (V - {,5}).,
                         a :    !XyW1I2IX2T3. . . ImUrnTrn*l               t

                         forsome (S,lr)€Rand                       ujef',       1< j<m.

We denote by Ct the rewriting system determined by the colony C : (V,T,R)
an d b y th e d e ri v a ti o n s te p i ;, i .e. C 1 : (V * ,R ,+ ) and w e denote by C OLI
the collection of all rewriting systemsC1.
To express languagesof environmerrt for C1we have directly from the definition:

Le m m a 3 . AL i u e (C t): V* D o m C tV *
             D e a d (C 1 ): (V - Dom C 1)*
             Reo.chable(Ct)U            : ceRV - Dom c)*Val c (V - Dom c)".
             ( J n r e a c h a b l e ( C 1 ) : V *- U c e R V - D o m c ) - V a l c ( V - D o ' m c ) * .

Note that C6 and Ct differs in the sets .Reachableand Unreachable but not in
Aliue and Dead.
                                                            Structures
                                                                     of theEnvironrnent
                                                                                      in Colonies                             195


T h e o re m 4 . L F (C I) :                        -D om c)* V al c (V -D om c). n V " D om C tV *
                                         U " .,. (V
                 GE (C t) -              V" D o m C tV * - U " .o(V - D om c)* V al c (V - D om c)*
                 DD(Ct) :                ( V - D o m C 1 ) " ( V a lC t - V " D o m C 1 V " ) ( V - D o m C 1 ) *
                 IIL(Ct) -               (V-DornCt)** [J"ea(V-Domc)" Val c(V-Domc)"

Proof. It follows from Lernma 3 and definitions.                                                                                 tr

T h e o re m 5 . o ) GE (C I) + A for any C 1.
                         b) LF(C;)+ 0 ''tr lDomCtl > 2
                         c) DD(C1)+ A tff (Val C1- V"Dom CtV")+ 0
                         d) I{ L(Ct)+ 0 iff (V - Dom Cr)"- V*Val Cy. + A
P r o o f. a ) L e t D o m C 1- { 5 1 , . . . , ^9" } . Then (S r 52... S ,)+ C GE (C I). It fol i ow s
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
( . S r)* c L F (C t).
Let Dom q:            {S}. Then words containing ,S cannot be derived and words not
containing ,9 do not produce any word. Therefore LF(C1) : A.
Points c) and d) follow from definitions.                                                           tr

Corollary          4.
                          'i#i;)t?,'\ff\':,'ffi;
                          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

IVote 3. 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 ) ,( 1 , 0 ,1 , 1 ) ,( 1 , 1 ,1 , 1 ) ,( 1 , 1 , 0 , 0 ) ,
                                      ( 1 ,1 , 0 ,1 ) ,( 1 ,1 , 1 , 0 ) i .

Proof. By Corollary 1 and Theorem 5 we have
     x ( C O L t ) q { ( 1 , 0 ,1 , 0 ) ,( 1 , 0 ,1 , 1 ) ,( 1 , 1 , 1 ,1 ) ,( 1 , 1 , 0 , 0 ) (, 1 , 1 , 0 ,1 ) ,( 1 , 1 , 1 , 0 )} .
All these vectors can be reached.
X ( C t ) : ( 1 , 0 ,1 , 0 ) f o r C l w i t h R : { ( a , { b } ) } a n d
     GE(C.): {a,b}+ -6+,                      LF'(C; -A,             DD(C):b*,                     IVL(C):A.

X Q t) : (1 , 0 , 1 , 1 ) fo r C 7w i th 7 ? : { (o, { b, ccc})} and
    {o, b}* - b+ c GE(CI), LF(CI) :0,                       b+ c DD(C),                             {r,cc} c I{ L(C).

X G t ) : ( 1 , 1 , 1 , 1 ) f o r C 7w i t h R . : { ( a , { b , b d d } ) ,( b ,{ " } ) } a n d
    a + c GE (C 1 ), b + c L I-(C ),               c* c D D (C ),                d+ c I,{ L(C ).

r q r ) : ( 1 , 1 , 0 , 0 ) f o r C l w i t h R : { ( o , { b } ) , ( b ,{ o } ) } a n d
      G E ( C t ) : { a , b } * - c r *- b * ,   LF(Ct) : a*ub+, DD(Ct) : 0, N L(C) : A.
196     A. Kelemenovd
                   andA. Koiani



X ( C t ) : ( 1 , 1 , 0 , 1 ) f o r C 7w i t h R : { ( o , { b , b c . c } )(,b ,{ o } ) } a n d
     ( a b 1 +c G E ( C I ) , b + c L F ( C I ) , D D ( C I ) : 0 ,                  c* c M(Ct).

x ( C t ) : ( 1 , 1 , 1 , 0 ) f o r C t w i t h R : { ( o , { b } ) , ( b ,{ r } ) } a n d
     a * c G E (C t), b + c L F (C I), c* c D D (C ),                               l { L(C t) : A .   !


4      Conclusions
Structures of the environment of the b-mode colonies and l-mode colonies differ
in some aspects. According to the presented results we have
    I) LF(Cb) is infinite for every Ca and 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 languages are
infinite, while nonempty l,l L(Cb) can be either finite or infinite.
    3) The set of characteristic vectors of COLb consists of 9 vectors, while the
set of characteristic vectors of COLt consists of 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.


References
 1. Csuhaj-Varjri, E.: Colonies - a multi-agent approach to language generation. Irr:
     Proc. ECAI'96 Workshop on Fini,te State Mctdels of Language, (A.Kornai, ed.),
    NJSZT, Budapest, 1996, 12*16
 2. Csulraj-Varjf, E., Dassow, J., I{elemen, J., PXurr. Gh.: Grammar Systems - A
     Gramtnatical Approach to Distribution and Cooperation. Gordon and Breach,
    London, 199,1
 3. Csulraj-Varjri, E., Keiernettov6, A.: Languages of Colonies. Theoretical Computer
    S c i e n c e1 3 . 1( 1 9 9 4 ) 1 i 9 - 1 3 0
 4. Dassorv,J., P5,un,Gh., Rozenberg,G.: Grammar systems.In; Handbook of Formal
    Languages, vol. 2 (G.Rozenberg and A. Salomaa, eds.) Springer-Verlag, Berlin,
     1997, 155-274
 5. I(elemetr, .I., Kelemenovd,,A.: A grammar-t,heoretic treat,ment of multiagent, sys-
    tems. Cybernetics and Systems 23 (IggZ) 621-633
 6. Kelemenovd,, A., Kelemen, J.: From colonies to eco(grammar) systems. In:
    Proc. Impor-tant results and trends in theoretico.lcomputer science, (J. Karhumdki,
    H. Nlaurer, G. Rozenberg,eds.), L|{CS 812, Springer-Verlag,Berlin, Lgg4,zl}-2}l
 7. Koiany, A.: Structural properties of PI\"I colonies. In:Mathematical and Engineer-
     ing L,Iethods in Computer Science Pre-procee.riings,Brno, 2005, 11-i6
 8. KoZan-. ,\.; Struktur6lni vlastnosti kolonif s f mod derivacf. In: Kognice a umely
    zit'ot VL Sestavili J. I{elemetr, V. Kvasnicka, Slezskd univerzita v Opavd, 2006,
    223-227
 9. IVlartirr-Vide, C., Pdurt, Gh.: Plvl-colonies. Computers and Artificial Intelligence 17
    ( 1 9 9 8 )5 5 3 - 5 8 2
10. Nlartfn-Vide, C., Piun, Gh.: New topics in colonies theory. Grammars I (1999)
    209-323