This paper presents the second part of the tech- number of terminals on the tape. We mainly focus on nical report [7] in which the study of the relation between deterministic restarting automata in order to ensure Parallel Communicating Grammar Systems (PCGS) and the correctness preserving property for the analysis, Freely Rewriting Restarting Automata (FRR) has been ini- i.e., after any restart in an accepting computation the tiated. The rst part of [7] is presented in [6]. Here, the content of the tape is a word from the characteristic distribution and generation complexity for PCGS are intro- language. In fact, we mainly consider strongly lexicadPuCcGedS awnidthstduisdtireidb.uIttioins schoomwpnletxhiatyt abnoualnydseisd bbyyraedcuocntsitoannftokr lized restarting automata. This additional restriction and generation complexity bounded by some other constant requires that all rewrite operations are deletions. j can be implemented by strongly linearized deterministic Parallel Communicating Grammar Systems are able FRR-automata with k rewrites per cycle. We show in nite to handle creations of copies of generated strings and hierarchies of classes of languages based on the parameters their regular mappings in a natural way. This ability k; j and on the notion of skeleton. strongly resembles the generation of coordinations in Czech (and some other natural languages) sentences, where coordinations are certain contiguous segments 1 Introduction (not only lexicalized elements). However, the synonymy of coordinations has not yet been modelled appropriately. In this paper the notions of distribution and generation complexity for PCGS are introduced and studied. It is shown that analysis by reduction for PCGS with distribution complexity bounded by a constant k and generation complexity bounded by some other constant j can be implemented by strongly linearized deterministic FRR-automata with k rewrites per cycle. We show in nite hierarchies of classes of languages based on the parameters k; j and on the notion of skeleton. The notion of skeleton is introduced in order to model the principle of so-called segments in (Czech) sentences (or in text). The elements of skeletons are so-called islands, which serve to model the so-called separators of segments (see [3]).
are used as markers for the left and right end of the In recent papers restarting automata were mainly workspace, respectively. They cannot be removed from used as acceptors. The (input ) language accepted by a the tape. The behavior of M is described by a transi- restarting automaton M is the set L(M ) := LC(M ) \ tion function ± that associates transition steps to cer- §¤. Here, motivated by linguistic considerations to tain pairs of the form (q; u) consisting of a state q and model the analysis by reduction with parallel processa possible content u of the read/write window. There ing, we are rather interested in the so-called proper are four types of transition steps: move-right steps, language of M , which is the set of words LP(M ) := rewrite steps, restart steps, and accept steps. A move- Pr§ (LC(M )): Hence, a word v 2 §¤ belongs to LP(M ) right step simply shifts the read/write window one po- if and only if there exists an expanded version u of v sition to the right and changes the internal state. A such that u 2 LC(M ). rewrite step causes M to replace a non-empty pre x u For each type X of restarting automata, we use of the content of the read/write window by a shorter LC(X) and LP(X) to denote the class of all characterword v, thereby shortening the length of the tape, and istic languages and the class of all proper languages of to change the state. Further, the read/write window automata of this type. is placed immediately to the right of the string v. A Following basic properties of FRR-automata are ofrestart step causes M to place its read/write window ten used in proofs. over the left end of the tape, so that the rst symbol (Correctness Preserving Property.) Each deterit sees is the left sentinel c, and to reenter the initial ministic FRR-automaton M is correctness preserving, state q0. Finally, an accept step simply causes M to halt and accept. i.e., if u 2 LC(M ) and u `cM¤ v, then v 2 LC(M ), too.
A con guration of M is described by a string ®q¯, where q 2 Q, and either ® = " (the empty word) and ¯ 2 fcg¢¡ ¤ ¢f$g or ® 2 fcg¢¡ ¤ and ¯ 2 ¡ ¤ ¢f$g; here q represents the current state, ®¯ is the current content of the tape, and it is understood that the window contains the rst k symbols of ¯ or all of ¯ when j¯j · k.
A restarting con guration is of the form q0cw$, where w 2 ¡ ¤. (Cycle Pumping Lemma.) For any FRR-automaton M , there exists a constant p such that the following property holds. Assume that uxvyz `cM ux0vy0z is a cycle of M , where u = u1u2 ¢ ¢ ¢ un for some non-empty words u1; : : : ; un and an integer n > p. Then there exist r; s 2 N+, 1 · r < s · n, such that u1 ¢ ¢ ¢ ur¡1(ur ¢ ¢ ¢ us¡1)ius ¢ ¢ ¢ unxvyz `cM
u1 ¢ ¢ ¢ ur¡1(ur ¢ ¢ ¢ us¡1)ius ¢ ¢ ¢ unx0vy0z holds for all i ¸ 0, that is, ur ¢ ¢ ¢ us¡1 is a pumping factor in the above cycle. Similarly, such a pumping factor can be found in any factorization of length greater than p of v or z as well as in any factorization of length greater than p of a word accepted in a tail computation.
computation which starts from the restarting con guration q0cw$, and ends with an application of an accept step. By LC(M ) we denote the language consisting of all words accepted by M . It is the characteristic language of M .
Any computation of M consists of certain phases.
A phase, called a cycle, starts in a restarting con
guration. The window is shifted along the tape by
moveright and rewrite operations until a restart operation
is performed and thus a new restarting con guration is
reached. If no further restart operation is performed,
the computation necessarily nishes in a halting con- We focus our attention on FRR-automata, for which
guration such a phase is called a tail. It is required the use of auxiliary symbols is less restricted than
that in each cycle M performs at least one rewrite in [
By Pr§ we denote the projection from ¡ ¤ onto §¤, Corollary 1. If M is a linearized FRR-automaton, that is, Pr§ is the morphism de ned by a 7! a (a 2 §) then the proper language LP(M ) is context-sensitive. and A 7! " (A 2 ¡ r §). If v := Pr§ (w), then v is the §-projection of w, and w is an expanded version of v. In what follows we are mainly interested in strongly For a language L µ ¡ ¤, Pr§ (L) := f Pr§ (w) j w 2 L g. linearized FRR-automata and their proper languages. We denote by (S)LnRR the class of (strongly) linearized i · m. If any of the components is a terminal string, deterministic FRR-automata, by N(S)LnRR the class of it is left unchanged. If any of the component grammars non-deterministic (strongly) linearized FRR-automata, contains a nonterminal that cannot be rewritten, the and by t-A the subclass of A-automata which execute derivation is blocked. If the rst grammar G1 contains at most t rewrite steps in any cycle. a terminal word w, the derivation nishes and w is the word generated by ¦ in this derivation. 2.1 Parallel Communicating Grammar If a communication symbol is present in any of Systems the components, then a communication step is performed. It consists of replacing those communication A PCGS of degree m, m ¸ 1, is an (m + 1)-tuple symbols with the phrases they refer to for which the ¦ = (G1; : : : ; Gm; K), where for all i 2 f1; : : : ; mg, phrases do not contain communication symbols. Such Gi = (Ni; T; Si; Pi), so-called component grammars, an individual replacement is called a communication. are regular grammars satisfying Ni \ T = ; and K µ Obviously, in one communication step at most m ¡ 1 fQ1; : : : ; Qmg T Sim=1 Ni is a set of special symbols, communications can be performed. If some communicalled communication symbols. cation symbol was not replaced in this communication A con guration is an m-tuple C = (x1; : : : ; xm); xi = step, it may be replaced in one of the next communi®iAi; ®i 2 T ¤; Ai 2 (Ni [ "); we call xi the i-th com- cation steps. Communication steps are performed unponent of the con guration (resp. component). The til no more communication symbols are present or the nonterminal cut of con guration C is the m¡tuple derivation is blocked, because no communication symN (C) = (A1; A2; : : : ; Am). If the nonterminal cut N (C) bol can be replaced in the last communication step. contains at least one communication symbol, it is de- The (terminal) language L(¦) generated by a PCGS noted N C(C) and called an NC-cut. ¦ is a set of the terminal words generated by G1 (in
We say that a con guration X = (x1; : : : ; xm) di- cooperation with the other grammars): rectly derives a con guration Y = (y1; : : : ; ym), and write X ) Y , if Y is derived from X by one gener- L(¦) = f ® 2 T ¤j (S1; : : : ; Sm) )+ (®; ¯2; : : : ; ¯m) g: ative or communication step (see below). Informally, in a communication step any occurrence of a communication symbol Qi in X is substituted by the i-th component of X (assuming that this component does not contain any communication symbol).
Let D = D(w) = C0; C1; : : : ; Ct be a derivation of w by ¦; D(w); ¦ and w are xed in what follows.
With derivation D(w), several notions can be associated which help to analyze the derivation of ¦ and to unambiguously determine w.
The trace of a (sub)derivation D is the sequence T (D) = N (C0)N (C1) : : : N (Ct) of the nonterminal cuts of the individual con gurations of D. 1. (Generative step) If jxijK = 0 for all i , 1 · i · m, then xi )Giyi for xi 2 T ¤Ni and yi = xi for xi 2 T +. The NC-sequence is de ned analogously; N CS(D) is 2. (Communication step) If jxijK > 0 for some i, the sequence of the NC-cuts of the con gurations in 1 · i · m, then for each k such that xk = zkQjk , the (sub)derivation D. Let us recall that any NC-cut zk 2 T ¤; Qjk 2 K, the following is true: contains at least one communication symbol. (a) if jxjk jK = 0, then yk = zkxjk and yjk = Sjk ; (b) if jxjk jK = 1, then yk = xk.
Now, we describe the derivations in PCGSs. A derivation of a PCGS ¦ is a sequence of con gurations D = C1; C2; : : : ; Ct, where Ci ) Ci+1 in ¦. If the rst component of Ct is a terminal word w, then we usually write D(w) instead of D. Analogously, we denote by W (D) the terminal word generated within the derivation D. Every derivation can be viewed as a sequence of generative and communication steps, too.
If no communication symbol appears in any of the component grammars, then we perform a generative step consisting of rewriting steps synchronously performed in each of the component grammars Gi; 1 · A cycle in a derivation is a subsequence N (C); N (C1); : : : ; N (Cj ); N (C) of nonterminal cuts of the derivation4 in which the rst and the last cuts (N (C)) are the same. If N (C) is an NC-cut, and none of the intermediate cuts N (Ci) is an NC-cut, then the cycle is called a communication cycle. A generative cycle is de ned analogously, we only require that none of its cuts is an NC-cut.
Note that, if there is a cycle in the derivation D(w), then manifold repetition of the cycle is possible and the resulting derivation is again a derivation of some terminal word. We call a derivation D(w) reduced, if each repetition of each of its cycles leads to a longer terminal word !; jwj < j!j. Obviously, to every derivation D(w) there is an equivalent reduced derivation
tion.
CS(D(w)) = (i1; j1; l1), (i2; j2; l2) ; : : : ; (ir; jr; lr); where w = g(i1; j1; l1); g(i2; j2; l2) : : : g(ir; jr; lr). The set of these indices is denoted I(D(w)). g(i; j) (g(i; j; D(w))) denotes the terminal part generated by Gi within the j-th generative section of D(w), we call it the (i; j)-(generative) factor (of
D(w)); n(i; j) (n(i; j; D(w))) denotes the number of occur
rences of g(i; j) in w; Fact 2 Let ¦ be a PCGS without a communication
g(i; j; l) denotes the l-th occurrence of g(i; j) in w, we cycle, D(w) a reduced derivation of a terminal word w.
call it the (i; j; l)-(generative) factor. Then there is a constant e(¦) such that, if more than
e(¦) generative steps of one generative section are
performed, then at least one g(i; j; D(w)) is changed
(see Example 1 in [
ery reduced derivation D(w) is bounded by `(¦); 3. the cardinality of the set of possible communication structures corresponding to reduced derivations by ¦ is bounded by s(¦). 3
N(j; D(w)) = §i n(i; j; D(w)), where the sum is taken over such i for which 9s : i = is & (is; js; ls) 2 I(D(w)).
tribution complexity and generation complexity. First, the distribution complexity of a derivation D (denoted DD(D)) is the degree of distribution introduced above.
Then, the distribution complexity of a language and the associated complexity class are de ned in the usual way (always considering the corresponding maximum): distribution complexity of a derivation à distribution complexity of a word à distribution complexity of a language L (denoted DD(L)) as a function of the length of the word à f (n) ¡ DD as class of languages whose distribution complexity is bounded by f (n).
The generation complexity is introduced analogously. Here, we are mainly interested in the classes of languages with t-DD and/or with j-DG for some natural numbers j; t. We denote by j-t-DDG the class of languages such that, to any language L of this class, there is a PCGS ¦ such that L(¦) = L, and DD(L(¦)) = t, DG(L(¦)) = j. (A1; : : : ; Am); (®1;1A1;1; : : : ; ®1;mA1;m); : : :
(®1;1®2;1 : : : ®s;1As;1; : : : ; ®1;m®2;m : : : ®s;mAs;m) the sub-derivation corresponding to this generative section. Merging the description of this sub-derivation into g(i; j; l) we obtain the extended version of g(i; j; l):
than one communication symbol, then there might be no generative step between two communication steps. : : : ®s;i µ As;1 ¶
As;2 A¢s¢;m¢ [e; i; j; l]: Such a description of g(i; j; l) is denoted ex-g(i; j; l). )¤ (c1wdc2wd : : : ctwd; S2; : : : ; St; St+1): mWaetiuosne aebxo-ugt(i;dje;rli)vattoiomneDrg(ew)thineto(towp.oOlobgviciaolu)sliyn,fowre- niquFeorast hine [l4o]w.er-bound part we use a similar techsccgila(meins;Lijslia;enplrte)ldaywiekn;raiDaswvba(wbotweiuyo)ts;nepetxsrxe.-aag-cgk(e(is;ia;jbaj;no;l)dul);t,ftahtbcreeatorcaeressscuayalbtcnolidevssegd.ieenRnneeeorxptae-ltagdic(veiee;xja-c;nwyly)-. itssut¡micL1eleittnrheeMawatrriLi=ztPeeds((MQFp;Re)§rR=;-c¡ayLu;ctctleo;h,$mo;lwadqt0hso;.enkCre;ot±hn§)asbtid:ee=exraet§cnhuo0etnew[dsoe§artdte1r.mwmAoi:ns=st-coTobhmteanmin,uctnohicneac¦taito-endneassttcrirnuigcpttuitohrnee goNifvCewn-s:ebqyuDen(cwe),oafnDd (ewx)-w,twhee scvTu1eharceshnnibotnnhtdhaoe¢tfr¢We¢wcet2xaininsLbtLnsCdC(aM(n2M)e.L)x.Lpt,eaCtnwodWnhesedirbdeveerenarassiinshoonaarctWlceaesrptg2teeixn¡ipgn¤atcneoogdfmeewrd-. ¦d(D(w)) = N CS(D(w))CS(D(w))ex-w: putation of M on input W . Clearly this cannot just be an accepting tail, and hence, it begins with a cycle Observations. Let ¦d(D(w)) be the ¦-description of the form W `cM W1. From the Correctness Preof w. serving Property it follows that W1 2 LC(M ), which implies that w1 := Pr§(W1) 2 Lt. As jW1j < jW j, (a) When a reduced derivation D(w) is taken, then we see from our choice of W that w1 6= w, that is, the length of ¦d(D(w)) is bounded from above w1 = c1x1d ¢ ¢ ¢ ctx1d for some word x1 2 §0¤ of length by c¦ ¢ jwj + c¦ , where c¦ is a constant depending jx1j < 2n. However, in the above cycle M executes on ¦ only. at most t ¡ 1 rewrite steps, that is, it cannot possi(b) From ¦d(D(w)) the terminal word w is easily ob- bly rewrite each of the t occurrences of anbn into the tained by deleting all symbols which are not ter- same word x1. It follows that w1 62 Lt, implying that minal symbols of ¦. Lt 62 LP((t ¡ 1)-NLnRR). 2 (c) Let T (D(w)) be the trace of D(w), and T (¦) := fT (D(w)) j w 2 L(¦)g. Then, T (¦) is a regular As L(t-DD) µ LP(t-SLnRR), we obtain the followlanguage, and the sets of NC-cuts and communi- ing hierarchies from Proposition 1, where LP(t-DD) cation sequences of ¦ are nite. Note that a nite just denotes the class L(t-DD). automaton is also able to check whether a given Theorem 1. For all X 2 fDD; LnRR; SLnRR; NLnRR, string x is a correct ex-g(i; j; l), N CS(D(w)), or NSLnRRg, and all t ¸ 1, CS(D(w)) given by ¦.
Analyzing the proof of Theorem 1 from [
LP(t-X) ½ LP((t + 1)-X) ½ [ LP(t-X) ½ LP(X):
t¸1
Corollary 2. For all k 2 N, k-DD µ LP(k-SLnRR). lands whose introduction has been motivated by our attempt to model two basic kinds of coordinated seg
For t 2 N+, separation of PCGSs of distribution ments in (Czech, German, Slovak) sentences. The
iscomplexity t from the proper languages of nondeter- lands in a level of skeleton serve to denote places of
ministic linearized FRR-automata with at most t ¡ 1 coordinated segments which are coordinated in a
murewrites per cycle, is done with the help of the lan- tually dependent (bound) way. The di erent levels of
guage islands serve for modelling the independence of
segLt := f c1wd ¢ ¢ ¢ ctwd j w 2 fa; bg¤ g; ments. A technical example how to construct skeletons
is given by the construction in the proof of [
Let SK(s) = f ci;j j 1 · i · t; 1 · j · s g be a Proof. It is not hard to show that Lt 2 L(t-DD). We subalphabet of cardinality t ¢ s of ¡ 0 = ¡ [ fc; $g. For use a PCGS with t + 1 component grammars for that: each j 2 f1; : : : ; sg, let SK(s; j) = fc1;j; : : : ; ct;jg be (S1; S2; : : : ; St+1) )¤ the j-th level of SK(s). We say that SK(s) is an s)¤ (c1Q2; c2Q3; : : : ; ctQt+1; wd) skeleton (skeleton) of M if the following holds: The elements of SK(s) are called islands of M . We say that SK(s) is a left skeleton of M , if M executes rewrite operations only with an island in the leftmost position of its window. 1. For all w 2 LC(M ) and all c 2 SK(s), jwjc · 1, Proposition 2. For all s; t 2 N+, that is, w contains at most one occurrence of c. 2. Each rewrite operation of M deletes a single con- (a) L(t;s) 2 L(s-t-DDG), tinuous factor from the actual contents of the win- (b) L(t;s) 2= LP(t-SK(s ¡ 1)) for s > 1, and dow, and at that point the window must contain (c) L(t;s) 2= LP((t ¡ 1)-SK(s)) for t > 1. exactly one occurrence of a symbol from SK(s).
This symbol is either in the rst or in the last po- Sketch of the proof. Note that Lt = L(t) = L(t;1) sition of the window. when j§1j = ¢ ¢ ¢ = j§tj = j¢j = 1. 3. If a cycle C of M contains a rewrite operation (a) For the upper-bound part we use a PCGS with during which a symbol ci;j 2 S(s; j) is in the rst (t+s) component grammars, which realize s phases or last position of the window, then every rewrite corresponding to s generative sections. The group of operation during C is executed with some element grammars Gs+1; : : : ; Gs+t plays the role of G2; : : : ; of S(s; j) in the rst or last position of the window. Gt+1 from the proof of Proposition 1, while the compo4. If w 2 LC(M ), w = xyz, such that jyj > k, and y nent grammars G1; : : : ; Gs play the role of grammar does not contain any element of SK(s), then start- G1 from that proof. At the end of the p-th generaing from the restarting con guration corresponding tive section, there is a word !pi present in component to w, M will execute at least one cycle before it ac- grammar Gs+1, where !p = c1;pwpdp : : : ct;pwpdp is a cepts. terminal word and i; 1 · i · s; is a nonterminal symbol indicating that Gi is the grammar into which !p should be communicated. Finally, the synchronized communication concatenates all !’s in an appropriate6 way in component grammar G1.
Thus, in each cycle M performs up to t rewrite (b) Assume that M is a t-SK(s ¡ 1)-automaton such (that is, delete) operations, and during each of these that LP(M ) = L(t;s). Thus, M has a (s ¡ 1)-skeleton operations a di erent island ci;j of the same level SK(j) SK(s ¡ 1) = f ci;j j 1 · i · t; 1 · j · s ¡ 1 g. is inside the window. As there are s such levels, we see Now assume that, for i = 1; : : : ; s, wi 2 Lt;i, that that there are essentially just s di erent ways to per- is, w := w1w2 ¢ ¢ ¢ ws 2 L(t;s). Further, let W be an form the rewrite steps of a cycle. expanded version of w. For each cycle of M in an ac
By LP(t-SK(s)) (resp. by LP(t-LSK(s))) we denote cepting computation on input W , there exists an inthe class of proper languages of t-SLnRR-automata dex j 2 f1; : : : ; s ¡ 1g such that each rewrite step of with s-skeletons (resp. with left s-skeletons). The cor- this cycle is executed with an island ci;j in the leftresponding classes of characteristic languages are de- or rightmost position of the window. From the proof noted by LC(t-SK(s)) (resp. by LC(t-LSK(s))). of Proposition 1 we see that, for each of the factors
Observe that the symbols of the form [b; i; s; l] in Lt;j , t rewrite steps per cycle are required. Thus, each the construction of an s-SLnRR-automaton M accept- of the factors Wi must contain t islands, that is, W ing the language LC (M ) = f ¦d(D(w)) j w 2 L(¦) g must contain at least t ¢ s islands. However, as the play the role of islands for M , and their complete set word W 2 LC(M ) contains at most a single occuris a left skeleton for M . This observation serves as rence of each symbol of the set SK(s ¡ 1), and as the basis for the proof of the next corollary. Recall jSK(s¡1)j = t¢(s¡1), W can contain at most t¢(s¡1) that s-t-DDG denotes the class of PCGSs that have islands. This contradicts the observation above, imsimultaneously generation degree s and distribution plying that L(t;s) is not the proper language of any degree t. t-SK(s ¡ 1)-automaton. (c) For the lower-bound part recall Proposition 1 Corollary 3. where Lt 62 LP((t ¡ 1)-NLnRR) is shown to hold. From For all s; t 2 N+, L(s-t-DDG) µ LP(t-LSK(s)): the proof it follows that L(t;s) 62 LP((t ¡ 1)-NLnRR).
To separate PCGSs of generation complexity t and As (t ¡ 1)-SK(s)-automata are a special type of (t ¡ 1)distribution complexity s from the class of proper lan- SLnRR-automata, the non-inclusion result in (c) folguages of (t ¡ 1)-LSK(s)-automata we de ne language lows. 2 L(t;s). This language is based on a kind of bounded Next we consider the language Lpe := f wcwR j concatenation of Lt. For s; t 2 N+ and i · s, let w 2 f0; 1g¤ g. By taking the symbol c as an island, we L(t) := f c1wd ¢ ¢ ¢ ctwd j w 2 fa; bg¤; ci 2 §i; d 2 ¢ g; easily obtain the following result. where §1; : : : §s; ¢ are new alphabets with empty intersection with fa; bg. Then,
L(t;s) := (L(t))s:
ism. In case of wrong nondeterministic choices the derivation is blocked.
On the other hand, this language cannot be ac- The study of the relation between PCGS and FRR was
cepted if we restrict our attention to left skeletons. motivated by computational linguistics; both models
seem to be useful in this eld. While in [
we have the following proper inclusions: