A Parallel Version of Earley’s Algorithm^{∗}

Danilo Bruschi  Giovanni Pighizzini

Dipartimento di Scienze dell’Informazione Università degli Studi Via Comelico 39, 20135 Milano – ITALY

          {bruschi,pighizzi}@imiucca.csi.unimi.it

TECH. REP. 114–94

Abstract

In the world of sequential computation the most referenced algorithms for recognizing context–free languages are the CYK algorithm introduced in 1963 by Cocke, Younger and Kasami, and Earley’s algorithm introduced in 1970. The former only deals with grammars in Chomsky normal form while the latter deals with every context–free grammar.

When in early 70’s people started investigating parallel algorithms, immediately it appeared that obtaining efficient parallel parsers was not easy. In fact in 1977 Jones et al. [JL77] proved that the construction of a context–free recognizer is a P–complete problem.

In [Ruz80, Ryt86] however Ruzzo and Rytter showed that when we restrict our attention to context–free grammars in Chomsky normal form, the P– completeness result just mentioned can be overcome. In fact a parallel version of CYK can be obtained using Ruzzo and Rytter results.

On the other hand, Jones et al. result seems to deny the possibility of having a “parallel equivalent” of Earley’s algorithm.

In this paper we show that this consideration is not true. More precisely we will show how to obtain a parallel algorithm for recognizing a language specified by a whatever context–free grammar. Using such an algorithm we will further describe a parallel algorithm for the parsing phase. To our knowledge these are the first parallel algorithms which solve such problems.

∗This work was supported in part by the ESPRIT Basic Research Action No. 6317: “Algebraic and Syntactic Methods in Computer Science (ASMICS 2)” and by the Ministero dell’Università e della Ricerca Scientifica e Tecnologica (MURST).

1 Introduction

In 1963 Cocke, Younger and Kasami independently discovered the first polynomial time algorithm (hereafter called CYK) for recognizing context–free languages (see [AU72] for a detailed description). But CYK has a limitation: it only deals with grammars in Chomsky normal form. We briefly recall that even if every context– free grammar can be efficiently transformed into an equivalent grammar in Chomsky normal form, such a transformation is quite unfair when the recognition process is followed by a parsing phase. In fact the parse tree which can be generated by a transformed grammar has very few resemblances to the parse tree related to the original grammar. Thus, for example, recovering correct semantic actions from the parse tree related to a transformed grammar is a very, if not impossible, hard task.

The problem of defining a recognizer and hence a parser which was able to deal with general context–free grammars was solved in 1970 by Earley [Ear70] with the introduction of a new recognizing algorithm obtained as an extension of Knuth’s LR(k) method [Knu65]. For its generality Earley’s algorithm is much more referenced than CYK especially for designing parsing algorithms for applications in which programming languages are not directly involved such as natural language processing [Tom85] and speech recognition [LS74].

At this point it is important to recall the attention of the reader on the following fact. Both CYK and Earley’s algorithms are uniform with respect to the grammar, this means that the recognition process which they perform is not bounded to an a priori known grammar, but is designed for working with grammars which can be part of the input.

In early 70’s with the diffusion of the first models of parallel computation people started investigating parallel algorithms. Quite soon, however, it appeared that the task of building parallel algorithms for recognizing context–free languages was not easy. In fact in 1977 Jones et al. [JL77] proved that the problem of the uniform recognition of context–free languages is P–complete [KR90], thus quite hardly parallelizable.

In 1980 however Ruzzo showed that when we restrict our attention to grammars in Chomsky normal form the P–completeness result could be overcome. In fact in [Ruz80] he described a parallel recognizer which can be executed on a CRCW PRAM in time O(log n) where n is the length of the input string. Subsequently, Rytter [Ryt86] referring to Ruzzo’s result showed how to build a parallel parser for context–free grammars in Chomsky normal form.

Essentially Ruzzo and Rytter results lead us to a parallel version of CYK; on the other hand, Jones et al. result seems to deny the possibility of having a “parallel equivalent” of Earley’s algorithm.

In this paper we show that this consideration is not true. In fact we show that if we renounce to the possibility of having a uniform recognizer, i.e., to the possibility of specifying the grammar in the input, then we can have a parallel algorithm for recognizing each kind of context–free grammar. More precisely, combining some revisited sequential versions of Earley’s algorithm [GHR80, Kil85, Lei90] with parallel tree contraction techniques recently introduced in the theory of parallel algorithms [MR85, MRK88], we will build a parallel recognizer which works for every fixed but arbitrary context–free grammar. Using such an algortihm we will further show how to derive a parallel algorithm for parsing a generic context–free grammar.

The paper is organized as follows. In Section 2 we introduce notations and notions used throughout the paper. For ease of exposition initially we will consider context–free grammars with no unit and ϵ–productions. In particular in Section 3 we show a parallel recognizer for such grammars. Since a recognizer is generally simpler than a parser, this will permits us to better illustrate some general concepts required for the parallel parser design. In Section 4 we will prove the correctness of the algorithm presented in Section 3. In Section 5, we will show how to derive a parallel parser from the recognizer constructed in Section 3. Finally in Section 6 we describe how the parser so constructed can be extended to context–free grammars with both unit and ϵ–productions.

2 Preliminary definitions

We assume that the reader is familiar with notions and formalisms from formal language theory as reported in [HU79]. A context–free grammar G will be denoted by (V, Σ, P, S), where V is the set of variables or nonterminal, Σ is the set of terminal symbols, P is the finite set of productions, and S is the start symbol. We will suppose that the sets V and Σ are disjoint. Throughout the paper, variables from V will be denoted by the capital letters A, B, C, …, terminal symbols by the lower case letters a, b, c, …, strings from (V ∪ Σ)^{∗} by the greek letters α, β, γ, . . .. ϵ will denote the empty string. Given a production (A → αβ) ∈ P, a dotted rule is a string A → α·β, where · ∉ V ∪ Σ. The only dotted rule corresponding to the ϵ–production A → ϵ will be denoted by A → ·. α ⇒^{∗} β (α derives β) will denote the fact that β follows from α by zero or more applications of some productions of P. The number of these applications is called the length of the derivation.

The language generated by a grammar G will be denoted by L(G) or L if G is understood. A recognizer is a procedure which accepts those strings in L(G) and rejects all others. A parser is a recognizer which additionally outputs a parse tree or a derivation of each accepted input. It is convenient to fix n ≥ 1, and to fix the input string to be parsed as x = x_{1} … x_{n}, x ≠ ϵ, x_{i} ∈ Σ, i = 1, …, n.

Our model of parallel computation is a parallel random–access machine with both concurrent read and concurrent write, (CRCW PRAM)[KR90]. Such a machine consists of several independent sequential processors, each with its own private memory. Communication among processors is through shared memory. In one unit of time, each processor can read one global or local memory location, execute a single RAM instruction, and write into one global or local memory location. In our particular case simultaneous write are allowed, and write conflicts are solved assuming that all processors writing into the same location must write the same value (the COMMON model).

3 The recognizer

In designing our algorithm, the main difficulty to overcome has been that of finding a strategy for recognizing in parallel general context–free grammars. This section is dedicated to illustrate the method we have devised for designing such an algorithm. In describing our algorithm we will refer to Earley’s algorithm as presented in [Lei90]. Initially we will give an informal description of the algorithm; subsequently it will be formalized using a Concurrent Pascal like language.

Given a context–free grammar G = (V, Σ, P, S), our algorithm performs the recognition of an input string x, |x| = n, by considering items of the form (A → α · β, i, j), where A → αβ ∈ P, 0 ≤ i ≤ j ≤ n, and identifying among them realizable items. An item I = (A → α · β, i, j) is said to be realizable if and only if α ⇒^{∗} x_{i+1} … x_{j}.^{1} So, the algorithm accepts the input string x if and only if there is a production S → α such that the item (S → α·, 0, n) is realizable.

Realizable items can be computed sequentially as follows. Initially all items of the form (A → ·β, i, i) are marked as realizable. Subsequently new items are marked as realizable using the following operations:

1. scan: if x_{j} = a and (A → α · aβ, i, j − 1) is realizable then (A → αa · β, i, j) becomes realizable;

2. complete: if both items (A → α · Bβ, i, k) and (B → γ·, k, j) are realizable, then the item (A → αB · β, i, j) becomes realizable.

Intuitively the scan operation augments the portion of a production recognized within an item when there is a matching between the first symbol of the portion of the production not yet recognized, and the next input symbol. The complete operation links together adjacent portions of the input string which have been recognized. We will now show how to parallelize such operations. The hardest part in such a task is the parallelization of the operation complete,^{2} which we have realized referring to partial evaluation techniques [Ruz80, Ryt85, MR85, MRK88].

1Intuitively the dot in a realizable item indicates the portion of the right part of the production recognized so far.

2Note that a trivial parallelization of such an operation, obtained considering in parallel all triples of items I = (A → α · Bβ, i, k), J = (B → γ·, k, j) and K = (A → αB · β, i, j) and marking the item K as realizable if both items I and J are realizable, is not efficient. For example with such a parallel implementation, the complete operation would require linear time when working on the grammar with the following productions S → AS, S → A, A → a.

More precisely, the algorithm we have devised, works in the following way. Given the grammar G, it starts considering a completely unconnected graph whose nodes are all possible items; during its execution the algorithm “draws” arcs between items and marks as realizable some of these items.

An arc (I, J) is drawn from item I to item J according to the following rules:

1. parallel scan: for all integers i, j, 0 ≤ i ≤ j ≤ n, do in parallel: if x_{j} = a then connect (A → α · aβ, i, j − 1) to (A → αa · β, i, j);

2. partial complete: for each node in the graph do in parallel: if (A → α · Bβ, i, k) is realizable then connect (B → γ·, k, j) to (A → αB · β, i, j); if (B → γ·, k, j) is realizable then connect (A → α · Bβ, i, k) to (A → αB · β, i, j).

Note that if the arc (I, J) exists then the realizability of I implies the realizability of J. Thus, if after the arc (I, J) has been drawn, the algorithm will mark the item I as realizable, then also the item J will be marked as realizable (this step will be performed by the operation mark defined later). Note also that when both the arcs (I, J) and (J , K) have been “drawn”, then also the arc (I, K) can be added. Thus, we introduce besides the operations just defined the additional operation square which computes transitive arcs of the graph.

Nodes are marked as realizable according to the following rules:

1. parallel predict: for each integer i, 0 ≤ i ≤ n, do in parallel: mark as realizable all items of the form (A → ·β, i, i);

2. mark: for each item I do in parallel:

if I is realizable then mark as realizable all items connected to I.

It is not difficult to see that the operations parallel predict and parallel scan can be executed only once, at the start of the recognition process, while we will show that the operations partial complete, square and mark have to be executed a logarithmic (in the length of the input) number of times in order to get a correct result.

The reader acquainted with parallel tree contraction techniques should have recognized the strong analogy between the procedures Rake and Compress introduced in [MR85] or the procedures MM, Eval_{+} and Eval_{×} introduced in [MRK88] and our operations partial complete, square and mark. In fact, square is a compression operation, while the operations partial complete and mark “remove leaves”.

A brief example will now illustrate how the algorithm works. Suppose we have to recognize the input string x = a + a ∗ a, with respect to the grammar G, whose variables are E, T, P, whose terminal symbols are a, +, ∗, whose start symbol is E, and whose productions are:

\begin{matrix}E → T \\ E → E + T \\ T → P \\ T → T ∗ P \\ P → a \end{matrix}

In the first step of the algorithm the following items are marked as realizable, by the parallel predict operation, for i = 0, …, 5:

\begin{matrix}(E → ·T, & i, & i) \\ (E → ·E + T, & i, & i) \\ (T → ·P, & i, & i) \\ (T → ·T ∗ P, & i, & i) \\ (P → ·a, & i, & i). \end{matrix}

Subsequently the operation parallel scan draws the following arcs:

((P → ·a,  0, 0), (P → a·,  0, 1))
((E → E · +T, i, 1), (E → E + ·T, i, 2)), i = 0, 1
((P → ·a, i, 2), (P → a·, i, 3)), i = 0, 1, 2
((T → T · ∗P, i, 3), (T → T ∗ ·P, i, 4)), i = 0, 1, 2, 3
((P → ·a,  i, 4), (P → a·,  i, 5)), i = 0, 1, 2, 3, 4

At this point the algorithm starts iterating the sequence of operations partial complete, square and mark. In the first of such iterations the following arcs are added by the partial complete operation, for 0 ≤ i ≤ j ≤ 5:

\begin{matrix}((T → P ·, & i, & j), & (E → T ·, & i, & j)) \\ ((T → T ∗ P ·, & i, & j), & (E → T ·, & i, & j)) \\ ((E → T ·, & i, & j), & (E → E · +T, & i, & j)) \\ ((E → E + T ·, & i, & j), & (E → E · +T, & i, & j)) \\ ((P → a·, & i, & j), & (T → P ·, & i, & j)) \\ ((T → P ·, & i, & j), & (T → T · ∗P, & i, & j)) \\ ((T → T ∗ P ·, & i, & j), & (T → T · ∗P, & i, & j)); \end{matrix}

while the following items are marked as realizable by the operation mark:

\begin{matrix}(P → a·, & 0, & 1) \\ (P → a·, & 2, & 3) \\ (P → a·, & 4, & 5) \end{matrix}

In the second iteration of the algorithm, the items

\begin{matrix}(E → E · +T, & 0, & 1) \\ (E → E + ·T, & 0, & 2) \\ (T → T · ∗P, & 2, & 3) \\ (T → T ∗ ·P, & 2, & 4) \\ (T → T ∗ P ·, & 2, & 5) \end{matrix}

are marked as realizable by the operation mark. Moreover, in the third iteration also the item (E → E + T ·, 0, 5) is marked as realizable, thus proving the membership of x to L(G).

In summary, the algorithm we have just outlined can be described in the following way.

Algorithm 1

begin

(1) parallel predict

(2) parallel scan repeat O(log n) times

begin

(3) partial complete

(4) square

(5) mark end

(6) answer end

The operations contained in the algorithm can formally be defined in the following way. Consider two boolean arrays R and Z. At the start of the computation all components of R and Z are initialized to false. The first array is indexed by items and it is used to mark them as realizable, i.e., at every step of the computation R(I) = true if and only if the item I has been marked as realizable. The array Z is a two–dimensional array indexed by items and used as adjacency matrix of the graph which the algorithm constructs during its execution. In particular Z(I, J) = true if and only if an arc has been drawn connecting item I to item J. The algorithm accepts the input string x if and only if at the end of the computation a boolean variable output contains the value true.

• parallel predict for all (A → ·β, i, i) in parallel do R(A → ·β, i, i) := true

• parallel scan

for all (A → αa · β, i, j) in parallel do if x_{j} = a then Z((A → α · aβ, i, j − 1), (A → αa · β, i, j)) := true

• partial complete for all (A → α · Bβ, i, k) and for all (B → γ·, k, j) in parallel do begin

if R(A → α · Bβ, i, k) then Z((B → γ·, k, j), (A → αB · β, i, j)) := true if R(B → γ·, k, j) then Z((A → α · Bβ, i, k), (A → αB · β, i, j)) := true

end • square

for all I, J , K in parallel do if Z(I, J) and Z(J , K) then Z(I, K) := true

• mark for all I, J in parallel do if Z(I, J) and R(I) then R(J) := true

• answer

output := false

for all I = (S → α·, 0, n) in parallel do if R(I) then output := true

4 Correctness proof and complexity analysis

In this section we will show that given a context–free grammar G, Algorithm 1 recognizes exactly all strings x ∈ L(G), in time O(log n) using at most O(n^{6}) processors.

The proof that every string accepted by the algorithm belongs to L(G) is quite immediate, the proof of the opposite implication is instead much more involved. We realized such a proof referring to the notion of path system introduced by Cook in [Coo70] and using the balanced divide–and–conquer technique introduced by Gurari and Ibarra in [GI80].

Lemma 4.1 After every step of Algorithm 1 the following assertions hold:

(i) for all items I = (A → α · β, i, j) and J = (C → γ · δ, p, q), if J is connected to

I, i.e., Z(J , I) = true, then i ≤ p ≤ q ≤ j and α ⇒^{∗} x_{i+1} … x_{p}γx_{q+1} … x_{j};

(ii) for every item I = (A → α · β, i, j), if (A → α · β, i, j) is realizable, i.e.,

R(I) = true, then α ⇒^{∗} x_{i+1} … x_{j}.

Proof. Statement (i) trivially holds if the value true is assigned to Z(J , I) in step (2) of Algorithm 1. It is also clear that (ii) holds if the value true is assigned to R(I) in step (1).

Consider now two items I, J and assume that for such items (i) and (ii) hold before the execution of steps (3), (4) and (5). The following cases have to be considered.

• Z(J , I) becomes true executing step (3); this can happen only when

1. I = (A → αB · β, i, j), J = (B → γ·, k, j) and R(K) = true, where K = (A → α · Bβ, i, k). By (ii) this implies α ⇒^{∗} x_{i+1} … x_{k} and then

αB ⇒^{∗} x_{i+1} … x_{k}B ⇒ x_{i+1} … x_{k}γ.

2. I = (A → αB · β, i, j), J = (A → α · Bβ, i, k) and R(K) = true, where K = (B → γ·, k, j). By (ii) this implies γ ⇒^{∗} x_{k+1} … x_{j} and then

αB ⇒ αγ ⇒^{∗} αx_{k+1} … x_{j}.

• Z(J , I) becomes true executing step (4). This case can be easily verified.

• I = (A → α · β, i, j) is marked as realizable executing step (5). This implies that there exists an item J = (C → γ · δ, p, q) for which Z(J , I) and R(J)

hold. Thus, α ⇒^{∗} x_{i+1} … x_{p}γx_{q+1} … x_{j} and γ ⇒^{∗} x_{p+1} … x_{q}. Then, we can

conclude that α ⇒^{∗} x_{i+1} … x_{j}.

As a consequence of the statement (ii) of previous lemma, it is immediate to conclude that every string x accepted by Algorithm 1 belongs to the language L(G). The converse result is more complicated. To prove it we need the preliminary notion of recognition tree.

Definition 4.1 Given a context–free grammar G = (V, Σ, P, S) and an input string x = x_{1} … x_{n}, x_{i} ∈ Σ, a partial recognition tree of x is a binary tree, whose nodes are labeled either with items or with pairs (a, j) ∈ Σ × {1, …, n} such that:

1. the label of an internal node is an item I = (A → α · β, i, j), with α ≠ ϵ; the label of its left son is J and the label of its right son is K, where:

• if α = α′B, with B ∈ V, then J = (A → α′ · Bβ, i, k) and K = (B → γ·, k, j), for some k, i ≤ k ≤ j, and B → γ ∈ P;

• if α = α′a, with a ∈ Σ, then j > i, a = x_{j}, J = (A → α′ · aβ, i, j − 1) and K = (a, j);

2. the labels of the leaves are items of the form (A → ·α, i, i) and, from left to right, the pairs (x_{p+1}, p + 1), …, (x_{q}, q), 0 ≤ p ≤ q ≤ n.

A recognition tree of x is a partial recognition tree whose root is labeled with an item (S → α·, 0, n), for some production S → α. The number of nodes of a partial recognition tree T will be denoted by η(T).

We underline that while parse trees describe the syntactical structure of sentences of a language L(G) with respect to the grammar G, recognition trees are related, as we will show in the following, to the recognition process performed by Algorithm 1.

A recognition tree of the string x = a + a ∗ a, with respect to the grammar G considered in the previous section, is represented in Figure 1.

Note that for grammars G which are not cycle–free, i.e., grammars which contain a derivation of the form A ⇒^{+} A for some variable A, the number of recognition trees related to some string x ∈ L(G) can be unbounded. However next theorem shows that even if a string x belonging to L(G) has infinitely many recognition trees, it has at least one recognition tree whose number of nodes is linear in the length of x.

[figure: (E→·E+T,0,0); (E→·T,0,0); (E→E·+T,0,1); (T →·P,0,0); (E→T ·,0,1); (E→E+·T,0,2); (P →·a,0,0); (T →P ·,0,1); (P →a·,0,1); (+,2); (a,1); (T →·T ∗P,2,2); (E→E+T ·,0,5); (T →·P,2,2); (T →T ·∗P,2,3); (P →·a,2,2); (T →P ·,2,3); (T →T ∗·P,2,4); (P →a·,2,3); (∗,4); (T →T ∗P ·,2,5); (a,3); (P →·a,4,4); (P →a·,4,5); (a,5)]

Figure 1: a recognition tree of the string x = a + a ∗ a

Theorem 4.1 Given a context–free grammar G = (V, Σ, P, S), for every string x = x_{1} … x_{n}, x_{k} ∈ Σ, k = 1, …, n, and for every item I = (A → α · β, i, j), if α ⇒^{∗} x_{i+1} … x_{j} then there exists a partial recognition tree T of x, with root labeled I and whose number of nodes is O(j − i).

Proof. Given an item I = (A → α · β, i, j), let τ(I) be the length of a shortest derivation α ⇒^{∗} x_{i+1} … x_{j}. Then, we define the rank of I as rank(I) = τ(I)+j−i+1.

First, we prove that for every item I = (A → α · β, i, j), if α ⇒^{∗} x_{i+1} … x_{j} then there exists a partial recognition tree T of x, whose root is labeled I and such that η(T) < 2rank(I). The proof is by induction on rank(I).

Basis. If rank(I) is 1 then j = i and α = ϵ; the partial recognition tree T contains only one node labeled (A → ·β, i, i), and η(T) = 1.

Induction Step. Let I be an item with rank(I) > 1. First, observe that in this case if α = ϵ then j > i so α cannot generate the string x_{i+1} … x_{j}. Thus we will only consider α ≠ ϵ. Two cases arise, depending on whether α ends in a terminal or ends in a variable.

Case 1: α = α′a for some a ∈ Σ. Since α ⇒^{∗} x_{i+1} … x_{j}, we have a = x_{j}, and α′ ⇒^{∗} x_{i+1} … x_{j−1}. Consider the item I′ = (A → α′ · aβ, i, j − 1). We have rank(I′) = rank(I) − 1. By induction hypothesis, there exists a partial recognition tree T′ with root labeled I′ such that η(T′) < 2rank(I′). Consider the tree T with root labeled I, left subtree T′ and right subtree the only node labeled (a, j). It is not difficult to see that T is a partial recognition tree satisfying our requirements.

Case 2: α = α′B for some B in V. There is some k, i ≤ k ≤ j, such that

α′ ⇒^{∗} x_{i+1} … x_{k} and B ⇒^{∗} x_{k+1} … x_{j}. Consider the item I′ = (A → α′ · Bβ, i, k).

Then, τ(I′) < τ(I) and rank(I′) < rank(I). By induction hypothesis, we can find a recognition tree T′ with root labeled I′ such that η(T′) < 2rank(I′). Let B ⇒ γ be the first step in one of the shortest derivation of B ⇒^{∗} x_{k+1} … x_{j}, and let I′′ be the item (B → γ·, k, j). Then τ(I) = τ(I′) + τ(I′′) + 1 and rank(I′′) < rank(I). By induction hypothesis, there exists a partial recognition tree T′′ with root I′′ and η(T′′) < 2rank(I′′). The tree T with root I, left subtree T′ and right subtree T′′ is a partial recognition tree of x_{i+1} … x_{j}, moreover η(T) = η(T′) + η(T′′) + 1. Then, since η(T′′) + 1 ≤ 2rank(I′′), we obtain η(T) < 2rank(I′) + 2rank(I′′) = 2rank(I). This completes the induction. For concluding the proof we recall that for every context–free grammar G there exists a constant c such that if a string y ≠ ϵ can be derived from a variable A, then there exists a derivation A ⇒^{∗} y of length at most c|y|. The value of the constant c can be found in [Sip82].

Let I be the item (A → α · β, i, j) with i ≠ j, and T the partial recognition tree with root labeled I obtained using the previous induction. Then, we have τ(I) ≤ c(j − i). This permit us to conclude that η(T) = O(j − i).

We point out that if a recognition tree T of a string x contains two nodes v and z marked with the same item I, then z must be a descendant of v (or vice versa). Thus, the tree T′ obtained from T substituting the subtree rooted at v with the subtree rooted at z is also a recognition tree of x. In this way, given a string x ∈ L(G), it is always possible to find a recognition tree whose nodes are all differently labeled. It is possible to verify that this property holds for the recognition tree constructed in the proof of Theorem 4.1. Then, from this point on, we only consider recognition trees such that all the labels of nodes are different. This will permit us of identifying every node with its label and of writing the node I instead than the node whose label is I.

The next theorem is crucial in order to prove the correctness of Algorithm 1. Its proof is obtained referring to the following lemma and using the balanced divide– and–conquer technique introduced in [GI80] for evaluating path systems.

Lemma 4.2 [Ruz80] Let T be a tree having z > 3 nodes, with each node having at most two descendants. Then there is a node s in T such that z/12 < z_{1}, z_{2} ≤ 11z/12, where z_{1} is the number of descendants of s (including s), and z_{2} is the number of nodes which are not proper descendants of s (again including s, so z_{1} + z_{2} = z + 1).^{3}

In the following, given a partial recognition tree T, a node I of T and a descendant J of I, we will denote by T (I) the subtree of T whose root is I and which contains all descendants of I in T, and by T (I, J) the tree obtained removing from the tree T (I) all descendants of J (except J).

Theorem 4.2 Let x be a string belonging to L(G), where G is some fixed context– free grammar, and let T be a recognition tree of x. Given an item I, if I is a node of T then the following statements hold:

(1) Algorithm 1 set to true R(I) within 3 log_{12/11} η(T (I)) iterations; (2) for every item J, I ≠ J, if J is a descendant of I in T, then Algorithm 1 sets

3Observe that the node s cannot be the root or a leaf of T.

to true Z(J , I) within 3 log_{12/11} η(T (I, J)) iterations.

Proof. By induction on the number z of nodes of the trees.

Basis (z ≤ 3). First, we prove (1). If η(T (I)) = 1 then I is a leaf of the form (A → ·β, i, i) and true is assigned to R(I) by the operation parallel predict, without any iteration. We observe that there are no recognition trees with an even number of nodes. Then, the next case we have to consider is η(T (I)) = 3. In this case I has the form (A → a · β, i − 1, i) and its sons are the nodes (A → ·aβ, i − 1, i − 1) and (a, i). We observe that true is assigned to R(A → ·aβ, i − 1, i − 1) and to Z((A → ·aβ, i − 1, i − 1), (A → a · β, i − 1, i)) by the operations parallel predict and parallel scan, respectively. Then, in the first iteration, the instruction mark assign true to R(A → a · β, i − 1, i).

For proving (2) the only case we have to consider is η(T (I, J)) = 3. In this case the root I of T (I, J) has two sons J and K where K is a leaf of T. If K is the right son of I then K is of the form (a, i) and then Z(J , I) is set to true by parallel scan. Otherwise, K has the form (A → ·β, i, i), trueis assigned to R(K) by parallel predict and then, in the first iteration, the operation partial complete sets Z(J , I) to true.

Induction Step. Let be z = η(T (I)). By Lemma 4.2, there exists a node K of T (I) such that both trees T (I, K) and T (K) have at most 11z/12 nodes. Of course, I ≠ K. Then, by induction hypothesis, it turns out that within 3 log_{12/11}(11z/12) = 3 log_{12/11} z − 3 iterations of Algorithm 1, both Z(K, I) and R(K) become true. In the next iteration, the operation mark will set to true the value of R(I). This proves (1).

Suppose now z = η(T (I, J)). By Lemma 4.2, it turns out that there exists a node K of T (I, J), K ≠ I, K ≠ J, such that both the subtree of T (I, J) rooted at K and the tree obtained by deleting from T (I, J) all proper descendants of K have at most 11z/12 nodes. Now, two cases arise depending on whether J is or is not a descendant of K.

J is a descendant of K. In this case the tree T (I, J) can be split in the two trees T (I, K) and T (K, J) each containing at most 11z/12 nodes. As in the proof of (1), using the induction hypothesis, we can conclude that within 3 log_{12/11} z − 3 iterations both variables Z(K, I) and Z(J , K) become true. Thus, in the subsequent iteration, the operation square will set to true the value of Z(J , I).

J is not a descendant of K. Let I′ be the first (from the leaves to the root) common predecessor of J and K, and denote by J′ the son of I′ on the path from I′ to J and by K′ the son of I′ on the path from K′ to K (see Figure 2). Consider now the trees T (K), T (K′, K), T (J′, J) and T (I, I′). Again, by Lemma 4.2 all these trees have at most 11z/12 nodes. Then, by induction hypothesis, after 3 log_{12/11} z−3 iterations of Algorithm 1, all variables R(K), Z(K, K′), Z(J , J′) and Z(I′, I) will contain the value true.

[figure: J; K; J′; K′; I′; I]

Figure 2: decomposition of the tree T (I, J).

In the iteration the operation mark will set R(K′) to true, in the following one the operation partial complete sets to true Z(J′, I′), and the operation square sets to true Z(J′, I). Finally, with another iteration Z(J , I) is set to true by the operation square. Thus, within 3 log_{12/11} z iterations, Z(J , I) becomes true.^{4}

Theorem 4.3 Given a context–free grammar G, Algorithm 1 decides the membership to L(G) of an input string x, of length n, in time O(log n) using O(n^{6}) processors on a CRCW PRAM.

Proof. First, we observe that as an immediate consequence of Lemma 4.1, every string accepted by Algorithm 1 belongs to L(G). Now, we prove the converse. Let be x ∈ L(G), then, by Theorem 4.1 there exists a recognition tree T with O(|x|) nodes. Applying Theorem 4.2, it turns out that after O(log |x|) iterations, Algorithm 1 is able to assign the value true to the item labeling the root of T. Then x is accepted.

The most expensive steps contained in Algorithm 1 correspond to the operations partial complete and square, which in parallel work on all triples of items. Since the number of items is O(|x|^{2}), the number of processors required by such operations is O(|x|^{6}).

4This part of the proof suggests some improvements to Algorithm 1. In fact, if in every iteration the sequence of operations partial complete; square; mark is substituted by the sequence mark; partial complete; square; square, then the constant 3 of the Theorem can be replaced by 1.

Moreover, the basis of the logarithm can be increased using more accurate decompositions of trees than the one given by Lemma 4.2 (see for example [GI80]). However, since in this paper we are mainly interested in the asymptotical complexity of the algorithm, we do not deepen into these considerations.

5 The parser

Given the recognizer shown in Section 3, the construction of a general parser is relatively easy. In particular, for such a task we propose a generalization of a method introduced in [Ryt86] for grammars in Chomsky Normal Form.

The parser can be divided in two phases. In the first phase, given the input string x, and the array R “constructed” by the recognizer, we build a recognition tree for x; subsequently from such a recognition tree, a parse tree is recovered.

5.1 Construction of the recognition tree

In order to obtain a recognition tree for x from the array R computed by the recognizer, first we build a directed acyclic graph G = (V, E). The vertex set V of this graph is the union of the set of all realizable items with the set {(x_{i}, i) | i = 1, …, n}. The set E of arcs is computed using the following algorithm:

Algorithm 2

begin

for all items I = (A → α · β, i, j) in parallel do if α ≠ ϵ and R(I) = true then begin

select a “possible pair” (J , K) of sons^{5} of I s.t. R(J) = true and if K is an item then R(K) = true E(J , I) := 1 E(K, I) := 1

end end

Given the grammar G = (Σ = {a, b}, V = {S, B}, P, S), where the set P contains the productions S → Sa, S → aB, B → Ba, B → b, a graph G computable using Algorithm 2 is represented in Figure 3.

The following general statements hold:

Lemma 5.1 The graph G above defined, related to a grammar G which does not contain ϵ–productions and unit productions, is acyclic.

Proof. First, we remark the following facts.

5(J , K) is a “possible pair” of sons of I when (J , K) can be a pair of sons of I in some recognition tree according to Definition 4.1, i.e., either I = (A → α′B · β, i, j), J = (A → α′ · Bβ, i, k), K = (B → γ·, k, j), for some i ≤ k ≤ j, B → γ ∈ P, or I = (A → α′x_{j} · β, i, j), J = (A → α′ · x_{j}β, i, j − 1), K = (x_{j}, j).

[figure: (S→·aB,0,0)^{⋆}_{•}; (a,1)^{⋆}_{•}; (B→·b,1,1)^{⋆}_{•}; (b,2)^{⋆}_{•}; (S→a·B,0,1)^{⋆}_{•}; (B→b·,1,2)^{⋆}_{•}; (S→·Sa,0,0)^{⋆}; (S→aB·,0,2)^{⋆}; (B→B·a,1,1)_{•}; (S→S·a,0,2)^{⋆}; (a,3)^{⋆}_{•}; (B→B·a,1,2)_{•}; (S→·aB,2,2); (S→Sa·,0,3)^{⋆}; (B→Ba·,1,3)_{•}; (S→a·B,2,3); (S→S·a,0,3); (B→·Ba,1,1); (S→aB·,0,3)_{•}; (B→B·a,1,3)]

Figure 3: the graph G. ^{⋆} indicates the nodes belonging to the recognition tree with root (S → Sa·, 0, 3), while _{•} indicates the nodes belonging to the recognition tree with root (S → aB·, 0, 3). The nodes corresponding to items of the form (A → ·β, i, i) without connections are not represented.

(1) Every item of the form (B → γ·, j, j) cannot be a node of a recognition tree. In fact, every item labeling a node of a recognition tree is realizable; so if (B → γ·, j, j) is a node of a recognition tree then B ⇒^{∗} ϵ. This is not possible since G does not contain ϵ–productions.

(2) If the graph G contains a path from an item I = (A → α · β, i, j) to an item I′ = (A′ → α′ · β′, i′, j′), then i ≥ i′ and j ≤ j′. This fact can be easily proved as a consequence of the definition of recognition tree.

Consider now a generic item I = (A → α · β, i, j). If α = ϵ then there are no arcs entering in I. So, I cannot belong to a loop. Suppose now that α ≠ ϵ. We have to consider two cases, depending on whether α ends with a terminal symbol or with a variable.

(a) Suppose α = α′x_{j}, α′ ∈ (V ∪ Σ)^{∗}. In this case Algorithm 2 chooses J = (A → α′ · x_{j}β, i, j − 1) and K = (x_{j}, j) as sons of I. Using (2) it is immediate to see that in this case there are no paths from I to J in G, thus I does not belong to a loop.

(b) Suppose now α = α′B, for some α′ ∈ (V ∪ Σ)^{∗}, B ∈ V, when the nodes selected by Algorithm 2 as sons of I have the following form: J = (A → α′·Bβ, i, k), K = (B → γ·, k, j), i ≤ k ≤ j, B → γ ∈ P.

From (1), it turns out that k < j. Thus, there are no paths from I to J in G. Now, we consider the item K. By (2), there are no paths from I to K when i < k. We show that this also happens when i = k, i.e. K = (B → γ·, i, j). If γ terminates with a terminal symbol, the considerations used in (a) have to be applied. When γ = γ′B, B ∈ V, node K has two sons J′ = (B → γ′ · B′, i, h) and K′ = (B′ → δ·, h, j). By (1), it must be h < j, thus I ≠ J′. Moreover, recalling that the grammar does not contain unit productions (then |γ′| ≥ 1) and ϵ–productions (then γ′ does not generate the empty string), we obtain i < h. Thus, I ≠ K. We can conclude that there are no paths from I to K, and so there are no loops in G which contain the node I.

Lemma 5.2 There exists a subgraph of G which is a recognition tree of x.

Proof. By construction of G, for every item I = (A → α · β, i, j), with R(I) = true and α ≠ ϵ, there are exactly two arcs (J , I) and (K, I) entering in I, where (J , K) is a pair of “possible sons” of I according to the definition of recognition tree. Since by Lemma 5.1 the graph G does not contain cycles, it is not difficult to conclude that there exists a subset V′ of V such that the subgraph of G induced by V′ is a recognition tree of the input.

The second part of the construction consists of finding a subgraph G′ = (V′, E′) of G, which is a recognition tree. This construction can be realized as follows. We choose an item I_{0} of the form (S → α·, 0, n) with R(I_{0}) = true. This item corresponds to the root of the recognition tree. The other elements of V′ are nodes connected to I_{0} by a path in G, i.e., all nodes I such that E^{∗}(I, I_{0}) = 1, where E^{∗} denotes the transitive closure of E.^{6}

Computational costs of the procedures described in this section can be determined as follows. The graph G can be computed from the array R in constant time with O(n^{5}) processors using an ARBITRARY CRCW PRAM.^{7} In fact, for each one of the O(n^{2}) realizable items we have to consider is parallel all pairs (J , K) of possible sons of I. In the worst case, such a pair is defined by two dotted rules and by three indices in {0, …, n}. Thus, the number of these pairs is O(n^{3}). By known simulation results, this computation can be simulated on a COMMON CRCW PRAM in time O(log n) using O(n^{5} log n) processors. Finally, it is easy to observe that the number of nodes of the recognition tree G so obtained is O(n). Thus, given the graph G, the computation of the recognition tree is essentially reduced to the computation of the transitive closure of a boolean square matrix of order O(n^{2}). This computation can be performed in O(log n) steps using O(n^{6}) processors.

5.2 Construction of the parse tree

Once the recognition tree G′ = (V′, E′) has been constructed, what remains to do is to build the parse tree. This last phase of the algorithm can be realized as follows. We call a node of V′ final if and only if its label is of the form (A → α·, i, j) or (a, j). It can be easily verified that, by definition of recognition tree, final nodes are the root and the right sons of nodes. Now, given G′, a parse tree can be constructed in the following way. The nodes of the parse tree are all the final nodes of G′. The root is the same root of G′. Connections among nodes are computed rearranging the arcs of G′, so that the father of every final node I, different from the root, is the first final node J that follows I in the path from I to the root of G′. Applying this construction to the recognition tree in Figure 1, we obtain the tree represented in Figure 4.

6As usual, we can suppose that the set E of arcs is represented by the adjacency matrix, also denoted by E.

7We recall that in this model, if two or more processors attempt to write in the same cell at the same time, then one of them, chosen in a random way, succeeds.

[figure: (E→E+T ·,0,5); (E→T ·,0,1); (+,2); (T →T ∗P ·,2,5); (T →P ·,0,1); (T →P ·,2,3); (∗,4); (P →a·,4,5); (P →a·,0,1); (P →a·,2,3); (a,5); (a,1); (a,3)]

Figure 4: construction of the parse tree

Finally, from the tree just constructed, the parse tree is recovered assigning to each node of the form (A → α·, i, j) the label A, and to each node of the form (a, j) the label a.

The above outlined transformation of the graph G′ = (V′, E′) in the parse tree can be obtained using the following algorithm, that computes a new adjacency matrix Ẽ from which, as we will explain later, it is possible to recover the parse tree.

Algorithm 3

begin for all I, J in parallel do Ẽ(I, J) := E′(I, J) repeat O(log n) times

for all I, J , K in parallel do if K is not a final node and Ẽ(I, K) = Ẽ(K, J) = 1 then begin

(1)  Ẽ(I, J) := 1
(2)  Ẽ(I, K) := 0

end end

Algorithm 3 uses a pointer jumping technique [KR90] for contracting paths in the tree. In particular, in k iterations, the algorithm reduces every path of length 2^{k} whose nodes (except the first and the last one) are non final, to a single arc. Moreover, every iteration of Algorithm 3 transforms a tree in another tree. Thus, write conflicts do not arise when instructions (1) and (2) are executed.

The correctness of Algorithm 3 can be proved as a consequence of the following theorem.

Theorem 5.1 Let Ẽ_{k} denotes the adjacency matrix Ẽ computed after the kth iteration of Algorithm 3, and E^{k} the kth power of E. Then, for every pair (I, J) of nodes of V′ the following sentences are equivalent:

(i) Ẽ_{k}(I, J) = 1;

(ii) there exists an integer m, 0 ≤ m ≤ 2^{k}, such that E^{m}(I, J) = 1, and there exist no final nodes H internal to the path from I to J in G′; moreover, if J is not a final node then m > 2^{k−1}.

Proof. We prove the theorem by induction on the number k of iterations. First, we observe that for k = 0 the result is trivial since Ẽ_{0} = E′. Thus, we now suppose that k > 0. First we prove that (i) implies (ii). Let I and J be two nodes such that Ẽ_{k}(I, J) = 1. Then either Ẽ_{k−1}(I, J) = 1 or there exists a non final node K such that Ẽ_{k−1}(I, K) = Ẽ_{k−1}(K, J) = 1. In the latter case, by induction hypothesis, we can easily conclude that (ii) holds. In the former case, we can also use the induction hypothesis. We have only to observe that since Ẽ_{k−1}(I, J) = Ẽ_{k}(I, J) = 1, the node J is final. In fact, at every iteration Algorithm 3 transforms a tree in another tree with the same root, and this root is a final node. Thus, if J is not final, then there exists a node J′ such that Ẽ_{k−1}(J , J′) = 1, but in this case, executing instruction (2) (with K = J), Algorithm 3 sets Ẽ_{k}(I, J) to 0. Then, since m < 2^{k−1} but J is final, we can conclude that (ii) holds also in this case.

Conversely, suppose that (ii) holds. If m ≤ 2^{k−1} then J must be a final node. By induction hypothesis Ẽ_{k−1}(I, J) = 1, and in the kth iteration of the algorithm the value of this component does not change. Thus (i) holds.

If m > 2^{k−1}, then we have E^{m} = E^{2^{k−1}}E^{m−2^{k−1}}. Thus, there exists K such that E^{2^{k−1}}(I, K) = E^{m−2^{k−1}}(K, J) = 1. By induction hypothesis it easily follows that Ẽ_{k−1}(I, K) = Ẽ_{k−1}(K, J) = 1. Moreover K is not a final node. Thus, Algorithm 3 sets to 1 the value of Ẽ_{k}(I, J).

We recall that the number of nodes of the recognition tree G′ is linear in the length n of the input string. Thus, using Theorem 5.1, it is not difficult to conclude that after O(log n) steps of Algorithm 3, the arcs are correctly rearranged, i.e., there exists an arc from a node I to a node J if and only if J is the first final node on the path from I to the root in the recognition tree G′. The parse tree corresponds to the graph G′′ = (V′′, E′′) where V′′ is the set of all final nodes of V′ and E′′ = Ẽ ∩ (V′′ × V′′), where Ẽ is the matrix computed by Algorithm 3.

It is immediate to observe that Algorithm 3 has the same complexity of the recognizer described in Sections 3 and 4.

6 Extension to context–free grammars with ϵ and unit productions

In this section we will show how the recognizer and the parser so far described can be extended to context–free grammars with ϵ and unit productions.

As already shown in Lemma 5.1, when a grammar G contains ϵ–productions or unit productions, the graph obtained by Algorithm 2 may contain some cycle. For instance, if A → AB and B → β are two productions of G and B generates the empty string, then the items (A → ·AB, 0, 0), (A → A · B, 0, 0), (A → AB·, 0, 0) and (B → β·, 0, 0) are realizable. Thus, Algorithm 2 can choose (A → ·AB, 0, 0), (A → AB·, 0, 0) as sons of (A → A · B, 0, 0) and (A → A · B, 0, 0), (B → β·, 0, 0) as sons of (A → AB·, 0, 0).

In order to avoid such a phenomenon we have devised the following strategy. We add to each item a counter whose value is computed by the recognizer and it is used for establishing the order between two realizable items of the form (A → α · β, i, j), (B → γ · δ, l, r), when l = i or j = r, during the construction of the recognition tree. More precisely, we define an extended item as a quadruple (A → α · β, i, j, h), such that (A → α · β, i, j) is an item and h ≥ 0 is an integer.

Extending Definition 4.1, we introduce now the notion of extended recognition tree.

Definition 6.1 Given a context–free grammar G = (V, Σ, P, S) and an input string x = x_{1} … x_{n}, x_{i} ∈ Σ, an extended partial recognition tree of x is a binary tree, whose nodes are labeled either with extended items or with pairs (a, j) ∈ Σ × {1, …, n} such that:

1. the label of an internal node is an extended item I = (A → α · β, i, j, h), with α ≠ ϵ; the label of its left son is J and the label of its right son is K, where:

• if α = α′B, with B ∈ V, then J = (A → α′ · Bβ, i, k, h′) and K = (B →

γ·, k, j, h′′), for some k, i ≤ k ≤ j, B → γ ∈ P, h′, h′′ ≥ 0 such that:

h = \{ \begin{matrix}0 & if i < k < j, \\ h′ + 1 & if i < k = j, \\ h′′ + 1 & if i = k < j, \\ max(h′, h′′) + 1 & if i = k = j. \end{matrix}

• if α = α′a, with a ∈ Σ, then j > i, a = x_{j}, h = 0, J = (A →

α′ · aβ, i, j − 1, h′), with h′ ≥ 0, and K = (a, j);

2. the labels of the leaves are items of the form (A → ·α, i, i, 0) and, from left to right, the pairs (x_{p+1}, p + 1), …, (x_{q}, q), 0 ≤ p ≤ q ≤ n.

An extended recognition tree of x is an extended partial recognition tree whose root is labeled with an item (S → α·, 0, n, h), for some production S → α, and some integer h with h ≥ 0.

Comparing Definition 6.1 with Definition 4.1, it turns out that there is a bijection between the set of recognition trees of a string x and the set of extended recognition trees of x. This observation can be used for proving the following theorem:

Theorem 6.1 Given a context–free grammar G, for every string x ∈ L(G) there exists an extended recognition tree T of x whose number of nodes is O(|x|). Moreover, if I = (A → α · β, i, j, h) is an item labeling a node of T, then 0 ≤ h < H, where H is the number of dotted rules of G.

Proof. (sketch) A slight modification of the proof of Theorem 4.1 permit us to conclude that for every x ∈ L(G) there is an extended recognition tree T of x, whose number of nodes if O(|x|) and such that all (non extended) items corresponding to labels of nodes of T are different.

Now we show that for every node I = (A → α·β, i, j, h) of T, it holds 0 ≤ h < H. Suppose in fact that h > 0. Then α = α′B for some α′ ∈ (V ∪ Σ)^{∗}, B ∈ V, and there exists a son I′ = (A′ → α′ · β′, i′, j′, h′) of I such that i′ = i, j′ = j, h′ = h − 1. Iterating this argument, we are able of finding a chain I_{0}, …, I_{h} in the tree with I_{0} = I, and, for k = 1, …, h, I_{k} = (A_{k} → α_{k} ·β_{k}, i, j, h−k). By assumption all (non extended) items corresponding to labels of nodes of T are different thus h cannot be greater than the number of dotted rules, i.e., h < H.

At this point, it is not difficult to modify Algorithm 1, Algorithm 2 and Algorithm 3 to work with extended items of the form (A → α · β, i, j, h) with 0 ≤ h < H.

In the last phase, when the parse tree is recovered from the graph constructed by Algorithm 2, when to a node I of the form (A → ·, i, j, h) is associated the label A, it is also necessary to append to the node I a new node I′ labeled ϵ.

Since the number of extended items (A → α · β, i, j, h) with 0 ≤ h < H, as that of item, is O(n^{2}), where n denotes the length of the input, it is not difficult to see that also the algorithm so modified work in time O(log n) using O(n^{6}) processors.

7 Concluding remarks

In this paper we have shown that the problem of deciding whether an input string x belongs to a context–free language L(G), where G is a fixed but arbitrary context– free grammar, can be solved by a CRCW PRAM in O(log |x|) time.

The algorithm we have just described is very efficient in terms of computation time but unfortunately it requires a big number of processors to be executed. However, using a more sophisticated partial evaluation technique introduced in [BPR94], it is possible to transform our parser into a parallel algorithm which works in sublinear time but uses a bit more than a square number of processors.

References

[AU72] A. Aho, J. Ullman, The Theory of Parsing, Translation and Compiling, Volume I: Parsing, Prentice–Hall, 1972.

[Coo70] S. Cook, “Path systems and language recognition,” Proc. STOC: 70–72, 1970.

[BPR94] D. Bruschi, G. Pighizzini and F. Ravasio, “How to trade time for processors in parallel algorithms”, submitted for publication.

[Ear70] J. Earley, “An efficient context–free parsing algorithm,” Comm. ACM 13(2): 94–102, 1970.

[GI80] E. Gurari and O. Ibarra, “Path systems: constructions, solutions and applications,” SIAM J 9: 348–374, 1980.

[GHR80] S. Graham, M. Harrison and W. Ruzzo, “An improved context–free recognizer,” ACM Transactions 2(3) : 415–462, 1980.

[HU79] J. Hopcroft and J. Ullman, Introduction to automata theory, languages and computation, Addison–Wesley, 1979.

[JL77] N. Jones and T. Laaser, “Complete problems for deterministic polynomial time,” TCS 3:105–117, 1977.

[Kil85] J. Kilbury, “A modification of the Earley–Shieber algorithm for direct parsing with ID/LP–grammars,” Proc. 8th German Workshop on Artificial Intelligence: 39–48, Springer, 1985.

[Knu65] D. Knuth, “On the translation of languages from left to right,” Inf. and Control 8: 607–639, 1965.

[KR90] R. Karp and V. Ramachandran, “Parallel algorithms for shared–memory machines,” in Handbook of Theoretical Computer Science, J.V. Leeuwen ed., Elsevier, 1990.

[Lei90] H. Leiss, “On Kilbury’s modification of Earley’s algorithm,” ACM Transactions 12(4): 610–640, 1990.

[LS74] R. Lipton and L. Snyder, “On the optimal parsing of speech,” Res. Rep. 37, Dep. Computer Science, Yale Univ., 1974.

[MR85] G. Miller and J. Reif, “Parallel tree contraction and its application,” Proc. 26th FOCS: 478-489, 1985.

[MRK88] G. Miller, V. Ramachandran and E. Kaltofen, “Efficient parallel evaluation of straight–line code and arithmetic circuits,” SIAM J 17: 687–695, 1988.

[Ruz80] W. Ruzzo, “Tree–size bounded alternation,” JCSS 21: 218–235, 1980.

[Ryt85] W. Rytter, “The complexity of two way pushdown automata and recursive programs,” in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil, ed.s, NATO ASI Series F:12, Springer, 1985.

[Ryt86] W. Rytter, “On the complexity of parallel parsing of general context–free languages,”TCS 47: 315–321, 1986.

[Sip82] S. Sippu, “Derivational complexity of context–free grammars,” Information and Control 53: 52–65, 1982.

[Tom85] M. Tomita, “An efficient context–free parsing algorithm for natural languages,” Proc. 9th IJCAI : 756–764, 1985.