On the Complexity of Szilard Languages - Advanced Studies on the Complexity of Formal Languages

5.2 N C 1 Refinements

6.1.3 On the Complexity of Szilard Languages

Henceforth, in any reference to a matrix grammarG= (N, T, A1, M, F),A1 is supposed to be the axiom, N ={A₁, A₂, ..., A_m} the ordered finite set of nonterminals, and M = {m₁, m2, ..., mk} the ordered finite set of labels associated with matrices in M. Each matrixm_j, 1≤j≤k, is a sequence of the formm_j = (p_m_j_,1, p_m_j_,2, ..., p_m_j_,k_mj),k_m_j ≥1.

Unless otherwise specified, each p_m_j_,r, 1 ≤ r ≤k_m_j, is a context-free rule of the form αmj,r → βmj,r, αmj,r ∈ N and βmj,r ∈(N ∪T)^∗. If βmj,r ∈ T^∗, then pmj,r is called a terminal rule. Otherwise,p_m_j_,r is called a non-terminal rule.

We define thenet effect of rule pmj,r, 1≤r≤kmj, with respect to nonterminalAl∈N, 1≤l≤m, by the differencedf_A_l(pmj,r) =|β_m_j_,r|_A_l−|α_m_j_,r|_A_l. IfGis a matrix grammar without appearance checking, then thenet effect of matrixm_j with respect to each non-terminalA_l∈N, 1≤l≤m, is the sumsA_l(mj) = Σ^k_r=1^mjdfA_l(pmj,r). To each matrixmj

we associate a vectorV(m_j)∈Z^m defined byV(m_j) = (s_A₁(m_j), s_A₂(m_j), ..., s_A_m(m_j)).

Depending on the context, the value of V(mj) taken at the l^th place, 1 ≤l ≤ m, i.e., V_l(m_j), is also denoted byV_A_l(m_j) =s_A_l(m_j).

IfGis a matrix grammar with appearance checking, then apolicy of a matrix m_j ∈M, denoted by `^q_j, is a choice of mj of using a certain subsequence of matrix mj obtained by dropping out some rules that occur in the same time in m_j and F. Hence, if the policy`^q_j is defined by the subsequencem^q_j = (pmj,1, pmj,2, ..., p_m_j_,ξ^q

mj) ofmj, then rules in m^q_j occur in the same order they occur in m_j. The net effect of matrix m_j, with respect to policy `^q_j and nonterminal Al ∈ N, is defined by sAl(`^q_j) = Σ^ξ

qmj

r=1dfAl(pmj,r).

To each policy `^q_j, identified by the sequence m^q_j, we associate a vector V(`^q_j) ∈ Z^m

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

defined by V(`^q_j) = (sA1(`^q_j), sA2(`^q_j), ..., sAm(`^q_j)). The value of V(`^q_j) taken at the l^th place, 1≤l≤m, is denoted byV_l(`^q_j) =V_A_l(`^q_j) =s_A_l(`^q_j).

The Case of Unrestricted Szilard Languages

In terms of indexing ATM resources, for Szilard languages associated with context-free matrix grammars without appearance checking, we have the next result [36,38,39].

Theorem 6.8. Each language L ∈ SZM(CF) can be recognized by an indexing ATM in O(logn) time and space (SZM(CF)⊆ALOGT IM E).

Proof. Let G= (N, T, A₁, M, F) be a context-free matrix grammar with F =∅, and A an indexing ATM composed of an input tape that stores an input word η ∈ M^∗ of length n, η = η1η2...ηn, an index tape to read the input symbols, and a (read-write) working tape, divided into three horizontal tracks. The first track is of a fixed and finite dimension and, at the beginning of computation, it stores the Parikh vector of the axiom V⁰, i.e., V₁⁰= V_A⁰

1= 1 and V_l⁰= V_A⁰

l= 0, V(m_j), and the net effects df_A_l(p_m_j_,r) of all rules inmj, 1≤j≤k, 1≤r≤kmj, 1≤l≤m. The other two tracks are initially empty.

Level 1 (Existential) In an existential state A guesses the length of η and verifies the correctness of this guess, i.e., writes on the index tapen, and checks whether then^thcell of the input tape contains a terminal symbol and the celln+ 1 contains no symbol. The correct value of n is recorded in binary on the second track of the working tape. The first and second tracks are parted by a double bar symbol (k). The end of the second track (and the beginning of the third track) is market by another symbolk.

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

•On℘1,Areadsη1= (pη1,1, pη1,2, ..., pη1,kη1) and checks whetherαη1,1=A1andsdfαη1,r+1

=V_α⁰_η

1,r+1+Pr l=1df_α_η

1,r+1(p_η₁_,l)≥1, 1≤r ≤k_η₁−1, i.e., whether the nonterminalα_η₁_,r+1 rewritten by the (r+ 1)^thrule ofη1 exists in the sentential form generated up to ther^th step of derivation inη₁. Process℘₁ returns 1 if these conditions hold, and 0, otherwise.

•For each℘i, 2≤i≤n−1,Acounts the number of occurrences of each matrixmj ∈M, 1 ≤ j ≤ k, in η⁽ⁱ⁾ = η₁η₂...ηi−1. Suppose that each m_j occurs in η⁽ⁱ⁾ of c⁽ⁱ⁾_j times, 0≤c⁽ⁱ⁾_j ≤i−1. Then, for each 1≤l≤m,Acomputess⁽ⁱ⁾_A

l =V_l⁰+Pk

j=1c⁽ⁱ⁾_j Vl(mj), i.e., the number of occurrences of each A_l in the sentential form upon which η_i is applied.

Consider ηi = (pηi,1, pηi,2, ..., pηi,k_ηi) and αηi,1 = Aqi, 1 ≤ qi ≤ m. A checks whether s⁽ⁱ⁾_A

qi = s⁽ⁱ⁾α_ηi,1 ≥ 1, i.e., whether the matrix η_i can start the computation. For each 1≤r ≤kηi−1, A checks whether³ sdfα_ηi,r+1 =s⁽ⁱ⁾α_ηi,r+1 +Pr

l=1dfα_ηi,r+1(pηi,l)≥1, i.e., whether the rules p_η_i_,r, 2≤r ≤k_η_i, can be applied in the same order they occur inη_i. Process℘_i, 2≤i≤n−1, returns 1 if these conditions hold. Otherwise,℘_i returns 0.

3Heres⁽ⁱ⁾α_ηi,r₊₁ is actually the sums⁽ⁱ⁾_A

l whereαη_i,r+1 is thel^thnonterminal inN.

• The last process ℘n counts the numberc⁽ⁿ⁾_j of occurrences of each mj, 1≤j ≤k, in η⁽ⁿ⁾ =η₁η₂...ηn−1, and computes the sums s⁽ⁿ⁾_A

l =V_l⁰+Pk

j=1c⁽ⁿ⁾_j V_l(m_j) ands^(n,out)_A

l =

V_l⁰+Pk

j=1c⁽ⁿ⁾_j Vl(ηj) +Vl(ηn), 1 ≤ l ≤m. Consider ηn = (pηn,1, pηn,2, ..., pηn,k_ηi), and α_η_n_,1 = A_q_n, 1 ≤ q_n ≤ m. Process ℘_n returns 1, if s⁽ⁿ⁾_A

qn ≥ 1, sdf_α_ηn,r+1 = s⁽ⁿ⁾α_ηn,r+1 + Pr

l=1dfα_ηn,r+1(pηn,l)≥1, for each 1≤r≤kηn−1, ands^(n,out)_A

l = 0, for each 1≤l≤m.

Otherwise,℘_n returns 0.

Each of the above processes uses the third track of the working tape for auxiliary com-putations, i.e., to record in binary the elements c⁽ⁱ⁾_j , 2 ≤ i ≤ n, 1 ≤ j ≤ k, and to compute the sums s⁽ⁱ⁾_A

l, 2 ≤i ≤n, sdf_α_ηi,r₊₁, 1 ≤ r ≤k_η_i −1, 1 ≤i ≤n, and s^(n,out)_A

l ,

1≤l≤m. The inputη is accepted if all℘i, 1≤i≤n, return 1. If at least one of the above processes returns 0, thenη is rejected.

The counting procedure used by each process ℘i, 1 ≤i ≤n, is a function in the UE^∗ -uniform N C¹. The same observation holds for the summation of a constant number of vectors or multiplication of an integer of at most logn bits with a binary constant.

Hence, all the above operations can be performed by an ATM in logntime and space.

The out-degree of the computation tree at this level isn. By using a divide and conquer procedure the computation tree can be converted into a binary tree of height at most logn. Consequently, the whole algorithm requiresO(logn) time and space.

Corollary 6.9. SZM(CF)⊂ N C¹.

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

Corollary 6.10. SZM(CF)⊂DSP ACE(logn).

Let G be a context-free matrix grammar with appearance checking. When reading a symbol ηi, 1 ≤ i ≤ n, as in the proof of Theorem 6.8, an indexing ATM A cannot deduce which of the rules in F have been previously applied or not. Hence, A has to consider all possibilities of computing the net effect of a matrixmj, 1≤j≤k, occurring in the Szilard word, with respect to the policies of mj. By using a divide and conquer algorithm in [38] we proved that each language in SZM^ac(CF) can be recognized by an indexing ATM in logarithmic space and square logarithmic time, with logarithmic number of alternations between existential and universal states. Hence, we have [38]

Theorem 6.11. Each languageL∈SZM^ac(CF)can be recognized by an indexing ATM in O(log²n) time and O(logn) space, by using O(logn) alternations.

Corollary 6.12. SZM^ac(CF)⊂ AC¹.

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

Proof. The claim is a direct consequence of Theorem6.11and the well known character-ization of theAC¹ class in terms of ATM resources,AC¹=ASP ACE-ALT(logn,logn) (see Section4.2.4).

Next we strengthen this result by proving that the above class of Szilard languages is in DSP ACE(logn) [39].

Theorem 6.13. Each language L ∈ SZM^ac(CF) can be recognized by an off-line deterministic Turing machine in O(logn) space and O(nlogn) time (SZM^ac(CF) ⊂ DSP ACE(logn)).

Proof. Let G = (N, T, A₁, M, F) be a context-free matrix grammar with appearance checking. Denote by P ={p_`₁, p`2, ..., p`s} the ordered set of productions in M, where

`q is the unique label associated with the q^th production in P, and each p_`_q is a rule of the formα_`_q →β_`_q,α_`_q ∈N,β_`_q ∈(N∪T)^∗, that may belong to one or more matrices.

LetBbe an off-line deterministic Turing machine (with stationary positions) composed of an input tape that stores an input word η ∈ M^∗, η = η₁η₂...η_n, of length n, and a (read-write) working tape. For each rule p`q, B records on the working tape, the `q

symbol, the left-hand side of p_`_q (i.e., the nonterminal α_`_q), and the net effects of rule p_`_q, with respect to each nonterminal A_l ∈ N. Besides, any rule in P ∩F is marked by a symbol ]. In this way each production in mj has associated a unique label `x, and m_j can be seen as a sequence of productions of the formp_`_x, whose characteristics, i.e., the rule’s left-hand side, the net effects with respect to each nonterminal inN, and the ] symbol, can be read from the working tape. For each matrix m_j, labeled by a certain η, B also records on its working tape the (unique) sequence of rules defining m_j. In order to be readable these characteristics are separated by a special symbol. As each matrix is a finite sequence of rules, and the net effect of a rule, with respect to a certain nonterminal, does not depend on the length of the input, to record the rules’

characteristicsB requires a constant amount of time and space.

At the beginning of the computation the working tape is empty. From an initial state q0, in stationary positions, B records (in constant time) the characteristics of all rules in P. At the right-hand side of these characteristics B books m blocks, each of which is composed of O(logn) cells. These blocks are used to record, in binary, the Parikh vectors associated with sentential forms. We refer to these blocks as Parikh blocks. For the moment,B uses the first cell of each Parikh block to record the Parikh vectorV⁰ of the axiom, i.e.,V₁⁰ =V_A⁰₁ = 1 andV_l⁰=V_A⁰

l= 0, 2≤l≤m. The net effects of the rules in P and the Parikh blocks are each separated by a ⊥ symbol. Denote byq_c the state reached at the end of this procedure. ThenB continues with the next procedures.

B_η₁_,j₁: B searches for the very first rule pη1,j1 in η1 = (pη1,1, pη1,2, ..., p_η₁_,k_η

1), such that p_η₁_,j₁ rewrites the axiom. This can be done by letting B when reading η₁, pass

from stateqcto stateqη1,1, and from stateqη1,j (in stationary positions) to stateqη1,j+1,

1. This can be done by letting B, in stationary position, pass from state q_η₁_,j to stateq_η₁_,j+1,j₁ ≤j ≤j₂−1, and checking for each rulep_η₁_,j, when entering in

Suppose that up to the r^th step of derivation in appearance checking in η₁, B found a subsequence (pη1,j1, pη1,j2, ..., pη1,jr) of η1, composed of rules that can be effectively applied and that the sentential form obtained at ther^thstep of derivation inη₁ contains sdf_A^(η¹^,j^r⁾ all rules in η₁ that do not occur in `^q_η₁ are skipped because they cannot be effectively applied according to Definition 6.2. If j_ξ^q

η16=kη1, then B continues to check, by passing from stateq_η₁_,jto stateq_η₁_,j+1,j_ξ^q_η

1 ≤j≤k_η₁−1, whether rulep_η₁_,j can be passed over becauseαη1,jdoes not occur in the sentential form obtained at thej^thstep of derivation, in appearance checking, inη₁. If no such a subsequence ofη₁ can be foundηis rejected.

Suppose that all rules inη₁ can be applied in appearance checking, and at the end of the checking procedures described above B reaches the state qη1,kη1. From state qη1,kη1 B enters inq_η₂_,1, by readingη₂ = (p_η₂_,1, p_η₂_,2, ..., p_η₂_,k_η

2), and fromq_η₂_,j,Bpasses toq_η₂_,j+1,

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

j1≤j≤kη2−1, by checking, in stationary positions, whether all rules inη2can be applied in appearance checking. This can be done by consecutively applying procedures of type B_η₂_,j_r, 1≤r ≤ξη^q2, where`^qη2= (pη2,j1, pη2,j2, ..., pη2,j_ξq

η2

) is a subsequence ofη2 composed of rules that can be effectively applied. The Parikh vector of the sentential form obtained after the application of matrix η₂, in appearance checking, is recorded on the mParikh blocks. B proceeds in the same manner for each matrixηi, 3≤i≤n.

The input is accepted if, for each η_i, a policy `^qηi = (p_η_i_,j₁, p_η_i_,j₂, ..., p_η₂_,j

ξq

ηi) ofη_i can be found, such that all rules in `^qηi can be effectively applied, while rules inηi that are not in`^qηi are skipped according to Definition 6.2. Besides, for the last matrixηi, in the last stateq_η_n_,k_ηn,Balso checks whether the Parikh vector of the last sentential form contains no nonterminal, i.e., sdf_A_l=V_l⁰+Pn

i=1

P^j^ξ

qηi

r=1df_A_l(p_η_i_,j_r) = 0, for any 1≤l≤m.

Since matrix grammars work sequentially, the length of each sentential form is linearly bounded by the length of the input. Hence,O(logn) cells are enough in order to record, in binary, the number of occurrences of each nonterminalA_lin a sentential form. There-fore, the space used by B is O(logn). Because each time, reading an input symbol, B has to visit O(logn) cells in the working tape, and the constant number of auxiliary operations with binary numbers (performed at each step of derivation in G) require O(logn) time,B performs the whole computation inO(nlogn) time.

The strict inclusion ofSZM^ac(CF) inDSP ACE(logn) follows, e.g., from the existence of the languageL={pⁿ|n≥0} ∈DSP ACE(logn)−SZM^ac(CF).

The Case of Leftmost Szilard Languages

Matrix grammars are highly nondeterministic rewriting systems. First, due to the non-deterministic manner in which nonterminals can be rewritten, and second, due to the appearance checking restriction on which rules in a matrix can be passed over. The first type of nondeterminism can be reduced by imposing an order on the manner in which nonterminals are rewritten. As in the case of Chomsky grammars, the leftmost deriva-tion is the most interesting one. Next we focus on the complexity of Szilard languages associated with leftmost-i derivations, i ∈ {1,2,3}, (Definition 6.5) introduced in [60].

However, proofs provided in this section can be considered as “prototypes” for a large variety of complexity results concerning Szilard languages associated with several other types of leftmost derivations introduced in [56, 79, 188]. The second type of nonde-terminism can be avoided by omitting the appearance checking mode. For leftmost-1 Szilard languages of matrix grammars without appearance checking we have [36,38,39]

Theorem 6.14. Each language L ∈ SZM L1(CF) can be recognized by an indexing ATM in O(logn) time and space (SZM L₁(CF)⊆ALOGT IM E).

Proof. LetG= (N, T, A1, M, F) be a context-free matrix grammar without appearance checking, working in leftmost-1 derivation manner. ConsiderAan indexing ATM having a similar configuration as the one used in the proof of Theorem 6.8, and let η ∈ M^∗, η = η₁η₂...η_n, be an input word of length n. In order to guess the length of η, A proceeds with the procedure described at Level 1 (Existential), Theorem 6.8. Then A spawns (Level 2)n universal processes℘i, 1≤i≤n.

•On℘1Areadsη1= (pη1,1, pη1,2, ..., p_η₁_,k_η

1) and it checks ifαη1,1=A1 and ifsdfαη1,r+1= V_α⁰_η

1,r+1+Pr l=1df_α_η

1,r+1(p_η₁_,l)≥1, 1≤r≤k_η₁−1, i.e., whether the nonterminalα_η₁_,r+1 rewritten by the (r + 1)^th rule of η1 exists in the sentential form generated up to the r^th step of the derivation inη₁. ThenAchecks whether rules in η₁ can be applied in a leftmost-1 derivation manner.

• For each ℘_i, 2 ≤ i ≤ n, A counts the number of occurrences of each matrix m_j, 1≤j ≤k, in η⁽ⁱ⁾ =η1η2...ηi−1. Suppose that this number is c⁽ⁱ⁾_j , 0≤c⁽ⁱ⁾_j ≤i−1. For each 1 ≤ l ≤ m, A computes the sums s⁽ⁱ⁾_A

l = V_l⁰ +P_k

j=1c⁽ⁱ⁾_j V_l(m_j), i.e., A computes the number s⁽ⁱ⁾_A

l of occurrences of A_l in the sentential form upon which η_i is applied.

Consider ηi = (pηi,1, pηi,2, ..., p_η_i_,k_ηi) and αηi,1 = Aqi, 1 ≤ qi ≤ m. A checks whether s⁽ⁱ⁾_A

qi = s⁽ⁱ⁾α_ηi,1 ≥ 1, i.e., whether the matrix η_i can start the computation. For each 1 ≤r ≤kηi−1, A checks whether sdfα_ηi,r+1 =s⁽ⁱ⁾α_ηi,r+1 +Pr

l=1dfα_ηi,r+1(p_η_i_,l) ≥1, i.e., whether the rules p_η_i_,r, 2≤r ≤k_η_i, can be applied in the same order they occur in η_i. Then, A checks whether the rules in ηi can be applied in the leftmost-1 derivation manner. To do so, A checks, from right-to-left in the sequence ηi = (pηi,1, pηi,2, ..., p_η_i_,k_ηi), whether each rulep_η_i_,r, 2≤r ≤k_η_i, rewrites the first nonterminal occurring on the right-hand side of the previous rule pηi,r−1, if this is not a terminal rule. If pηi,r−1

is a terminal rule, thenA searches backwards in η⁽ⁱ⁾ =η₁η₂...ηi−1 for a matrixη_v such that there exists a non-terminal rule inηv producing the nonterminal rewritten bypηi,r. In this order,Aspawnsi−1 existential branches (Level 3) such that each branch takes a matrix η_v = (p_η_v_,1, p_η_v_,2, ..., p_η_v_,k_ηv), 1≤ v ≤ i−1. A checks whether there exists a non-terminal rule pηv,s, 1 ≤ s ≤ kηv, in ηv, such that pηv,s produces the nonterminal rewritten by p_η_i_,r. This is performed as follows.

Denote by sv the number of rules used in the derivation process between rule pηv,s of matrix η_v and rule p_η_i,r−1 of matrix η_i (including rules p_η_v_,s and p_η_i,r−1). Suppose that q of these rules (excluding p_η_v_,s) are non-terminal. Denote bys_q the total number of nonterminals produced by the q non-terminal rules. A checks whether αηi,r is the (s_v−s_q)^thnonterminal occurring on the right-hand side of rulep_η_v_,s. Note that, ifp_η_v_,sis the rule that produces the nonterminal rewritten bypηi,r, and this is the ¯r^thnonterminal occurring on the right-hand side p_η_v_,s, then for the case of leftmost-1 derivation order, we must have ¯r+sq =sv. This is because each nonterminal produced in the sentential

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

form between pηv,s and pηi,r (including nonterminals existing up to the ¯r^th nonterminal on the right-hand side ofp_η_v_,s), must be fully rewritten by these rules. The nonterminals existing in the sentential form beforepηv,s is applied, will be rewritten only after the new nonterminals produced between p_η_v_,s and p_η_i_,r are fully rewritten. For each existential branch at Level 3, such that the relation ¯r+s_q =s_v holds, A checks whether the ¯r^th nonterminal occurring inβηv,s is indeed the nonterminalαηi,r rewritten bypηi,r, i.e., no other rule used between rulep_η_v_,sof matrixη_v and rulep_η_i_,r of matrixη_i rewrites the ¯r^th nonterminalαηi,r, occurring inβηv,s (for which a relation of type “¯r+sq=sv” may also hold). In this respect A universally branches (Level 4) all symbols occurring between ηv+1 and ηi−1. There are i−v−1 such branches. On each branch holding a matrix η_l= (pη_l,1, pη_l,2, ..., p_η_l_,k_ηv),v < l < i,Asettles on a non-terminal rulepη_l,¯s, 1≤s¯≤kη_l, and it checks whether

1. α_η_l_,¯_s equalsα_η_i_,r,

2. ¯r+ ¯s_q = ¯s_v, providing thatα_η_i_,r is the ¯r^thnonterminal occurring on the right-hand side ofpηv,r, ¯sq is the number of nonterminals produced between rulespηv,s+1 and p_η_l_,¯s−1, and ¯s_v is the number of rules used betweenp_η_v_,s andp_η_l_,¯_s(excludingp_η_l_,¯_s), 3. the number of nonterminals α_η_i_,r rewritten between p_η_v_,s and p_η_l_,¯s−1 is equal to the number of nonterminalsα_η_i_,r produced between these rules, up to the ¯r^th non-terminal occurring on the right-hand side ofpηv,s (excluding the ¯r^th nonterminal).

Each universal branch (at Level 4) returns 0 if conditions 1−3 hold, and otherwise 1. If all universal branches spawned for the valuesat Level 4 return 1, then rulepηv,s (found at Level 3) is the rule that produces the nonterminal rewritten bypηi,r in the leftmost-1 derivation manner. Then the existential branch spawned at Level 3, corresponding to thesvalue, will be labeled by 1.

Each process℘i, 2≤i≤n−1, returns 1 if there exists an existential branch at Level 3, labeled by 1. Otherwise, ℘_i returns 0. The last process℘_n, returns 1 if besides, at the end of the application of matrix ηn, the sentential form contains no nonterminal, i.e., whether s^(n,out)_A

l = 0, where s^(n,out)_A

l =V_l⁰+P_k

j=1c⁽ⁿ⁾_j V_l(η_j) +V_l(η_n), 1≤l≤m.

Note that for each ℘_i, 1 ≤ i ≤ n, A does not have to check whether matrices η_v and η_l can be applied in a leftmost-1 derivation manner. If η_v and η_l do not satisfy these requirements, then the wrong logical value returned by ℘i is “rectified” by the 0 value returned by℘_v or℘_l, since all processes are universally considered.

As in Theorem 6.8, each of the above processes uses the third track of the working tape for auxiliary computations, i.e., to record in binary the elements c⁽ⁱ⁾_j , 2 ≤ i ≤ n, 1≤j≤k, and to compute the sumss⁽ⁱ⁾_A

l, 2≤i≤n,sdf_α_ηi,r₊₁, 1≤r≤k_η_i−1, 1≤i≤n, and s^(n,out)_A

l , 1 ≤ l ≤ m. It is easy to see that A performs the whole computation in logarithmic time and space.

Corollary 6.15. SZM L1(CF)⊂ N C¹.

Corollary 6.16. SZM L1(CF)⊂DSP ACE(logn).

The algorithm described in the proof of Theorem 6.14 cannot be applied in the case of leftmost-1 Szilard languages of matrix grammars with appearance checking, nor in the case of leftmost-iderivations in matrix grammars, with or without appearance checking, i ∈ {2,3}. The explanation, for the leftmost-1 derivation case, is that in the proof of Theorem 6.14, for any matrix η_i, 2 ≤ i ≤ n, A has to guess a policy of a matrix η_v that contains a non-terminal rule that produces the nonterminal rewritten by rulepηi,r

of η_i. However, even if process℘_v returns true, which means that at its turnη_v can be applied in a leftmost-1 derivation manner on η1η2...ηv−1, the process ℘i cannot “see”

with which policyηv works, since all branches (or processes) spawned at the same level of the computation tree ofAare independent on each other. Hence, the policy of matrixη_v (guessed by℘v) that provides the non-terminal rule producing the nonterminal rewritten by rule p_η_i_,r, may not work in the leftmost-1 derivation manner upon η₁η₂...ηv−1. In general, for all leftmost-iderivations in matrix grammars, i∈ {1,2,3}, with or without appearance checking, for each matrixη_j, 1≤j≤n, occurring in an input of lengthn, a Turing machine must have information concerning the order in which first occurrences of nonterminals inN occur in the sentential form at any step of derivation. To this end we introduce the notion of the ranging vector for a matrix grammar.

Informally, aranging vector associated with a sentential form, denoted bySF_`^q

j (SFp_`q j

), obtained after the policy `^q_j of a matrix mj (or, respectively, the rule p_`^q

j in `^q_j) has been applied at a certain step of derivation, provides the order of the first occurrences of nonterminals in N occurring in SF_`^q

j (SF_p

`q j

). Denote by ∂_m_j the (finite) number of policies of matrixmj. By defining an order on these policies we can uniquely label them.

Thus, to theq^th policy of matrix m_j, we associate the label`^q_j, 1≤q≤∂_m_j, 1≤j≤k.

Formally we have [39]

Definition 6.17. Let G = (N, T, A1, M, F) be a matrix grammar with appearance checking andw∈(N∪T)^∗. The ranging vector associated with a wordw, denoted by RV(w), with respect to the set of nonterminals N, is a vector inN^m defined as

RV_l(w) = order of first occurrences of nonterminals fromN inw.

We denote byRV(SF_`^q

j) (RV(SF_p

`q j

)) theranging vector associated with the sentential formSF_`^q

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

) in which the order of the first occurrences of nonterminals is provided by RV(SF_`^q

j) (RV(SFp_`q j

)), while substrings (denoted by small letters, see Example 6.1), occurring between the first occurrences of nonterminals inN are strings in (N ∪T)^∗. Note that if matrix m_j⁰, with the policy `^q_j0, is applied before matrix m_j, with the policy `^q_j, then RV(SF_`^q

j) can be nondeterministically computed knowing RV(SF_`^q

j0) (Example6.1), for all leftmost-i,i∈ {1,2,3}, derivations. Next we give an example for the letfmost-2 derivation case.

Example 6.1. Consider RV(SF_`^q

j0) = (4,1,3,2,0)∈N⁵ the ranging vector associated with the sentential form SF_`^q

j0, obtained after the policy `^q_j0 of matrix m_j⁰ has been applied, at the i^th step of derivation, such that SF_`^q

In document Advanced Studies on the Complexity of Formal Languages (sivua 121-136)