Complexity Results for Szilard Languages of PC Grammar

The notion of Szilard language (Definition7.5) of a PC grammar system was introduced in [150] in order to keep control of derivations in PC grammar systems and to measure the amount of work, cooperation, and communication performed by the components of the system. The main objective in [150] was to study properties and relations between classes of Szilard languages associated with several kind of PC grammar systems. Below we recall, from [150], only some of the most important results for our considerations.

Theorem 7.18. For any class Y of grammars and any r ≥1 we have 1. SZ(CP C_rY)⊆SZ(P C_rY),SZ(N CP C_rY)⊆SZ(N P C_rY), 2. SZ(XrY)⊆SZ(Xr+1Y), for anyX ∈ {CP C, N P C, N CP C, P C}.

3. SZ(X_rY₁) ⊆SZ(X_rY₂), for any X ∈ {CP C, N P C, N CP C, P C}, and any Y₁, Y₂ ∈ {REG, LIN, CF} such thatL(Y₁)⊆L(Y₂).

4. REG⊂SZ(CP C2REG)⊂CF L, SZ(P C2REG)⊆CF L.

5. SZ(X_rREG)⊆L(X_rREG), X ∈ {CP C, N P C, N CP C, P C}.

Chapter 7. Grammar Systems

6. SZ(XrLIN)⊆L(XrLIN),X ∈ {CP C, N P C, N CP C, P C}.

7. SZ(CP C_rREG)⊂L(CP C_r+1REG) (i.e., an infinite hierarchy).

The aim of this subsection is to study the complexity of Szilard languages associated with derivations in PC grammar systems in terms of parallel computation. To do so we simulate several classes of PC grammar systems by alternating Turing machines (ATMs) and then we relate them to N C¹ and N C² circuit complexity classes. We consider only PC grammar systems with context-free components.

Recall that for a PC grammar system Γ = (N, K, T, G1, . . . , Gr), each component is of the form G_i = (N ∪K, T, P_i, S_i) where |P_i| = c_i, 1 ≤ i ≤ r, N = {A₁, ..., A_m} is the ordered finite set of nonterminals, and K ={Q₁, . . . , Qr} is the finite set of query symbols. To label the productions of the components, we use the following labeling procedure. Each rule p ∈ P₁ is labeled by a unique label p_q, 1 ≤ p_q ≤ c₁, and each p∈Pi, 2≤i≤r, is labeled by a unique labelpq, such thatPi−1

r=1cr+ 1≤pq≤Pi r=1cr. Denote byLab(Γ) the set of all labels introduced in this way, and byLab(G_i) the set of labels associated with rules inPi.

For any context-free rule p of the form αp → βp, αp ∈N, and βp ∈V_Γ^∗, whose label is p_q ∈Lab(Γ), thenet effect of rulepwith respect to each nonterminalA_l ∈N, 1≤l≤m, is given by dfA_l(pq) =|β_p|_Al− |α_p|_Al. To each rulep, we associate a vectorV(pq)∈Z^m defined by V(p_q) = (df_A1(p_q), df_A2(p_q), ..., df_Am(p_q)), where Zis the set of integers. The value of V(pq) taken at thel^th place, 1≤l≤m, is denoted byVl(pq) =VAl(pq).

Henceforth, if Γ = (N, K, T, G1, . . . , Gr) is a PC grammar system, a Szilard word γ ∈ SZ(Γ) is considered to be of the formγ =γ₁γ₂...γ_n, where eachγ_i∈Lab(Γ), 1≤i≤n, is the label of a context-free rule in∪^r_i=1Piof the formαγi →βγi,αγi ∈N, andβγi ∈V_Γ^∗. In the sequel, for the sake of simplicity, we use the same notation both for a rule and the label associated with it.

The Case of Centralized PC Grammar Systems

When Γ is a centralized PC grammar system, each Szilard word of a component G_i, i 6= 1, is composed of only labels in Lab(Gi). For returning centralized PC grammar systems we have [40,41]

Theorem 7.19. Each language L ∈ SZ(CP C_rCF) can be recognized by an indexing ATM in O(logn) time and space (SZ(CP C_rCF)⊆ALOGT IM E).

Proof. Let Γ = (N, K, T, G1, . . . , Gr) ∈ CP Cr(CF) and A an ATM composed of an input tape, an index tape, and a working tape divided into three blocks B₁, B₂, and B₃. Let γ ∈ Lab^∗(Γ), γ = γ1γ2...γn, be an input word of length n. At the beginning of the computation γ is stored on the input tape. The Pr

q=1cq vectors V(r_h) ∈ Z^m,

1 ≤h ≤ Pr

q=1cq are stored on B₁. As Pr

q=1cq is finite, the space used by A to store them is constant (with respect to the length of γ).

Level 1 (Existential) In an existential state A guesses the length of γ, i.e., writes on the index tapen, and checks whether then^th cell of the input tape contains a terminal symbol and the cell n+ 1 contains no symbol. The correct value of n is recorded in binary onB₂.

Level 2(Universal) Aspawnsn universal processes℘_i, 1≤i≤n.

I₁. On℘₁ Achecks whether γ₁ ∈Lab(G₁) andα_γ1 =S₁, while on ℘₂ Achecks whether i.) γ2 ∈ Lab(G1), |β_γ1|_K = 0, and |β_γ1|_αγ

2 ≥ 1 (rewriting step), or ii.) γ2 ∈ Lab(Gi), i 6= 1. For the latter case A searches forward in γ (Level 3-Existential) for the next label in Lab(G₁). Suppose this is γ_c+2. A checks whether β_γ1 is of the form β_γ1 = z1Qi1z2Qi2. . . zcQiczc+1, where z_l ∈ (N ∪T)^∗, 1 ≤ l ≤ c+ 1, γj+1 ∈ Lab(Gij) and α_γj+1 =S_ij, 1≤j ≤c (communication step in which each grammar interrogated byγ₁ performs only one rewriting step). Process ℘2 returns 1 if eitheri. orii.holds.

I2. On any process ℘q, such that γq−1 ∈ Lab(G1) and γq ∈ Lab(Gi), i 6= 1, i.e., on any ℘_q that takes a label γ_q placed at the beginning of a communicating Szilard string C,A searches forward (Level 3-Existential) for the label placed at the right edge of C. Suppose that γ_t is this label, i.e., C = γ_q...γ_t. As C is a communicating Szi-lard string, γq−1 must be a query rule of the form α_γq−1 → β_γq−1, α_γq−1 ∈ N and βγq−1 = z1Qi1z2Qi2. . . z_c⁰Qi_c0z_c⁰₊₁, where z_l ∈ (N ∪T)^∗, 1 ≤l ≤c⁰ + 1. For any Qij, 1 ≤j ≤c⁰, A searches backward in γ (Level 4-Existential) for the very last communi-cating Szilard string that contains a label inLab(Gij). Denote byC_ij this substring. A counts the number of labels inLab(G₁) occurring betweenC_ij andC, i.e., the number of rewriting steps performed byG1 between two consecutive communication steps in which G₁ interrogates G_ij. Suppose this number is g_ij ≥1. A guesses c⁰ positive integers `<sub>j</sub>, such that 1≤`_j ≤g_ij, 1≤j≤c⁰, and `<sub>1</sub>+...+`_c⁰ =t−q+ 1, where`_j is the length of the Szilard word³ generated by Gij betweenC_ij and C. To store them in binary, onB₃, Auses onlyO(logn) space (sincec⁰ is a constant that does not depend on the length of the input).

Levels 5−6 on℘_q (Universal-Universal)Aspawns (Level 5)c⁰ universal processes ¯℘_j, 1≤j≤c⁰, each of which checks whetherγ_q+^Pj−1

belongs toLab(Gij). ThenAspawns`j universal branches (Level 6). On the first branch Achecks whetherγ_q+^Pj−1 between two communication steps, as many derivation steps as the master grammar does, since the sentential form ofGi_j becomes a terminal string.

Chapter 7. Grammar Systems in the sentential form obtained at the h^th rewriting step in G_ij (obtained by summing up the net effect of rules in γ^(h)). A checks whether s^(h)_A

l > 0 for Al = αγ

q+Pj−1 i=0`i+h

(the nonterminal rewritten by γ_q+^Pj−1

i=0`i+h exists in the sentential form of G<sub>ij</sub>). For each j such that `j < gij, A checks whether s^(`_A^j−1)

l +V_Al(γ_q+^Pj

i=0`i−1) = 0, 1≤l≤ m (the sentential form ofG<sub>ij</sub> at the`^th_j rewriting step is a terminal string). Furthermore, when ever there exist two (or more) equal query symbolsQik andQil inβγq−1,Achecks

Ift=n (the rightmost label inC is at the end ofγ) then besides the above conditions, Achecks whethers^(`_A^j−1)

l +V_Al(γ_q+^Pj

i=0`i−1) = 0, for any 1≤j≤c⁰, 1≤l≤m, i.e., all strings that satisfy query symbols in βγq−1 are terminal.

I₃. Each ℘_q that takes a label γ_q such that γq−1, γ_q ∈ Lab(G_i), i 6= 1, i.e., γq−1γ_q is either a substring or a suffix of a communicating Szilard stringC, returns 1, without any further checking, since the correctness ofCis verified by the process that takes the label placed at the beginning ofC. Each℘_q that checks a label occurring in a communicating Szilard string is called plugged process. A plugged process always returns 1.

I₄. On any℘_q that takes a labelγ_q,γ_q∈Lab(G₁), considerγ^(q)=γ₁γ₂...γq−1. rewriting step, produced only by rules ofG₁.

• A counts the number of occurrences of each rule rji ∈ Pi, i 6= 1, 1 ≤ ji ≤ ci, in number of occurrences of each A_l, 1≤l≤m, left in the sentential form after all communication steps done by each G_i, 2≤i≤r, up to the q^th rewriting step in G1. The integer qi is the number of query rules occurring in γ^(q) that contain on the right-hand side at least oneQ_i (since Γ∈CP C_r(CF),G_i returns to its axiom after each communication step).

Process℘_q returns 1 ifPr

i=1s^(q,i)α_γq >0, i.e., the nonterminal rewritten byγ_q exists in the sentential form at theq^th step of derivation (after summing up the net effect of all rules occurring inγ^(q) with respect to nonterminal α_γq).

Concerning the last process ℘n, if γn ∈ Lab(G1), then besides the above conditions A also checks whether γ_n is not a query rule, and whether Pr

i=1s^(n,i)_A

l +V_Al(γ_n) = 0 for any Al, i.e., no nonterminal occurs in the sentential form at the end of derivation. If γ_n ∈ Lab(G_i), i 6= 1, then γ_n is the right edge of a last communicating Szilard string occurring in γ. Hence, ℘_n is a plugged process, and it returns 1 “by default”. The correctness of this last communicating Szilard stringC_nis checked by process℘_n⁰, where γ_n⁰ is the label placed at the left edge of C_n.

The computation tree ofAhas six levels, in which each vertex has unbounded out-degree.

By using a divide and conquer algorithm each of these levels can be converted into a binary tree of height O(logn). All functions used in the algorithm, such as counting and addition, are in N C¹, which is equal to ALOGT IM E under the U_E^∗-uniformity restriction [187]. To store and access the binary value of auxiliary computations, such as sums of net effects,AneedsO(logn) time and space. Hence, for the whole computation A usesO(logn) time and space.

Corollary 7.20. SZ(CP C_rCF)⊂ N C¹.

Proof. The claim is a direct consequence of Theorem 7.19and the results in [187]. The inclusion is strict since there exists L={pⁿ|n≥0} ∈ N C¹−SZ(CP CrCF)(CF).

Corollary 7.21. SZ(CP C_rCF)⊂DSP ACE(logn).

For non-returning centralized PC grammar systems we have [41]

Theorem 7.22. Each language L∈SZ(N CP C_rCF) can be recognized by an indexing ATM in O(logn) time and space (SZ(N CP CrCF)⊆ALOGT IM E).

Proof. Let Γ= (N, K, T, G1, . . . , Gr)∈N CP Cr(CF),Aan indexing ATM with the same configuration as in the proof of Theorem7.19, andγ ∈Lab^∗(Γ),γ =γ1γ2...γn, an input word of lengthn. In order to guess the length ofγ,Aproceeds with Level 1-Existential, Theorem7.19. Then it spawns (Level 2-Universal)nuniversal processes℘i, 1≤i≤n.

• On each ℘_i that checks a label γ_i, 1≤i≤q−1, such that γ_q is the left edge of the second communicating Szilard string occurring inγ,Aproceeds in the same manner as for the returning case.

•On each℘_q, such thatγ_q is placed at the beginning of a communicating Szilard string CandCis not the first communicating Szilard string inγ,Asearches forward inγ (Level 3-Existential) for the label placed at the right edge of C. Suppose that γt is this label, i.e., C = γ_q...γ_t. As C is a communicating Szilard string, γq−1 must be a query rule of the form αγq−1 → βγq−1, αγq−1 ∈ N and βγq−1 = z1Qi1z2Qi2. . . zc⁰Qi_c0zc⁰+1, where z_l∈(N∪T)^∗, 1≤l≤c⁰+ 1.

Chapter 7. Grammar Systems

For any symbolQij occurring inβγq−1,Asearches backward in γ (Level 4-Existential), for the very last communicating Szilard string that contains a label inLab(G_ij). Denote byC_ij this communicating Szilard string. Alocalizes in C_ij the Szilard word ofGij that satisfies Q_ij. Denote by S_ij this Szilard word and by s_ij the length ofS_ij (computable knowing the start and end position of S_ij in C_ij). A counts the number of labels in Lab(G1) occurring between the right edge ofC_ij and the left edge of C, i.e., the number of rewriting steps performed byG₁ between C_ij and C. Suppose this number isg_ij ≥1.

With this information, i.e.,sij andgij, acquired for each query symbol inβγq−1,Aguesses c⁰ positive integers`<sub>j</sub> such thats<sub>ij</sub> ≤`_j ≤s_ij+g_ij, 1≤j ≤c⁰, and`<sub>1</sub>+...+`_j =t−q+ 1 (each`j is the length of the Szilard word generated by Gij up to C, which is composed ofsij labels inLab(Gij) produced up toC_ij andgij labels produced betweenC_ij andC).

A stores the binary value of s_ij, g_ij, and `_j, along with the start and end positions of S_ij in γ, 1 ≤j ≤ c⁰, on the third block B₃ of the working tape. As c⁰ is bounded by a constant, that does not depend on the length of the input, the space needed by Ato store these numbers is O(logn).

Levels 5-6on process ℘_q (Universal-Universal) Aspawnsc⁰ universal processes (Level 5) ¯℘j, 1≤j ≤c⁰, each of which checks whether the substring γ_q+^Pj−1

i=0`i+s_ij are equal, i.e., the string that has satisfied Q_ij, at the previous communication step of G_ij, is a prefix of γ_q+^Pj−1

i=0`i...γ<sub>q+</sub><sup>P</sup>j i=0`i−1. If `j =sij, then A checks whetherS_ij is a Szilard word that corresponds to a terminal derivation in G_ij. This can be done (as at Levels 5-6, Theorem 7.19) by summing up the net effect of the rules used in S_ij, and checking that the sentential form contains no nonterminal. If S_ij is not a Szilard word that corresponds to a terminal derivation in Gij, then A checks whether γ_q+^Pj−1

i=0`i+s_ij...γ_q+^Pj

i=0`i is the suffix of a Szilard word of Gij, starting from the derivation point left “open” at the previous communication step in G_ij. Informally, this can be done in a similar way as in process℘_q, Level 6, in Theorem 7.19. Furthermore, when ever there exist two (or more) equal query symbols Q_ik and Q_il, A checks whether γ_q+^Pk−1

i=0`i...γ_q+^Pk

i=0`i−1 = γ_q+^Pl−1

i=0`i...γ_q+^Pl

i=0`i−1. If t=n, i.e., the rightmost label occurring inC is the end of the input word,Afollows the same procedure as for℘_n, Theorem7.19.

• On each plugged process ℘l, q + 1 ≤ l ≤ t, that takes a label γl occurring in a communicating Szilard string of the formC =γ_q...γ_t, or on each process℘_t⁰,t⁰ ≥t+ 1, such thatγt∈Lab(Gi), i6= 1, andγt⁰ ∈Lab(G1),A proceeds as in Theorem7.19, with the difference that q_i = 1, since each grammarG_i,i6= 1, never returns to its axiom.

It is easy to observe that A needs O(logn) time and space to perform the whole com-putation.

Corollary 7.23. SZ(N CP CrCF)⊂ N C¹.

Corollary 7.24. SZ(N CP CrCF)⊂DSP ACE(logn).

Note that Theorems 7.19 and 7.22, and consequently Corollaries 7.20, 7.21, 7.23, and 7.24 hold also for the case of unsynchronized PC grammar systems. In order to ob-tain this result, for instance for the case of unsynchronized CPCr(CF), in the proof of Theorem 7.19, A does not have to count the number of rewriting steps performed by grammar G1 between two consecutive communication steps of component Gij. Hence, when A guesses at process℘q of Theorem 7.19, c⁰ positive integers `j, 1 ≤j ≤c<sup>0</sup>, the only condition that these numbers must fulfill is `₁+...+`_c⁰ =t−q+ 1. (There is no synchronization between grammars. A grammar may perform several consecutive steps of derivation, meantime the others, including the master grammar, may wait.)

The Case of Non-Centralized PC Grammar Systems

For the case of non-centralized PC grammar systems any component may ask for the sentential form of any other component in the system. The Szilard word of the master grammarG₁ may be transfered, at any moment of the derivation, to another grammar.

Hence, for the returning case, what may be expected before ending up a derivation to be the prefix of a Szilard word (generated by G₁) may become, during the last steps of derivation, a substring or a suffix of the system’s Szilard word. This happens in the case that G₁ interrogates the grammar whose G₁’s former Szilard word has been communicated. Otherwise, G₁’s former Szilard word is wiped out (sinceG₁ returns to its axiom), and the system’s Szilard word is obtained just at the end of derivation.

Since non-returning PC grammar systems do not forget, after performing a communi-cation step, their derivation “history”, these PC grammar systems are easier to handle.

We point out that, when Γ is a non-centralized PC grammar system any Szilard word of Γ is either of the formγ =γr1C₁γr2C₂...γrkC_k or, of the formγ =γr1C₁γr2C₂...C_k−1γrk. A string of type γ_r corresponds to those rewriting steps in G₁ that take place before any communication event through which γr is sent to another grammar Gi, i6= 1. In order to distinguish aγ_r sequence from a “γ_r ” sequence that has been communicated to another grammar, we call the later substring adummy γ_r rewriting substring (while the former is considered an original rewriting substring).

A string of type C is composed of concatenations of Szilard words of grammars G_i, i 6= 1, which satisfy query symbols occurring in the query rule that cancels γr (that precedes C). A Szilard word of G_i is composed of sequences of labels in G_i (due to consecutive rewriting steps in Gi) and Szilard words of other grammars Gj, including G₁,j6=i, that satisfy query symbols produced by G_i.

Chapter 7. Grammar Systems

To be observed thatC cannot end up in a label inLab(G1). Indeed, if the rightmost label inC belongs to Lab(G₁), then there must exist in Γ a configuration with Szilard words (see Definition7.5and Examples7.1and7.2) of the form ((x1, α1), ...,(xi, αi), ...,(xj, αj), ...,(x_r, α_r)), 1< i < j< r, such that |x₁|_Qi>0,|x_i|_Qj>0,x_j contains no query symbols and α_j ends in a label γ_t∈ Lab(G₁). As γ_t cancels α_j, no rewriting step should be performed byGjafter it asked for the sentential form ofG1, unlessxjis a terminal string, i.e., x₁ is a terminal string, which is absurd. Hence, ((x₁, α₁), ...,(x_i, α_i), ...,(x_j, α_j), ..., (xr, αr)) should be obtained from ((x⁰₁, α⁰₁), ...,(x⁰_i, α⁰_i), ...,(x⁰_j, α⁰_j), ...,(x⁰_r, α⁰_r)) through a communication step in which x⁰₁ is sent to G_j, α_k =α⁰_k (andx_k=x⁰_k), for each k6=j, αj=α⁰_jα1, |x⁰₁|_Qi>0, |x⁰_i|_Qj>0, and |x⁰_j|_Q1>0, which contradicts⁴ Definition 7.2 (the sentential form of G1 cannot be sent to Gj, since it contains a query symbol). For non-returning non-centralized PC grammar systems we have [40]

Theorem 7.25. Each language L ∈ SZ(N P C_rCF) can be recognized by an indexing ATM in O(logn) time and space (SZ(N P CrCF)⊆ALOGT IM E).

Proof. Let Γ = (N, K, T, G1, . . . , Gr)∈SZ(N P CrCF), A an ATM with the same con-figuration as in Theorem7.19, and γ ∈Lab^∗(Γ),γ =γ₁γ₂...γ_n, an input word of length n. To guess the length ofγ,A proceeds with Level 1-Existential, Theorem 7.19. Then A spawns n universal processes ℘_i, 1 ≤ i ≤ n, (Level 2-Universal) such that each ℘_i checks a label γi occurring inγ as follows.

I₁. On any process ℘_q that takes a label γ_q ∈ Lab(G₁), occurring in a string of type γ_r ,Achecks whetherγ_q can be applied on the sentential form obtained at theq^th step of derivation in G1, i.e., the nonterminal rewritten by γq exists in the sentential form corresponding toγ^(q)=γ₁γ₂...γq−1. This can be done, as described in Theorem7.19,I₄, by summing up the net effect of each rule γs, 1 ≤ s≤ q−1, with the difference that q_i = 1 (since Γ is a non-returning PC grammar system).

To distinguish an original γr substring from a dummy one, A searches backward in γ (Level 3-4 Existential-Universal) for a rewriting sequence γ_r⁰ such that γ_r = γ_r⁰. If no such substring is found, then γ_r is an original one. Otherwise, let s^(f)_γr and s^(c)_γr be the position of the first and the current occurrence⁵ of γr in γ, respectively. A checks, by universally branching⁶ (Level 5) pairs of labels of the form (γ

s^(c)_γr −s^(f)_γr +j,γ_j), 1≤j≤s^(f)γr −1, whether γ_s(c)

γr −s^(f_γr⁾+1...γ_s(c)

γr −1 equalsγ1...γ_s(f)

γr −1, i.e., γ1...γ_s(f)

γr −1γr is a communicated substring, case in which if it is correct,γ_r is a dummy rewriting sequence.

4This is the case of acircular query. Any circular query blocks the work of Γ on the corresponding branch of derivation.

5These are the positions inγ of the first label inγr for the first and current occurrence ofγr inγ.

6Each branch returns 1 ifγ

s^(c)_γr −s^(f)_γr+j=γj, and 0 otherwise, where 1≤j≤s^(f)γr −1.

I2. On any℘q that takes a labelγq placed at the beginning of a communicating Szilard stringC, i.e.,γq−1∈Lab(G₁),γ_q ∈Lab(G_i),i6= 1, andγq−1 is a query rule,Asearches forward (Level 3-Existential) for the label γt that cancels C (C = γq...γt) such that γ_t+1 ∈ Lab(G₁), γ_t ∈/ Lab(G₁), γ_t is not a query rule, and C is delimited at the left and right side by two consecutive (original) sequences of type γ_r (whose correctness are checked as in Levels 3-4, I1). Let γq−1 be a query rule of the form αγq−1 →βγq−1, β_γq−1 =z₁Q_i1z₂Q_i2. . . z_cQ_icz_c+1, wherez_l∈(N∪T)^∗, 1≤l≤c+1. Aguessescpositive integers `j, 1 ≤j ≤c, such that `1+...+`c=t−q+ 1, where each`j is the length of the Szilard word ofG_ij that satisfiesQ_ij. A stores all these numbers in binary, onB₃, by using O(logn) space. Then A spawnscuniversal processes ¯℘j, 1≤j≤c, (Level 4), each of which checks whetherγ_{`j</sub> =γq+xj−1...γ<sub>q+xj−1+`j}−1 is a valid Szilard word of Gij, wherexj−1 =Pj−1

i=0`_i.

I3. On each ¯℘j, A spawns `j universal processes ¯℘j,ı (Level 5), each of which takes a label γ<sub>x</sub>, x =q+xj−1+ı, 1≤ı ≤`_j−1, and it checks whether γ_x can be applied on the sentential form obtained up to the application of rule γx−1.

Note that eachγ_{`j</sub> may be composed of i.) substrings over labels inG<sub>ij</sub>, corresponding to consecutive rewriting steps in Gij, that have not been transfered to other grammars, and ii.) substrings over labels inG<sub>i</sub>,i6=i<sub>j</sub>, which are Szilard words inG<sub>i</sub> that satisfied query symbols set by Gij. Szilard words in Gi may also be composed of substrings over labels in Gij, which represent consecutive rewriting steps in Gij that have been transfered to grammar G<sub>i</sub>. In other words,γ<sub>`j} has the same structure as γ, withG_ij as the master grammar. Denote by γ^(G_` ^ij)

j substrings of type i, and by γ_`^(Gi)

j substrings of type ii. Suppose that γ`j is composed of k substrings of type i, in which the l<sup>th</sup> such substring is denoted byγ<sub>l,`</sub>^(Gij)

j , and the l^thcommunicating substring is denoted by γ_l,`^(Gi)

j . Suppose thatLl,`j ( Ll,`j) is the length ofγ^(G_l,`^ij)

j (respectively,γ_l,`^(Gi)

j ). Ll,`j is computable knowing the start and end positions ofγ<sub>l,`</sub>^(Gij)

j inγ_{`j</sub>. To localize γ<sub>l,`}^(Gij)

j (orγ_l,`^(Gi)

j ) in γ_`j, A proceeds in the same way as for substrings of typeγ_r in G₁. This is possible due to the fact that any string that satisfies a query symbol posed by G1 in βγq−1 is a prefix of the Szilard word of G_ij generated from the beginning of derivation in Γ (since Γ is a non-returning system).

Suppose that up to the q^th label in γ, G1 has performed tq rewriting steps (tq is com-putable knowing the location of eachγ_r inγup to theq^thlabel). SinceG₁has performed tq rewriting steps any grammarGij, whose Szilard words satisfy query symbols inγq−1

must perform at most t_q rewriting steps.

However, when Szilard words of a grammar G_i, i 6= i_j, satisfy query symbols set by grammar Gij inside γ_`j, the number of rewriting steps performed by Gi, up to the

Chapter 7. Grammar Systems

interrogation time, must be less or equal to the number of rewriting steps performed by G_ij on γ_{`j</sub>, and so on. The space used by A to record the number of rewriting steps performed byG1 may be later reused to record the number of rewriting steps performed by G<sub>ij</sub>, since the number of derivation steps performed by any grammar inside γ<sub>`j} (including G₁) are related afterwards to the number of derivation steps performed by Gij. Hence, the space used by A does not exceed O(logn). Furthermore, each time A meets a substring in γ_`j composed of labels corresponding to rewriting steps inG₁, that satisfies a query symbol set by Gij, A checks whether this substring matches the prefix of γ of length at most the number of rewriting steps done by G_ij up to the interrogation time. The same procedure is applicable to grammar Gij, when A meets a substring composed of labels corresponding to rewriting steps in Gij occurring in a communicating Szilard string that satisfies a query symbol set byG_i.

I_3a. On any ¯℘_j,m (of type ¯℘_j,ı) that takes the m^th label, denoted by γ_j,m, in γ_l,`^(Gij)

j , 1 ≤ m ≤ Ll,`j, 1 ≤ l ≤ k, A checks whether⁷ Pl−1

j=1Lj,`j +m ≤ tq, and whether the nonterminal α_γj,m (rewritten by γ_j,m) exists in the sentential form corresponding to γ_j,m^(m−1) =γ_q+xj−1...γj,m−1. This can be done, as in I₁ (applied to G_ij) by summing up the net effect of each rule in γ_j,m^(m−1).

I3b. On any ¯℘j,q (of type ¯℘j,ı) that takes a label γj,q such that γj,q−1 ∈ Lab(Gij), γ_j,q ∈ Lab(G_i), i 6= i_j, and γj,q−1 is a query rule in G_ij, i.e., on any ¯℘_j,q that takes a label γ_j,q placed at the beginning of a communicating Szilard string γ_l,`^(Gi)

j in G_ij, A proceeds as follows. Let γj,q−1 be a query rule for which its right-hand side is of the form β_γj,q−1 = z₁Q_l1z₂Q_l2. . . z_c⁰Q_l

c0z_c⁰₊₁. As for the case of rule γq−1 ∈ Lab(G₁), A guessesc⁰ positive integers`<sup>0</sup><sub>j</sub>0, such that `⁰₁+...+`<sup>0</sup><sub>c</sub>0 = Ll,`j, where each `<sup>0</sup><sub>j</sub>0, 1≤<sup>0</sup> ≤c<sup>0</sup>, is the length of the Szilard word of component G<sub>lj</sub>0, that satisfies Q<sub>lj</sub>0 in β<sub>γj,q−1</sub>. Then A checks in parallel whether each substring of length`⁰_j0 is a valid Szilard word ofGl_j0.

c0z_c⁰₊₁. As for the case of rule γq−1 ∈ Lab(G₁), A guessesc⁰ positive integers`<sup>0</sup><sub>j</sub>0, such that `⁰₁+...+`<sup>0</sup><sub>c</sub>0 = Ll,`j, where each `<sup>0</sup><sub>j</sub>0, 1≤<sup>0</sup> ≤c<sup>0</sup>, is the length of the Szilard word of component G<sub>lj</sub>0, that satisfies Q<sub>lj</sub>0 in β<sub>γj,q−1</sub>. Then A checks in parallel whether each substring of length`⁰_j0 is a valid Szilard word ofGl_j0.

In document Advanced Studies on the Complexity of Formal Languages (sivua 171-182)