Szilard Languages of Phrase-Structure Grammars

Recall from Subsection 2.3.4 that a phrase-structure grammar G = (N, T, P, S) is in simple normal form (Definition 2.13) if every rule in P is in one of the following forms A→α,AB→λ, whereA, B∈N,α∈(N∪T)^∗.

In [192] it is proved that each phrase-structure grammar can be put in simple normal form without affecting the language generated. From [42] we have

Theorem 5.4. The leftmost Szilard language of a phrase-structure grammar in simple normal form can be recognized by an indexing ATM in O(logn) time and space.

Proof. LetG= (N, T, P, A1) be an arbitrary phrase-structure grammar in simple normal form, where A₁ is the axiom, N = {A₁, A₂, ..., A_m} and P = {p₁, p₂, ..., p_k} are the ordered sets of nonterminals and rules, respectively. In the sequel, each rule of the form AB → λ (A → λ, A → t, A → β) is labeled by p_{iP S} (p_iCFλ, p_iCFt, p_iCF, respectively) wheret∈T⁺,β∈(N ∪T)⁺, and iis the order number of rulepi inP.

Letγ =p_i1x

1p_i2x

2...p_inxn be an “indexing” word inP^∗, wherex_j ∈ {CF_λ, CF_t, CF, P S}, 1≤j≤n. Denote by`(pij, k) thek^thnonterminal of the left-hand side ofpij,k∈ {1,2}, and by r(p_ij, k) the k^th nonterminal of the right-hand side of p_ij,k ≥1, both counted from left to right. Letrp_ij be the number of nonterminals on the right-hand side ofpij. ByA6↑t(A6↓t),A∈N,t∈T⁺, is meant thatAis not followed (preceded) by a terminal or string of terminals. Next we describe an indexing ATM A that reads γ ∈ P^∗ and checks, inO(logn) time and space, whetherγ is a possible leftmost Szilard word. Beside the input and the index tape,Ahas one working tape composed of three (independent) tracks, used in a similar manner as in Theorem 5.1, i.e., to store the vectors V⁰ and V(p_i), 1≤i≤k, and several other auxiliary values. In order to guess the length of γ, Aproceeds with the procedure described atLevel 1, in the proof of Theorem5.1. Then A universally branches all p_ijxj, 1 ≤ j ≤ n. On each branch A checks whether p_ijxj, 1 ≤ j ≤ n, can be the j^th production of a leftmost derivation. Since all branches are universally considered, the process enabled at the j^th branch is supposed to work if all

leftmost derivation conditions imposed to previous rules in γ, fulfill. On each branch B_j, 1≤j≤n,A proceeds as follows.

B₁. A checks whether`(pi1,1) =A1. B₂. A checks whether p_i2x

2 can be applied, according to the leftmost derivation order, over the previous rule⁴, i.e., Aexistentially checks conditions 1) and 2):

1. x₂ ∈ {CF_λ, CF_t, CF} and`(p_i2,1) =r(p_i1,1),

S₁. Suppose that betweenp_i1 andp_ijthere arekgroups of context-free non-erasing rules.

Letpij2hxj2h...pij2h−1xj2h−1be these groups⁷, with xiq=CF,j2 ≤q ≤j1,j_2h≤q≤j2h−1, and x_iq0∈ {CF_λ, CF_t, P S},j₁< q⁰≤j−1,j2h−1< q⁰< j2h−2, 2≤h≤k, 1 =j_2k ≤j2k−1

< j2k−2 ≤j2k−3 <...< j2≤j1< j. Aspawns Σ^k_h=1(j2h−1−j2h+ 1) existential branches,

4This process (and all the others) does not check whether the previous rule(s) can be applied in a leftmost derivation order. Since all branches are universally considered the input wordγis accepted, if and only if all branchesBi, 1≤i≤n, are labeled by 1.

5Ifrp_ij−2 = 1, thenAguesses an integerc, 3 ≤c≤j−1, such thatrp_ij−c ≥2, and no CFλ/t or phrase-structure rule occurs betweenpi_j−c andpi_j−2.

6That is, no terminal separates`(pi<sub>j</sub>,1) and`(pi_j,2) in the sentential form wherepi_j is applied.

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars

The aim of procedureS₁is to find the rulep_iq that pumps in the sentential form the non-terminal rewritten byp_ij. The groups of rules p_iq... p_ij

have a contribution in a leftmost derivation order, on all sentential forms up to the j^th step of derivation, with a number of Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0r_pim −(j_2h⁰−1 −j_2h⁰ + 1)) + Σ^j_m=q+1^2h−1 rp_im −(j2h−1−q) nonterminals. All these nonterminals together with the non-terminals introduced by rule p_iq up to the nonterminal r(p_iq,Σ^h_h0=1(k_2h⁰−1+ 2k_2h⁰)− nonterminal that must be rewritten, in a leftmost derivation order, by the rulepij. If no rulep_iqCF, with the above properties, can be found in any of thekgroups (all existential branches are labeled by 0) B_j is labeled by 0. Otherwise, if there exist at least one branch⁸ in the existential fork spawned atS₁ (labeled by 1) thenB_j is labeled by 1.

S₂. Consider that betweenpi1 andpij−1 there existkgroups of context-free non-erasing rulespij2hxj2h...pij2h−1xj2h−1, 1≤h≤k, with similar properties as inS₁. ThenAspawns Σ^k_h=1(j2h−1−j_2h+1) existential branches, and for eachp_iqxiq,j_2h ≤q ≤j2h−1, 1≤h≤k, Achecks whether the inequality 1) fromS₁, and equality 2) fromS₁, in which the left-hand side of this equality is replaced by `(p<sub>ij</sub>,2), hold. A must also check whether no terminal separates`(pij,1) and`(pij,2), in the sentential form where rulepij is applied.

S₃. Consider that between p_i1 and p_ij there existk groups of context-free non-erasing rules, pij2hxj2h...pij2h−1xj2h−1, 1 ≤ h ≤ k, with the same properties as in S₁. Then A generates Σ^k_h=1(j2h−1−j_2h+ 1) existential branches. Each branch corresponds to a rule p_iqxiq,j_2h≤q≤j2h−1, 1≤h≤k. For this rule Aexistentially checks 1) and 2):

1. r_piq ≥Σ^h_h0=1(k_2h⁰₋₁+2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0r_pim−(j_2h⁰₋₁−j_2h⁰+1))−(Σ^j_m=q+1^2h−1 r_pim− (j2h−1−q)) + 1,

8If there exist more than one existential branch labeled by 1, then the greatest indexqis the correct solution for the branchBj.

2. rp_iq = Σ^h_h0=1(k2h⁰−1+2k2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0rp_im−(j_2h⁰₋₁−j_2h⁰+1))−(Σ^j_m=q+1^2h−1 rp_im− (j2h−1−q)),

where eachki, 1≤i≤2k, has the same meaning as inS₁. If 1) holds, thenAuniversally checks whether:

• `(p_ij,1) =r(p_iq,Σ^h_h0=1(k_2h⁰−1+ 2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0r_pim−(j_2h⁰−1−j_2h⁰+ 1))− (Σ^j_m=q+1^2h−1 rp_im −(j2h−1−q))),

• `(p_ij,2) =r(p_iq,Σ^h_h0=1(k_2h⁰−1+ 2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0r_pim−(j_2h⁰−1−j_2h⁰+ 1))− (Σ^j_m=q+1^2h−1 rp_im −(j2h−1−q)) + 1),

• r(piq,Σ^h_h0=1(k_2h⁰−1+2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0rp_im−(j_2h⁰₋₁−j_2h⁰+1))−(Σ^j_m=q+1^2h−1 rp_im− (j2h−1−q)))6↑t.

If 2) holds, thenA universally checks whether:

• `(pij,1) =r(piq,Σ^h_h0=1(k_2h⁰−1+ 2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0rp_im−(j_2h⁰−1−j_2h⁰+ 1))− (Σ^j_m=q+1^2h−1 r_pim −(j2h−1−q))),

• r(piq,Σ^h_h0=1(k_2h⁰−1+2k_2h⁰)−Σ^h−1_h0=1(Σ^j_m=j^2h0−1

2h0rp_im−(j_2h⁰₋₁−j_2h⁰+1))−(Σ^j_m=q+1^2h−1 rp_im− (j2h−1−q)))6↑t,

• `(pij,2) =r(piq−1,1), r(piq−1,1) 6↓ t if q > j2h, otherwise, if q = j2h, A searches for the next group of consecutive non-erasing context-free rules, in order to cover the second nonterminal from the left-hand side of the rulep_{ijP S}. In this order A follows a procedure similar toS₁ (in which the valuej−1 is replaced by j_2h).

If no rule p_iqCF that satisfies 1) or 2) can be found in none of the k groups, then B_j is labeled by 0. If piq satisfies 1) along with the three conditions that follow it, then B_j is labeled by 1. If p_iq satisfies 2), but no rule p_iq0CF can be found such that

`(pij,2) = r(pi_q0,1), r(pi_q0,1) 6↓ t, in none of the groups of consecutive non-erasing context-free rules existing between pi1 and pij2h, then the branch B_j is labeled by 0.

Otherwise,B_j is labeled by 1.

B_n. For pi1x1...pin−1xn−1pi_nxn, A proceeds in a similar way as for the branch B_j. In addition, A checks whether the rule p_inxn ends up the computation, i.e., whether the sum V⁰+ Σⁿ_q=1V(p_iq) is the null vector (the sentential form contains no nonterminal).

Note thatS₁,S₂, andS₃, are guessing procedures. Aguesses an indexq(using the index tape) and checks whether the rules p_iq satisfies conditions described in S_i, 1 ≤ i≤ 3.

Each guess can be considered as an existential branch. There can be at most O(n) existential branches. Therefore, the time complexity, i.e., the height of the computation tree ofA, isO(logn). The space complexity is alsoO(logn) (all numbers are stored in binary). The sum V⁰+ Σⁿ_q=1V(piq) and the number of erasing rules can be computed by a counting procedure belonging toN C¹.

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars

Corollary 5.5. The leftmost Szilard language associated with a context-free grammar can be recognized by an indexing ATM in O(logn) time and space.

Proof. The claim is a special case of Theorem5.4with no rules of the formAB→λ.

Corollary 5.6. SZL(CF)⊂ N C¹.

In [137] it is proved thatSZL(CF)=SS, whereSS is the class of languages generated by ss-grammars. Recall (Definition 2.5, Subsection 2.3.1) that an ss-grammar is a context-free grammar G= (N, T, P, A₁) with rules of the formsX→aY,a∈T,Y∈N^∗, such thata uniquely identifies a production, i.e., no other production inP has aon its right-hand side. Using this property it is trivial to prove that SS ⊂ N C¹, as follows.

LetAbe an indexing ATM andw=a₁a₂....a_n∈T^∗. Using universal statesAuniversally branches all ai, 1≤ i≤n. Since each ai uniquely identifies the production applied at thei^thstep of derivationAknows which nonterminal is rewritten at this step. Hence, as in the proof of Theorem 5.1,A checks whether this nonterminal exists in the sentential form obtained at thei^thderivation step. Therefore, Corollary5.6can be also considered as a consequence of the (proper) inclusionSS ⊂ N C¹.

Recall (Definition 2.13, Subsection 2.3.4) that a context-sensitive (phrase-structure) grammarG= (N, T, P, S) is in (extended) Kuroda normal if each rule in P is in one of the formsA→BC, (A→λ),A→t, orAB→CD,A, B, C, D∈N,t∈T.

In [143, 145] it is proved that each context-sensitive (phrase-structure) grammar can be put in (extended) Kuroda normal form without affecting the language generated.

Next we prove several results similar to Theorem 5.1, for leftmost Szilard languages of context-sensitive and phrase-structure grammars.

Theorem 5.7. The leftmost Szilard language associated with a context-sensitive (phrase-structure grammar) in (extended) Kuroda normal form can be recognized by an indexing ATM in O(logn) time and space.

Proof. The claim is a consequence of Theorem 5.4, in which instead of erasing rules of type AB→λ, rules of the form AB→CD are considered.

More generally we have [42]

Theorem 5.8. The leftmost Szilard language associated with an arbitrary phrase-structure grammar can be recognized by an indexing ATM in O(logn) time and space.

Proof. Let G = (N, T, P, A1) be an arbitrary phrase-structure grammar, where N = {A₁, A₂, ..., A_m}, andP ={p₁, p₂, ..., p_k}are the ordered finite sets of nonterminals and rules, respectively. Each rule of the form A → λ(respectively A → t, A → β, α → λ, α → t, α → β) is labeled by pi_CFλ (respectively pi_CFt, pi_CF, pi_{P Sλ}, pi_{P St}, pi_{P S}) where

t∈T⁺,α∈(N ∪T)^∗N(N∪T)^∗,β∈(N ∪T)⁺, and iis the order number of rulepi in P. To each rule p_i we associate two positive integers l_pi and r_pi, where l_pi and r_pi are the numbers of nonterminals in α and β, respectively. Furthermore, `(pij, k) denotes the k^th, k ≥ 1, nonterminal in α and r(p_ij, k) denotes the k^th nonterminal in β, both tape, and one working tape composed of three tracks, used in a similar manner as in Theorems 5.1 and 5.4, i.e., to store the vectors V⁰ and V(pi), 1 ≤ i ≤ k, and several other auxiliary values. A hasγ ∈P^∗ as input word. It checks, in logn time and space, whether γ, of length n, can be a leftmost Szilard word.

In order to guess the length ofγ,Afirst proceeds with the procedure described atLevel 1, in the proof of Theorem 5.1. Then A universally branches allp_ijxj, 1≤j≤n. Each branch checks whetherpi_jxj, 1≤j ≤n, can be thej^thproduction activated in a leftmost derivation order, as follows: the same time a prefix and suffix for itself.

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars left-hand side of p_ij occurs also on the right-hand side of p_ij−c. The meaning is that the left-hand side of rulepij is covered by suffixes of right-hand sides of some rules occurring betweenc consecutive context-free or phrase-structure rules, such that the right-hand side ofpij−c holds in a suffix of the left-hand side of rule pij. In this case A checks whether there exist at least two consecutive rulespx−1 and

10Heretis the terminal string placed on the right-hand side of ruleX→t. Ifx2=CFλ, thent=λ.

11Heretis the right-hand side of rulepi₂. Ifx2=P Sλ, thent=λ.

12The main difference is that the sum Σ^h_h0=1(k2h⁰−1 + 2k2h⁰) is replaced by Σ^j−1_m=j1+1lp_im + Σ^h−1_h0=1Σ^j_m=j^2h0−1

2h0+1+1lp_im, i.e., the number of nonterminals deleted by erasing context-free and phrase-structure rules occurring inside the groupspij2h0...pij2h0 −1, 1≤h⁰≤h−1.

px,ij−c+1 < x < ij, such that lpx > rpx−1. If this happens, cmay be infinite, and Acontinues with procedure S₅. Ifl_px ≤r_px−1 for all two consecutive rulesp_x and px−1,ij−c+1 ≤x≤ij−1, thencis finite, and Acontinues with procedure S4. S₄. In this case, A universally checks: 1. `(pij, k) = r(pij−1, k), 1 ≤ k ≤ rp_ij−1,

`(p<sub>iq</sub>, k) =r(p<sub>iq−1</sub>, k), 1≤k≤l<sub>piq</sub>,j−c+ 1≤q ≤j−1, 2. `(pij, rp_ij−1 +k) =r(pij−2, lp_ij−1 +k), 1≤k≤rp_ij−2 −lp_ij−1, 3. `(p_ij, r_pij−1+Pc⁰

x=1(r_pij−x−1−l_p

ij−x)+k) =r(p_ij−c0−2, l_pi

j−c0−1+k), 1≤k≤r_pi

j−c0−2− lpij−c0−1, 1≤c⁰ ≤c−2,

4. `(p<sub>ij</sub>,1)↓t≺<sub>s</sub>r(p<sub>i1</sub>,1)↓<sub>p</sub> t+r(p<sub>i2</sub>,1)↓<sub>p</sub> t+...+r(p<sub>ij−1</sub>,1)↓<sub>p</sub> t, 5. `(pij, k)↑t=r(pij−1, k)↑t, 1≤k≤rp_ij−1 −1,

6. `(pij, rp_ij−1)↑t=r(pij−1, rp_ij−1)↑t+r(pij−2, lp_ij−1 + 1)↓_s t,

7. `(p<sub>ij</sub>, r<sub>pij−1</sub> +k)↑t=r(p<sub>ij−2</sub>, l<sub>pij−1</sub> +k)↑t, 1≤k≤r<sub>pij−2</sub> −l<sub>pij−1</sub> −1 8. `(pij, rp_ij−1 +rp_ij−2 −lp_ij−1)↑t=r(pij−2, rp_ij−2)↑t+r(pij−3, lp_ij−2 + 1)↓_s t, 9. `(pij, rp_ij−1 +Pc⁰

x=1(rp_ij−x−1 −lp_ij−x) +k)↑ t=r(pi_j−c0−2, lpij−c0−1 +k)↑ t,1≤k≤ rpij−c0−2−lpij−c0−1−1,

10. `(pij, rp_ij−1+Pc⁰

x=1(rp_ij−x−1−l_pij−x)+rpij−c0−2−l_pi

j−c0−1)↑t=r(pi_j−c0−2, rpij−c0−2)↑ t+r(p_ij−c0−3, l_pi

j−c0−2 + 1)↓_st, 1≤c⁰ ≤c−2,

11. `(p_ij, l_pij)↑t≺_p r(p_ij−1, l_pij)↑_st+r(p_ij−2, l_pij−1)↑_st+...+r(p_i1, l_pi

2)↑_st.

For procedureS₅we first provide a sequential algorithm. A parallel algorithm, performed by an indexing ATM in logarithmic time and space, is explained afterward.

In the sequel, if x1 and x2 are two strings such thatx1 is a prefix ofx2, then byx2−x1

we denote the suffix of x₂ obtained by erasing the prefix¹³ x₁. By |x| we denote the length of the string x. If px is a rule in P, then by lh(px) and rh(px) we denote the left-hand side and the right-hand side of px, respectively. Each side of a rule has the formH(p_x) =H_tpxH_Vpx, where H_tpx ∈T^∗ andH_Vpx ∈N(T∪N)^∗,H ∈ {rh, lh}. A rule px for whichlpx > rpx−1 is called left-increasing rule, a rulepx−1 for whichlpx < rpx−1 is called right-increasing rule.

Suppose that an integer c has been guessed such that rp_ij−1 +rp_ij−2 +...+rp_ij−c ≥ l_pij+l_pij−1+...+l_pij−c+1 holds, the last nonterminal from the left-hand side ofp_ij occurs in the right-hand side of pij−c, and there exist at least two consecutive rules px−1 and p_x, ij−c+1 < x < i_j, such that l_px > r_px−1. Then A working in a sequential manner, needs a second working tape, that works similar to a pushdown store, and uses the next three routines, briefly explained below.

A. For each left-increasing rulepx (lpx> rpx−1),ij−c+1< x≤ij,rhV_px−1 must be a pre-fix oflh_Vpx, otherwise the input is rejected. If this holds the suffixlh_Vpx−rh_Vpx−1 oflh_px

13For instance, ifx1=abcandx2=abcdef g, thenx2−x1=def g.

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars

is recorded on the second working tape of A(a “push” operation). This routine is ap-plied if rh(px−1) =λ or rh(px−1) = t, t∈ T^∗. In this case, the whole string lh_Vpx is recorded on the second working tape. All strings recorded on this tape are delimited by a ]symbol.

B. If l_px = r_px−1, then A checks whether the strings lh_Vpx and rh_Vpx−1 are equal, and the second working tape ofA is left unchanged. IflhV_px and rhV_px−1 are not equal the input is rejected.

C. For each right-increasing rulepx−1 (l_px < r_px−1), ij−c+1 < x < i_j, lh_Vpx must be a prefix ofrhV_px−1 (otherwise the input is rejected). Denote`1]...]`q−1]`qthe strings (left-hand sides of left-increasing rules) recorded on the second working tape, untilp<sub>x</sub> is read (from right to left) inγ. If|`_q| ≥ |rh_Vpx−1−lh_Vpx|, thenAchecks whetherrhV_px−1−lh_Vpx is a prefix of `<sub>q</sub>. If this does not hold the input is rejected. If rh<sub>Vpx−1</sub> −lh<sub>Vpx</sub> is equal with a prefix of`_q, then this prefix is deleted from the second working tape (a “slow pop”

operation¹⁴ for `q). If |`_q| < |rh_Vpx−1 −lh_Vpx|, then rh_Vpx−1 −lh_Vpx is covered by the left-hand sides of more than one rule, delimited on the second working tape by]symbols.

In this case A checks whether `q is a prefix of rhV<sub>px−1</sub> −lhV<sub>px</sub> (otherwise the input is rejected). If this property holds, `_q is deleted from the second working tape (a “pop”

operation for `q). Then the suffix rhV<sub>px−1</sub> −lhV<sub>px</sub> −`q of rhV_px−1 −lhV_px is compared with`q−1. If |`_q−1| ≥ |rh_Vpx−1 −lh_Vpx −`<sub>q</sub>|, thenrh<sub>Vpx−1</sub> −lh<sub>Vpx</sub> −`_q must be a prefix of `q−1 (otherwise the input is rejected), and rh<sub>Vpx−1</sub> −lh<sub>Vpx</sub> −`_q is deleted from the second working tape (a “slow pop” operation for`q−1). If|`_q−1|<|rh_Vpx−1−lhV_px−`q|, then `q−1 must be a prefix of rh_Vpx−1 −lh_Vpx −`<sub>q</sub> (otherwise the input is rejected). In this case`q−1 is deleted from the second working tape (a “pop” operation for`q−1), and the checking procedure proceeds in the same way with the string`q−2.

ProcedureCcontinues forpx−1, until the entire stringrhV_px−1−lhV_px is checked out and deleted “piece by piece” from the second working tape. At the very first mismatch the input is rejected. Since at procedureA, the stringslh(p_x) andrh(px−1) are recorded on the second working tape without the prefixes lht_px andrht_px−1, respectively, “pieces” of strings that composerh_Vpx−1− lh_Vpx may not match perfectly with “pieces” of left-hand sides recorded on the second working tape, in the sense that some prefixes or suffixes, composed of terminal symbols, are missing fromrh_Vpx−1 − lh_Vpx or from`_z, 1≤z≤q.

Therefore, besides routinesA,B, andC,Aalso must check several heuristics of types4 -11. With the routinesA,B, and Cdescribed above S₅ sequentially works as follows.

S₅. (sequential version) Aslp_ij> rp_ij−1,Astarts with routineAand stores on the second working tape lh_Vpi

j

− rh_Vpi

j−1. A continues by applying routine Aas long as rules

oc-14In this case the whole string, placed on the top of the second working tape, will be entirely deleted by applying several “slow pop” operations.

curring in the Szilard word, read from right to left, are left-increasing. When A reads a group of consecutive erasing or terminal rules (composed of at least one erasing or terminal rule), according to routine A, all left-hand sides of these rules are recorded, from left to right, on the second working tape. At the first rulep_x,ij−c+1< x < i_j, such thatl_pij=r_pij−1 orl_pij< r_pij−1,Aproceeds with routine B orC, until the next left-in-creasing rule p_x⁰ is found in γ,ij−c+1< x⁰ < x < ij, when routine Ais applied again.

ProcedureS₅, working in a sequential manner, ends up when A succeeds to read, from right to left, the whole stringpij−cxij−c... pij−1xj−1pi_jxj. If all strings checked during rou-tines B and C match, and at the end of S₅ the second working tape is empty, B_j is labeled by 1. Otherwise,B_j is labeled by 0. Since it might require linear time and space the sequential version ofS₅is not suitable for our considerations, ascmight be arbitrarily large. However, it provides a natural interpretation of the leftmost derivation mechanism through a pushdown-like structure. Next we describe a parallel version ofS₅.

S₅. (parallel version) Suppose that inputγ is read from right to left. According with the leftmost derivation mechanism described above if two rules p_x and p_x⁰, ij−c+1<

x⁰< x < ij, are left-increasing rules and no other left-increasing rule occurs between p_x⁰ and p_x, then in the sentential form created during the execution of the Szilard subwordpij−c...px⁰...px...pij first (readingγ from right to left) must be introduced those nonterminals that occur in suffix lh(p_x⁰)−rh(p_x⁰−1) and afterward those nonterminals that occur in suffix lh(p_x)−rh(px−1). Ifp_x is the first left-increasing rule that precedes pij in the Szilard word, and no other left-increasing rule occurs betweenpx and pij, and there are too many right-increasing rules between p_x and the very first left-increasing rulep_x⁰ that precedespxin the Szilard word, whereij−c+1< x⁰< x< ij, then the number of nonterminals introduced in the sentential form by right-hand sides of right-increasing rules occurring betweenpx⁰ and px, must “cover” first the whole left-hand side ofpx and at least a prefix oflh(pij)−rh(pij−1).

This is the reason why the left-hand side of rule p_ij may be split into a (finite) number of substrings “covered” by the right-hand sides of several right-increasing rules scattered along the Szilard subwordp_ij−cxi

j−c... p_ij−1xj−1p_ijxj. In order to find the right-increasing rules placed betweenp_ij−c andp_ij−1 inγ, that introduce subwords of the left-hand side of rule pij, A guesses all possible t-tuples of pairs, (sq, νq), 1 ≤ q ≤ t, where t is the number of disjoint subwords in whichlh(p_ij) can be split ands_q is the position of rule pi_sq in the Szilard word that inserts νq in the sentential form. Denote by µq the length of ν_q, i.e.,µ_q=|ν_q|, 1≤q≤t, thenlh(p_ij)=ν_t...ν₁, and µ_t+...+µ₁=|lh(p_ij)|.

As all s_q’s, 1≤ q≤ t, depend on the length of the Szilard word, s_q may be arbitrarily large, while µq is always finite. Because lh(pij) is a finite string, there exist a finite number of t-tuples of pairs (non-deterministic guessings) with the above properties.

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars

This makes it possible to compute and store thet-tuples by using logarithmic time and space. Suppose that for p_ij there existc_s possible t-tuples of pairs. Then A spawnsc_s existential branches. On each branch, holding at-tuple of the form ((s1, ν1), (s2, ν2), ...,

ist nonterminal in rhp_ist, and heuristics of types4 - 6 hold forν_t,

Note that for each existential branch, holding an arbitrarily large integer c, A checks whether the inequality rp_ij−1 +rp_ij−2 +...+rp_ij−c ≥ lp_ij +lp_ij−1 +...+lp_ij−c+1 holds.

This can be performed in logarithmic time and space, i.e., the function is computable insideN C¹. Each branch for which this inequality holds is labeled by 1.

If no c can be found with the above property, i.e., all branches are labeled by 0, then the branch B_j is labeled by 0, and the input is rejected (all B_j branches, 1 ≤ j ≤ n, are universally considered). The computation continues with the procedureS₅ (parallel version), only on those branches labeled by 1. Each branch for which S₅ (holding a t-tuple) holds, is labeled by 1. Otherwise, the branch is labeled by 0. If all branches spawned by A, during the execution of S₅, are labeled by 0, the branch B_j is labeled by 0, and the input is rejected. If there exist at least one branch spawned by Aduring S₅, labeled by 1,B_j is labeled by 1. If there exist more than one existential branch that correctly guesses an arbitrarily large integer c, the closest branch to j is considered as the most likely candidate forS₅.

B_n. Forp_i1x

1... p_in−1xn−1p_inxn,A proceeds in a similar manner as for the branch B_j. In addition, A checks whether the rule pi_nxn ends up the computation, i.e., whether the sum V⁰+ Σⁿ_q=1V(p_iq) is the null vector (the sentential form contains no nonterminal).

Each searching procedure described in S₁, S₄, and S₅ (parallel version), are guessing procedures that do not require more than O(logn) space (all numbers are stored in binary). In order to find an integercwith the property described at branchB_j, 4≤j≤ n,Aspawns at mostj existential branches, each branch corresponding to each rulepiq,

Each searching procedure described in S₁, S₄, and S₅ (parallel version), are guessing procedures that do not require more than O(logn) space (all numbers are stored in binary). In order to find an integercwith the property described at branchB_j, 4≤j≤ n,Aspawns at mostj existential branches, each branch corresponding to each rulepiq,

In document Advanced Studies on the Complexity of Formal Languages (sivua 104-117)