Parallel RAMs with owned global memory and deterministic context-free language recognition.
We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, Owner Write, or CROW-PRAMS, these are machines in which each global memory location is assigned a unique owner processor, which is the only processor allowed to write into it.  Considering the difficulties that would be involved in physically realizinga full CREW-PRAM model and demonstrate its stability under several definitional changes.  Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time O(log n) (and implicity with a polynomial number of processors) is exactly the class LOGDCFL of languages  log space reducible to deterministic context-free languages.  Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log n space work tape, and pushdown store of small maximum height. For example, time O(n1 + &egr;) is achievable with pushdown height O(log2 n). These result extend and unify work of von Braunmhl, Cook, Mehlhorn, and Verbeek, Klein and Reif; and Rytter.
under several definitional changes. Second, we precisely characterize
the power of the CROW-PRAM by showing that the class of languages
recognizable by it in time O(log n) is exactly the class LOGDCFL of
languages log space reducible to deterministic context free languages.
Third, using the same basic machinery, we show that the recognition
problem for deterministic context-free languages can be solved in time
O(n 1+ffl =S(n)) for any ffl ? 0 and any log 2 n - S(n) - n on a deterministic
auxiliary pushdown automaton having a log n space work tape,
pushdown store of maximum height S(n), and random access to its
input tape. These results extend and unify work of von Braunm-uhl,
Cook, Mehlhorn, and Verbeek; Klein and Reif; and Rytter.
1 Introduction and Related Work
There is now a fairly large body of literature on parallel random access machine
(PRAM) models and algorithms. There are nearly as many definitions
of this model as there are papers on the subject. All agree on the general
features of such models - there is a collection of more or less ordinary sequential
processors with private, local memories, that all have access to a
shared global memory. The model is synchronous - in each time unit, each
processor executes one instruction. There is much more diversity regarding
other features of the model. For example, there are differences as to whether
the model has single- or multiple-instruction streams, how many processors
there are, how they are numbered, how they are activated, what instruction
set they have, what input convention is used, and how simultaneous read
or write requests to a single global storage location are arbitrated. Most of
these variations make little or no difference in the power of the model.
Two features seem to have a substantial impact on the power of the
model. One is uniformity. In general, we only consider uniform models in
this paper, i.e., ones where a single program suffices for all input lengths,
and where a single processor is initially active, creating other processors
as desired. The second sensitive feature is arbitration of memory access
conflicts. Two main variants have been most intensively studied. Following
the nomenclature introduced by Vishkin [37], the CRCW (Concurrent-Read,
Concurrent-Write) PRAM allows memory access conflicts. All processors
reading a given location in a given step receive its value. Among all processors
CROW-PRAMs and DCFL Recognition 3
writing to a given location in a given step, one is allowed to succeed, e.g.,
the one with the lowest processor number. (Other resolution rules for write
conflicts have been proposed. All are known to be equivalent in power up
to constant factors in running time, and polynomial factors in number of
processors and global memory size, although the models are separated if
processors and memory are more tightly constrained.)
In the CREW (Concurrent-Read, Exclusive-Write) model, concurrent
reads are allowed, as above, but concurrent writes are not. CREW algorithms
must arrange that no two processors attempt to write into the same
global memory location at the same time.
In this paper we introduce a third variant, argue that it is a more "natu-
ral" model than the CREW PRAM, and give a surprising characterization of
its power. There are several reasons to study this restriction of the CREW-
PRAM. The CREW-PRAM model has been criticized for being too powerful
to serve as a realistic model of physically realizable parallel machines due to
its "unbounded fanin." Anderson and Snyder [1] point out that the two-stage
programming process of first using the CREW-PRAM model to develop a
straightforward fully parallel algorithm (e.g., for the "or" of n bits), and then
emulating this algorithm on a physically realizable network, could lead to a
sub-optimal algorithm (\Theta((log n) 2 ) for the above example). Nevertheless the
CREW-PRAM has arguably been the most popular theoretical model for the
design, specification and analysis of parallel algorithms, due principally to
the simplicity and usefulness of the global memory model for programmers.
It is useful therefore to consider the power of the more restricted CROW-
PRAM model, in order to understand its feasibility as a model for parallel
programming. As noted above, most CREW-PRAM algorithms are in fact
CROW-PRAM algorithms, or can be easily modified to be so.
How can a CREW-PRAM algorithm ensure that it is obeying the
Exclusive-Write restriction? With two exceptions discussed below, all
CREW-PRAM algorithms we have considered achieve, or can be easily modified
to achieve, write exclusion by the following simple stratagem: each
global memory location is "owned" by one processor, which is the only processor
ever allowed to write into that cell. Further, the mapping between
global memory addresses and processor numbers is easy to compute, so that
each processor has no difficulty in determining which cells it owns. For ex-
4ample, processor p might own the block of k consecutive cells beginning at
global memory address kp. We call this the Owner-Write restriction, and call
PRAMs that obey this restriction Concurrent-Read, Owner-Write PRAMs,
or CROW-PRAMs. The ownership restriction seems to be a very natural
framework in which to design exclusive-write algorithms. Similar but not
identical notions of "ownership" have appeared in the earlier lower bound
work of Cook, et al. [7], and have also proven useful in practice for certain
cache coherence protocols. (See, e.g., Archibald and Baer [2].) In many current
architectures of parallel systems, the machines provide a global memory
programming model, implemented using physical hardware in which every
memory cell is local to some processor. Caching or other techniques are used
to ameliorate the cost of access to non-local memory. If non-local writes are
prohibited, the necessary cache coherence algorithms are simplified. In fact,
a positive solution to the CROW versus CREW problem discussed in Section
3 would presumably suggest an interesting new approach to the cache
coherence problem.
We give a precise definition of the CROW-PRAM model in Section 2
below. The main goal of this paper is to investigate the power of the CROW-
PRAM. Unexpectedly, this question turns out to be intimately related to
the complexity of deterministic context-free language (DCFL) recognition.
The recognition problem for a deterministic context-free language L is
to decide, given a word x, whether x 2 L. The sequential complexity of
this problem has been well-studied, and there are many practical sequential
algorithms for solving it in space and time O(n). The small-space and parallel
time complexities of the problem are less well-understood. Two main results
in these areas are by von Braunm-uhl, Cook, Mehlhorn, and Verbeek [5, 38],
and by Klein and Reif [20].
Cook [5] presents a sequential algorithm for the DCFL recognition problem
that runs in polynomial time on a Turing machine using only polynomial
in log n space. This result has been improved by von Braunm-uhl et al. [38],
who give Turing machine algorithms with optimal time-space product for
any space bound in the range from (log n) 2 to n.
Building somewhat on the ideas of [5, 38], Klein and Reif [20] present
an O(log n) time CREW-PRAM algorithm for DCFL recognition. (It is
known that results of Stockmeyer and Vishkin [35] can be combined with the
CROW-PRAMs and DCFL Recognition 5
algorithm of Ruzzo [32] to yield an O(log n) time algorithm for general CFL
recognition, but only on the more powerful CRCW-PRAM model.)
Our main result is the following characterization of CROW-PRAMs.
Theorem 1 A language L is accepted by a CROW-PRAM in O(log n)
time if and only if L is log-space reducible to a DCFL.
The class LOGDCFL of languages log-space reducible to DCFLs was first
defined and studied by Sudborough [36], who showed that it is equal to the
class of languages recognizable in polynomial time by log-space bounded deterministic
auxiliary pushdown automata (DauxPDAs), defined by Cook [4].
Our result appears to be the first to precisely characterize a parallel time
complexity class (up to constant factors) in terms of a sequential one. For
example, Sudborough's ``hardest DCFL'' [36] provides a natural example of a
problem complete for CROW-PRAM time O(log n). Complete problems have
been discovered by Chandra and Tompa for CRCW-PRAM time classes [3].
We know of no analogous natural problems that are complete for CREW-
classes. Following an earlier version of our paper [12], Lange
and Niedermeier [22] established characterizations of other PRAM variants
in terms of sequential complexity classes.
We use the DCFL characterization to demonstrate the stability of
CROW-PRAM complexity classes under definitional changes. For example,
it follows from the DCFL simulation that a CROW-PRAM can be simulated
time loss by a parallel machine on which there is no global memory,
but each processor contains a single externally visible register, that may be
read (but not written) by any other processor. This model seems to be closer
to the way that some parallel machines have actually been constructed than
models with an independent global memory not associated with any processor

The DCFL recognition algorithms of von Braunm-uhl et al. [38] and Klein
and Reif [20] are difficult ones, and use superficially different approaches. The
third goal of this paper is to provide a unified approach to both problems,
which, although based on both, we believe to be simpler than either.
We obtain both a small time parallel algorithm and a small space sequential
algorithm for DCFL recognition using the same basic approach. The
small space algorithm provides an improvement to a result by Rytter [33],
and a technical refinement to the optimal results of von Braunm-uhl et al. [38].
Rytter had shown, using a sequential implementation of [20], that it is possible
to obtain a polynomial time, O(log 2 n) space algorithm for DCFL recognition
using space mainly as a pushdown store (more precisely, a log n space
DauxPDA with an O(log 2 n) bounded pushdown), rather than unrestricted
O(log 2 n) space as in [38]. We improve these results by performing our simulation
on a DauxPDA (like Rytter) while attaining a time-space product
similar to that of von Braunm-uhl et al.
Section 2 presents the CROW-PRAM model, and discusses variations
in the definition. Section 3 presents its simulation by deterministic
auxiliary pushdown automata, establishing CROW-PRAM-TIME(log n) '
LOGDCFL. Section 4 introduces some definitions and notation needed in
our DCFL recognition algorithm. Section 5 presents a high level description
and correctness proof of the DCFL recognition algorithm. Section 6
discusses CROW-PRAM implementation of the algorithm, establishing the
other inclusion needed for Theorem 1, i.e., LOGDCFL ' CROW-PRAM-
TIME(log n). Finally, Section 7 refines the simulation of Section 5 to obtain
a faster sequential algorithm than that obtained by combining the CROW-
PRAM algorithm of Section 6 with the general simulation of Section 3.
Further work involving the owned global memory concept in PRAMs
has appeared following a preliminary version of this paper [12]. Fich and
Wigderson give a lower bound separating EROW and CROW PRAMs [14].
Rossmanith introduces and studies Owner Read, Owner Write PRAMs,
showing, for example, that they can do list ranking in O(log n) time [31].
Nishimura considers the owner concept in CRCW-PRAMs [29]. Nieder-
meier and Rossmanith [27, 26] have considered the owner concept with other
PRAM variants. Lin, et al. show that CROW-PRAMs are sufficiently powerful
to execute a variant of Cole's parallel merge sort algorithm in time
O(log n) [23]. Work on further restrictions of the CROW-PRAM model by
Lam and Ruzzo [21] and Dymond, et al. [11] is described at the end of section
two.
CROW-PRAMs and DCFL Recognition 7
2 Definition of CROW-PRAMs
We start by defining the CREW-PRAM model we will use. As mentioned
above, most of the details of the definition are not critical. For specificity we
use the definition of Fortune and Wyllie [15] (called simply a P-RAM there)
which has: an unbounded global memory and an unbounded set of processors,
each with an accumulator, an instruction counter and an unbounded local
memory. Each memory cell can hold an arbitrary non-negative integer. The
instruction repertoire includes indirect addressing, load, store, add, subtract,
jump, jump-if-zero, read, fork, and halt. The input is placed in a sequence of
special read-only registers, one bit per register. The read instruction allows
any processor to read any input bit; concurrent reads are allowed. A fork
instruction causes a new processor to be created, with all local memory cells
zero, and with its accumulator initialized to the value in the accumulator
of its creator. Initially, one processor is active, with its local memory zero,
and the length of the input given in its accumulator. The model accepts if
the initially active processor halts with a one in its accumulator. It rejects
if two processors attempt to write into the same global memory location at
the same time.
These CREW-PRAMs do not have "processor numbers" or "IDs" as a
built-in concept, but we will need them. We adopt the following processor
numbering scheme. The (unique) processor active initially is numbered 0;
the first child processor created by processor i will be numbered 2i
second will be numbered 2 1). This
corresponds to the natural embedding of an arbitrary tree (the processor
activation tree) into a binary tree by the rule "eldest child becomes right
child, next younger sibling becomes left child." Reverse-preorder traversal of
the activation tree and the binary tree are identical. As we will see, many
other numbering schemes will also work; this one is fairly natural. Processors
do not automatically "know" their number, but it is easy to program them
to compute it, if needed.
algorithm is a CREW-PRAM algorithm
for which there exists a function owner(i; n), computable in deterministic
space O(log n), such that on any input of length n processor p attempts to
write into global memory location i only if
The intuitive definition given earlier said that the owner function should
be "simple". We have particularized this by requiring that it be log-space
computable and that it be oblivious, i.e., independent of the input, except for
its length. We have not required that the model detect ill-behaved programs,
i.e., ones that attempt global writes in violation of the ownership constraint.
Such programs simply are not CROW programs. These seem to be natural
choices, but we will also show that our main results are fairly insensitive to
these issues. We could generalize the model in any or all of the following
ways:
G1. Allow the owner function to depend on the input.
G2. Allow the owner function to depend on time.
G3. Allow "bounded multiple ownership", i.e., owner(i; n) is a set of size
O(1) of processor numbers.
G4. Allow ill-behaved programs, by defining the model to halt and reject
if an attempted write violates the ownership constraint.
G5. Allow any processor numbering scheme that gives processors unique
numbers and allows one to compute in logarithmic space the parent of
a given processor p, the number of older siblings it has, and the number
of its k th child.
G6. Allow the owner, parent, and sibling functions above to be computable
by a deterministic log-space auxiliary pushdown automaton that runs
in polynomial time.
Alternatively, we could restrict the model in any or all of the following ways:
R1. Require that the owner function be the identity -
This is equivalent to saying that the machine has no global memory;
instead it is a collection of processors each with a private local memory
and one globally readable "communications register"
R2. Require that processors use only O(1) local memory locations.
CROW-PRAMs and DCFL Recognition 9
R3. Require that the machine be write-oblivious, i.e., the times and locations
of writes to global memory are independent of the input, except
for its length.
One consequence of our results is that CROW-PRAMs, even ones satisfying
only the relatively weak conditions G1-G6, can be simulated by CROW-
PRAMs satisfying the strict conditions R1-R3, with only a constant factor
increase in time and a polynomial increase in number of processors.
Is it possible that CREW- and CROW-PRAMs have equivalent power?
On the positive side, conditions G1-G6 are fairly generous. It is difficult to
imagine a protocol by which a PRAM algorithm could achieve write-exclusion
that would not be covered by these. For example, note that a general CREW-
PRAM algorithm can be considered to be a CROW-PRAM algorithm where
the owner function is allowed to be input- and time-dependent (conditions
G1 and G2 above) and in some sense computable by a CREW-PRAM in real-
time. We know that, say, CREW-PRAM time O(log n) can be simulated by
a logarithmic space deterministic auxiliary pushdown automaton that runs in
time n O(log n) , so real-time CREW-PRAM computable functions may not be
that different from n O(1) DauxPDA computable ones. Thus it seems possible
that time on CROW-PRAMs and CREW-PRAMs might be identical. At
least, this provides some intuitive support for the empirical observation that
most known CREW-PRAM algorithms are CROW-PRAM algorithms.
In one context, we know the two models are equivalent. Following the
appearance of an extended abstract of this paper [12], Ragde (personal com-
munication; see also Fich [13], Nisan [28]) observed that nonuniform CROW-
PRAMs, i.e., ones having arbitrary instructions, exponentially many processors
initially active, and allowing different programs for each value of
n, running in time t are equivalent to Boolean decision trees of depth 2 t .
Nisan [28] established that for any set recognized by a (nonuniform) CREW-
PRAM in time O(log n), for each n there is a equivalent Boolean
decision tree problem of depth 2 t(n) . Taken together these results show time
on the two models is the same up to a constant factor in the nonuniform
setting. This leaves open the stronger conjecture that any set recognized
by a CREW-PRAM in time log n can be recognized on a CROW-PRAM in
time O(log n), both of the ordinary, uniform variety and both using polynomially
many processors. Note that Nisan's simulation of CREW by CROW
uses nonuniformity in a fundamental way and uses 2 2 t(n)
initially active pro-
cessors, and that in his nonuniform model all languages are recognizable in
O(log n) steps.
In one restricted setting we know the two (uniform or nonuniform) models
to be different. Suppose processors 1 through n are active, each knows one
bit b i , and we want to compute the "or" of these bits, given that at most one
b i is 1. A CREW-PRAM can solve this in one step: any processor having a 1
bit writes it into global location 0. No write-conflict can happen since there is
at most one 1 bit. However, Marc Snir (personal communication) has shown
that a CROW-PRAM
n) steps to solve this problem from the
same initial state.
Snir's result does not settle the general question, however. The problem
discussed above is defined only when at most one input bit is one. (This
has been called a "partial domain" by Fich, in contrast to the more usual
situation where an algorithm is required to produce a correct answer on all
n-bit input sequences.) We know from the results of Cook, et al. [7] that even
a CREW-PRAM requires time \Omega\Gammame/ n) to test whether its input contains at
most one 1 bit. Conceivably, a CREW algorithm that exploited something
like Snir's ``or'' could always be transformed into a CROW algorithm by using
this "preprocessing" time to better advantage.
The only full domain problem known to us where (uniform) CREW-
PRAMs seem more powerful that CROW-PRAMs is the recognition problem
for unambiguous context-free languages. For this problem Rytter [34] has
given an O(log n) CREW-PRAM algorithm that appears to use the power of
non-owner exclusive writes in a fundamental way. Loosely speaking, it seems
that the unambiguity of the underlying grammar allows one to repeatedly
exploit a feature like Snir's ``or''.
While CROW-PRAMs appear to be nearly as powerful as CREW-
PRAMs, it is interesting to compare them to a possibly weaker parallel model,
the parallel pointer machine of Dymond and Cook [10]. PPMs consist of an
unbounded pool of finite-state transducers, each with a finite set of pointers
to other processors. A PPM operates by sensing the outputs of its neighboring
processors, and moving its pointers to other processors adjacent to
its current neighbors. Cook proposed such a model as an example of the
simplest possible parallel machine with "variable structure" [6].
CROW-PRAMs and DCFL Recognition 11
Lam and Ruzzo [21] establish that time on PPMs is linearly related to
time on a restricted version of the CROW-PRAM, on which doubling and
adding one are the only arithmetic operations permitted. (In fact, they also
showed a simultaneous linear relationship between the amounts of hardware
used on the two machines.) Our conjecture that the CROW-PRAM's ability
to access two-dimensional arrays in constant time cannot be directly emulated
on a CROW-PRAM whose arithmetic capability is so limited has been
proved recently by Dymond, et al. [11]. Since two-dimensional arrays appear
to play an important part in the DCFL simulation algorithm of Section 6,
this suggests that quite different techniques would be needed to recognize
DCFLs in time O(log n) on the PPM, if this is indeed possible. An analogous
nonconstant lower bound on two dimensional array access was proved
for sequential unit cost successor RAMs by Dymond [9].
3 Simulation of CROW-PRAMs by
DauxPDAs
In this section we will prove the first half of Theorem 1, namely:
Theorem 2 Any set recognized in time O(log n) on a CROW-PRAM is
in LOGDCFL.
Recall that LOGDCFL is the class of languages log space reducible to
deterministic context-free languages. Sudborough [36] defined the class, and
characterized it as the set of languages recognized in polynomial time on a
logarithmic space deterministic auxiliary pushdown automaton.
The main construction is similar to analogous ones given by Pratt and
Stockmeyer [30], Fortune and Wyllie [15], and Goldschlager [17] showing
that PRAM time log n is contained in DSPACE(log 2 n). We define three
mutually recursive procedures:
state(t; p) returns the state of processor p at time t, i.e., after the t th instruction
has been executed.
local(t; returns the contents of location i of the local memory of processor
p at time t.
global(t; i) returns the contents of global memory location i at time t.
Each depends only on the values of these procedures at time t \Gamma 1, so the
recursion depth will be at most t. Furthermore, each procedure will require
only O(log n) bits of local storage, so by well-known techniques these procedures
can be implemented on a logarithmic space deterministic auxiliary
PDA whose pushdown height is at most O(log 2 n). This much of the proof
is essentially the same as in [15, 17, 30]. The main novelty with our proof
is that our algorithm runs in polynomial time, rather than time n log n as in
the earlier results. This is possible because the owner function allows us
in global(t; i) to directly identify the only possible writer of global memory
location i at time t \Gamma 1. This allows each of our procedures to make only
recursive calls per invocation, which gives a polynomial running time.
If we were simulating a general CREW-PRAM algorithm, it would appear
necessary to check all processors at time t \Gamma 1 to see whether any of them
wrote into i, and if so, whether more than one of them did. This appears to
require more than polynomial time.
Extensions to these basic procedures to accommodate generalizations G1-
G6 are quite direct, except for G4, ill-behaved programs. G4 is also possible,
but more delicate, since in effect we must check at each step that none of
the many non-owners attempts to write to a global cell, while maintaining
the property that our algorithm makes only O(1) recursive calls per invoca-
tion. (It is possible that a similar generalization of the CREW model would
increase its power.)
Proof of Theorem 2: Detailed descriptions of the three procedures follow.
A typical PRAM instruction is "global indirect store l", whose meaning is
"store the accumulator into the global memory location whose address is
given by the contents of local memory location l". We will not describe the
rest of the PRAM's instruction set in great detail; see Fortune and Wyllie [15].
The state of processor p at time t is an ordered pair containing the
instruction counter, and the contents of the accumulator of p at the
end of the t th step. We define three auxiliary functions accumulator(S),
instruction-counter(S), and instruction(S), that, for any state S, give the accumulator
portion of S, the instruction counter portion of S, and the instruction
pointed to by the instruction counter of S, respectively. Assume that a
value of 0 in the instruction counter designates a "halt" instruction, which by
CROW-PRAMs and DCFL Recognition 13
convention will be the instruction "executed" in each step before processor
p is activated and after it has halted. Also, assume that instruction(S) will
be a "halt" instruction if it is not otherwise defined, e.g., after a jump to a
location beyond the end of the program. It is convenient to assume that the
local memory of a processor is set to zero as soon as it halts, but its accumulator
retains its last value. We assume that processor 0 initially executes
instruction 1, and that a processor activated by a "fork l" instruction initially
executes instruction l. We also assume that each processor maintains
in local memory location 0 a count of the number of "fork" instructions it has
executed. (This count should be initially 0, and is incremented immediately
after each "fork" is executed.) It is easy to modify any PRAM algorithm
to achieve this. We also use two functions parent(p) and sibling-count(p)
that, for any processor number p, return the processor number of the parent
of p, and the number of older siblings of p, respectively. For the processor
numbering scheme we have chosen these functions are very easy to compute.
Namely, if k is the largest integer such that p is evenly divisible by 2 k , then
procedure Simulate-CROW-PRAM
comment: Main Program.
begin
ne comment: An upper bound on the running time
of the PRAM.
if state(T;
function global(t; i)
comment: Returns the contents of global memory location i at time t.
begin
store l" and
then return accumulator(S)
else return
function local(t;
comment: Return the contents of local memory location i of processor
p at time t.
begin
case
"local store i" : return accumulator(S)
"indirect local store l": if
then return accumulator(S)
return
CROW-PRAMs and DCFL Recognition 15
function state(t; p)
comment: Return the state of processor p at time t.
begin
then comment: AC is initially length of input.
return (1; n)
else comment: All other processors are idle at time 0.
return (0;
AC := accumulator(S)
IC := instruction-counter(S)
case
"indirect load l": return (IC
"global indirect load l"
"add", "sub", "read"
similar to "load"
then return (l; AC)
else return (IC
parent activated p in this step.
then return (l; accumulator(S 0
else comment: p not activated; just pass AC.
return (0; AC)
Correctness of the simulation is a straightforward induction on t. Implementation
of the procedures on an DauxPDA is also easy. Note that each
procedure has local variables requiring at most O(log n) bits of storage, so
the DauxPDA needs only that much space on its work tape. The recursion
depth is equal to the PRAMs running time, i.e., O(log n), so the pushdown
height will be at most the product of those two quantities, i.e., O(log 2 n).
Each procedure makes at most O(1) recursive calls per recursive level, so the
running time of the simulation is (O(1)) O(log n) = n O(1) . This completes the
proof of Theorem 2. 2
The simulation given above is easily adapted to accommodate the generalizations
G1-G6 to the definition of CROW-PRAMs proposed earlier. Allowing
a more general owner function, say depending on the input or on time
(G1,G2) is trivial - just add the appropriate parameters at each call. Using
a different processor numbering convention is equally easy, provided that
parent(p), and sibling-count(p) are easily computable (G5). Allowing these
functions to be log-space and polynomial time DauxPDA computable will
not effect the asymptotic complexity bounds (G6). Bounded multiple ownership
(G3), is also easy - in the global procedure, where we check whether
the owner of global memory cell i wrote into it, we would now need to check
among the set of owners to see if any of them wrote. Since this set is only of
size O(1), the running time would still be polynomial.
Changing the procedures to accommodate ill-behaved PRAM algorithms
(G4) is more subtle. The first change required is that we must now determine
the exact running time T a of the algorithm. Using some upper bound
cause us to falsely reject due to an invalid global store by
some processor after T a . The value of T a is easily determined by evaluating
state(t; halts and accepts. (If it does not
accept, there is no need to worry about ownership violations.) The second,
and more interesting change, is to check all "store" instructions by all active
processors p up to time T a , basically by doing a depth-first search of the
processor activation tree.
CROW-PRAMs and DCFL Recognition 17
procedure Simulate-G4-CROW-PRAM
comment: Modified Main Program, incorporating G4.
begin
while instruction(state(t; 0)) 6= "halt" do t
if accumulator(state(t; 0)) 6= 1 then halt and reject
T a := t
treewalk(0;
halt and accept
procedure treewalk(t; p)
comment: "Visit" processor p at each time - between t and T a , and
any descendants created during that interval. For each,
verify that no non-owner writes occur.
begin
for - := t to T a do
store l" and
then halt and reject; comment: Owner violation; quit.
then
Correctness of this procedure is argued as follows. If the CROW-PRAM
algorithm has no owner write violations, then the procedure is correct, as
before. On the other hand, suppose there is a violation, say at time t by
processor p. Our procedures correctly determine the state of the PRAM up
t. After time t, the state of the PRAM is undefined, whereas
our procedure calls return values as if the violation had not occurred. How-
ever, eventually treewalk will detect the fault. It may reject when evaluating
but on a branch of the processor
activation tree that happens to be explored before p's branch. At the latest,
however, it will detect the fault after evaluating state(t; p). We can count
on this, since our simulation is faithful up to time and the state of
the PRAM at that time contains all the information we need to deduce that
processor p is active at time t, and about to execute a "store" in violation
of the ownership constraint. Hence, eventually we will evaluate state(t; p),
detect the fault, and halt.
The running time of this algorithm is still polynomial, since treewalk(-; p)
is called exactly once for each active processor p, and there are at most
polynomially many processors to be checked.
Thus we have shown the following.
Theorem 3 Any set recognized in time O(log n) on a generalized
CROW-PRAM, i.e., one satisfying generalizations G1-G6 of the basic defi-
nition, is in LOGDCFL.
This completes the proof of the "only if" direction of Theorem 1. The
converse is shown in the following sections.
4 DPDA Definitions and Notation
We assume familiarity with deterministic pushdown automata (DPDA), as
defined for example by Harrison [19], as well as standard variations on this
model.
Our DPDAs have state set Q, input alphabet \Sigma and pushdown alphabet
\Gamma. The empty string is denoted by ffl, the length of string S by jSj, and string
concatenation by "\Delta". At each step either the current topmost pushdown
symbol is popped off the pushdown, or a single new symbol is pushed onto
the pushdown above the current symbol. We assume the transition function
is defined for every possible state, input symbol and pushdown symbol.
Thus
The DPDA begins in state q 0 with as the initial pushdown contents,
with the input head at the left of the input, and accepts by entering state q a
with fl as the only pushdown contents after having advanced the input head
to the right end of the input. We assume the DPDA never fails to read all
CROW-PRAMs and DCFL Recognition 19
the input and always empties its pushdown of all symbols except fl at the
end of the computation. Furthermore, we assume that for all oe 2 \Gamma there is
some transition pushing oe. By standard techniques (see, e.g., Harrison [19,
Section 5.6]), there is a constant c ? 0 such that the DPDA can be assumed
to have the above properties and to halt in time c \Delta n at most, with maximum
pushdown depth n, on any input of length n.
The efficient simulation of a DPDA to be described makes use of the
concepts of surface configuration and instantaneous description, which are
defined relative to a particular input
configuration is a triple (q; i; oe) where q is a state, i is an integer coded in binary
between 0 and n representing the position of the input head, and oe
represents the topmost pushdown symbol. The set of all surface configurations
is denoted U . An instantaneous description (id) of the DPDA is a pair
hu; Si where u is a surface configuration and S is a string representing
all but the topmost symbol of the pushdown (with bottommost pushdown
represented by the rightmost position of S). For convenience, we
refer to S as the stack. Thus, the initial id is h(q and the unique accepting
id is h(q a ; n; fl); ffli. An id where the stack component is ffl is called an
ffl-id. (Note an ffl-id corresponds to a pushdown of one symbol, in the surface
configuration.) For an id I = hu; Si we define height(I) to be jSj, and define
projection functions
A surface configuration is said to be popping if the transition
defined for q, x i and oe pops the pushdown, and is pushing otherwise. An id
is popping or pushing as its surface configuration is popping or pushing.
We write I 1 ' I 2 if id I 2 follows from id I 1 in one step of the DPDA on
input x, I 1 ' t I 2 if I 2 follows I 1 in exactly t steps, and I 1 '   I 2 if I 1 ' t I 2
for some t - 0.
By our definition, ids only represent configurations of the machine with
at least one pushdown symbol; if I 1 is a popping ffl-id there is no id I 2 such
that I 1 ' I 2 . Thus, a popping ffl-id is said to be blocked. This is true even
though the DPDA makes one final move from I 1 (depending on the input
state, and single pushdown symbol in the surface configuration) to
empty its pushdown.
For convenience we assume the final accepting configuration is defined
to pop, so that it will be a blocked id. We denote by hu; the id
modified so that the symbols of S 2 are placed below
the symbols of S 1 on the stack. We illustrate some of the notation with three
useful propositions.
Proposition 4 (Bottom-padding) For all surface configurations u; v and
strings
Note the converse is not true in general, but is in the following case.
Proposition 5 (Bottom-unpadding) For all surface configurations u; v
and strings S 1
and
then
Proposition 6 (Block-continuation) For all surface configurations
In addition to the restrictions on DPDAs discussed above, we assume that
no id can occur twice in a computation of the DPDA when started at any
given id [19, Section 5.6]. This justifies using ids as references to particular
points in computations. E.g., if I ' t J , we could refer to the id J to uniquely
identify the point in the computation t steps after id I.
CROW-PRAMs and DCFL Recognition 21
5 The Basic DPDA Simulation Algorithm
We now will describe a procedure to efficiently simulate a DPDA on input
x of length n. Our algorithm is motivated by the "repeated doubling" idea
used, e.g., by Fortune and Wyllie [15, 39] and Klein and Reif [20], which can
be described in our setting as follows.
Suppose we have computed for all surface configurations u 2 U and all
strings
Si). Then we could easily compute the 2 k+1 step transition function
D k+1 by composing D k with itself:
However, efficiency considerations preclude defining D k for all possible stacks.
Observing that in a computation of 2 k steps only the top 2 k symbols of the
stack are accessed, S can be "split" by writing contains
everything after the first 2 k symbols of S. (S 2 will be empty if S has length
.) Then the above could be rewritten
Although this could be used to limit the number of stacks considered to those
of length at most 2 k , there are still too many for a polynomial number of
processors to compute in O(log n) time. A key observation in constructing
an efficient algorithm is that the number of stacks that need to be considered
can be much more limited than suggested above. It will be shown that it is
sufficient to consider a polynomial-sized set of stacks, provided we use both
stack splitting and a somewhat more complicated doubling technique. To
simplify the set of stacks considered, we compute a function \Delta k in place of
described above, that gives the result after at least 2 k steps rather than
exactly steps. The advantage is that we can use appropriately chosen
break points to keep the stacks simple.
We first describe the algorithm assuming that all of the stacks are explicitly
manipulated. In Section 6, we describe a PRAM implementation that
avoids this by using a more succinct representation than the stacks them-
selves. Two functions on ids are used, \Delta k and LOW k , each of which is
defined inductively on the parameter k. For an id I returns an id
I 2 that results after t steps of the DPDA starting in id I 1 . The value of t
is implicitly determined by the algorithm itself, but it will be shown that
blocked id is reached from I 1 in less than 2 k steps - in this
case t is the number of steps needed to reach the blocked id. Formally, for
ids I 1 and I 2 , \Delta k will satisfy:
I 2 is blocked. (1)
The function LOW k returns the id I 2 that is the id of lowest height
among all ids in the computation from I 1 to \Delta k inclusive, and if there is
more than one id of minimal height in this computation, is the earliest such
id, i.e., the one closest to I 1 . More formally,
(a) I 1
(c)
Given these definitions, to determine if the DPDA accepts x, it is sufficient
to check whether
since the DPDA runs in time at most c \Delta n on any input of length n.
As discussed above it is necessary to restrict the number of stacks on
which must be defined. By careful definition of \Delta the information needed
to compute \Delta k+1 from \Delta k can be restricted to consideration of ids whose stack
contents are suffixes of stacks produced by \Delta k operating on ffl-ids, of which
there are only polynomially many, O(n) in fact. To state this more precisely,
we define SS k (mnemonic for "simple stacks") to be the set of strings over
that represent the bottom portions of stacks in ids in the range of \Delta k
operating on all ffl-ids, i.e.,
is a suffix of stack
Because contains O(n 2 ) elements - one for each u 2 U
and for each suffix of the unique stack determined by u. To motivate this
CROW-PRAMs and DCFL Recognition 23
pp pp ppp pp ppp ppp pppp pppppppppp ppppp
pp ppp ppp ppppp pp pp
pppp pppppp pppp pp
Time
Height
Stack

Figure

1: Illustrating SS k .
definition of SS k , consider the diagram in Figure 1, plotting stack height
versus time in a part of a computation of the DPDA. The diagram shows
a stack S 1 built up by a \Delta k -computation starting from hu; ffli. There must
be a complementary computation, starting at hv; S 1 i that eventually empties
this stack. In Figure 1, part of S 1 is removed in the computation starting at
continuing to hw; S 2 i. The rest of S 1 (consisting of S 2 ) is removed
later beginning at hy; S 2 i. Note that S 2 is a suffix of S 1 - which illustrates
why SS k contains not only stacks arising from \Delta k operating on ffl-ids, but
also all suffixes of such stacks.
We will show later that for k - 0, the stacks in SS k+1 are further restricted
in that each is the concatenation of two strings in SS k , i.e.,
SS
For technical reasons, it will be important to maintain the information specifying
how a stack in SS k+1 is split into two stacks from SS k , rather than
simply treating stacks as undifferentiated character strings. In the interest
of simplicity, however, we will largely ignore this issue in the current section.
It will be treated fully in Section 6.
In arguing the correctness of our algorithm, we prove the following by
induction on k.
are well-defined
for all ids with stacks from SS k ; and
and SS k satisfy properties (1), (2) and (3) above, respectively

The crux of our algorithm and its correctness proof is captured by the following
lemma, which shows that we can progress at least 2 k steps in the simulation
while simultaneously restricting attention to a limited set of stacks,
by applying \Delta k only at selected low points.
Lemma 7 (The be an id with S 2 SS k ,
let
(a) I ' t J for some t - 0,
(b) if J is unblocked, then t - 2 k , and
(c) stack(J) 2 SS k \Delta SS k .
Proof: See Figure 2, which plots stack height versus time in the computation
of the DPDA. There are three distinct cases. In the first and
simplest (not shown in the diagram), the DPDA blocks (attempting to pop
when stack height is zero) before completing 2 k steps. In the second, the
-computation from hsurface(L); ffli blocks before completing 2 k steps, but
we will argue that the overall LOW-\Delta computation does complete at least
steps. In the third case, none of the sub-computations block.
Part (a) follows directly from properties (1) and (2).
From correctness property (2), L is the lowest point in the computation
from I to L (at least), so stack(L) must be a suffix of
is in SS k by assumption. Thus, stack(L) is in SS k . From the definition of
is also in SS k . Thus, stack(J) is in SS k \Delta SS k ,
satisfying (c).
Now assume J is unblocked. Let
M \Delta stack(L). If M is itself unblocked, then from the correctness property
J is at least 2 k steps past L and part (b) follows. On the other
hand, if M is blocked but J is unblocked, then stack(L) must have non-zero
height. In this case J cannot precede \Delta k (I), since otherwise the id
succeeding J would be a point of lower height than L in the range from I
CROW-PRAMs and DCFL Recognition 25
Height
Stack
pp ppp ppppp ppppp pp
ppp pp ppp ppp ppppp
pp pppp ppppppppppp ppppp ppp pp
I
or
Time
stack (J) 2 SS k+1
stack
stack

Figure

2: The LOW-\Delta Lemma.
to \Delta k (I), inclusive, contradicting correctness property (2). It follows that
is unblocked, and part (b) again follows from correctness property (1).The expression for J in the lemma above occurs so frequently that it is
convenient to introduce a special notation for it. We define e
(L) to be
stack(L). For example, the LOW-\Delta Lemma shows that
e
steps or blocks.
Note that for I; L; J as in the LOW-\Delta Lemma, if height(L) ? 0, then J is
necessarily unblocked, and so e
necessarily progresses 2 k steps.
The Lemma applies to an id I only when its stack is in SS k . We
will need an analogous result when I has a stack consisting of two or three
segments each from SS k . The desired low point in such a stack is found
by the following Iterated LOW function. It will be useful later to define the
function to handle any constant number d of stack segments rather than just
three. See Figure 3.
ppp pp pp pp
pppp pp ppp
ppppp pppp pp pp
pppppp pp
ppp ppp ppppppp ppppp pp
Time
e
Sd
Stack
Height
I
e

Figure

3: I-LOW k .
function I-LOW k returns id
comment: Assuming I 2 U \Theta (SS k ) d , return the id of a LOW k point
of nonzero height in a computation from I, if one exists. If not,
return the resulting ffl-id.
begin
for to d do
if
then return
comment: Every segment emptied.
return hu; ffli
The desired generalization of the LOW-\Delta Lemma is the following.
CROW-PRAMs and DCFL Recognition 27
be an id with S 2
(a) I ' t J for some t - 0,
(b) if J is unblocked, then t - 2 k , and
(c) stack(J) 2 (SS k ) d+1 .
Proof: Part (a) follows from propositions (1) and (2). Let
modifies the stack of its argument only by calling
that stack(L) is a suffix of stack(I), and hence by
hypothesis is in (SS k ) d . The stack segment added by the call to e
k is in
establishing part (c).
The key point in establishing (b) is that is a "LOW k
point," hence the LOW-\Delta Lemma can be applied. Specifically, let i 0 be the
last value taken by i in the for loop, and let u 0 be the value taken by u before
the last call to LOW k . Let I
i, and L
is the last value taken by hu; Si before return. Then, letting J
and is easy to see that I '   I 0 \Delta T ,
. Now, the Lemma applies to I 0 ; In particular, if J 0
is unblocked, then it is at least 2 k steps past I 0 , hence J is at least 2 k past
I, satisfying part (b). Thus it suffices to show that J 0 is unblocked whenever
J is unblocked. There are two cases to consider. First, suppose I-LOW k
returns because height(L necessarily
be unblocked. On the other hand, if I-LOW k returns with height(L 0
then by inspection . Thus in either case J is
unblocked if and only if J 0 is unblocked, and part (b) follows. 2
In the code for I-LOW k given above we do not indicate how to determine
the decomposition of its stack parameter into d segments from SS k . In brief,
as suggested in the remark following the definition of SS k , we will retain this
decomposition information when the stacks are initially computed. Detailed
explanation of this issue is deferred to the next section.
In defining LOW k , it will be convenient to use an auxiliary function
"min", that takes as argument a sequence of ids and returns the id of minimal
height in the sequence. If there are several of minimal height, it returns the
leftmost; for our applications, this will always be the earliest in time.
Construction: We are finally ready to define \Delta k and LOW k for all
[Correctness: Following the parts of the definitions of the functions, we
provide, enclosed in square brackets, appropriate parts of the correctness
arguments establishing that
Basis I with
J if 9 J such that I ' J
I otherwise (i.e., if I is blocked);
and
[Correctness: By our assumption that for all oe 2 \Gamma there is some state
pushing oe, we see that SS 0 must be exactly \Gamma [ ffflg, which is exactly the
set of stacks in the domain of \Delta 0 and LOW 0 . By inspection, for all I in
this domain I ' t blocked. Thus (1) is
satisfied. (2) holds because there are only two points in the range of points
under consideration, and min selects the lower of these. (3) holds vacuously.]
The inductive definition of \Delta k+1 and LOW k+1 is done in two phases, first
considering ids with empty stacks, which determine SS k , then considering
ids with stacks in SS k \Gamma ffflg.
Inductive Definition of \Delta k+1 and LOW k+1 on empty stacks: (See

Figure

4.) For k - 0, and for all u
and
Basically, this procedure computes \Delta-LOW-\Delta. Assuming the computation
does not block, the id reached by the first \Delta is 2 k steps past the
starting point, and satisfies the hypothesis of the LOW-\Delta Lemma. Thus,
the subsequent LOW-\Delta pair achieves another 2 k steps progress, and keeps
the resulting stack simple (i.e., in SS k+1 ). This argument is the main ingredient
in the correctness proof, below. The case where the initial id has a
CROW-PRAMs and DCFL Recognition 29
ppp pp pp ppp ppppppp pppp pp pp
ppppppppp pppp pp
ppp pppp ppppppp ppp ppp pppp pp pp
ppp pppppp ppppppppp ppppppp pppp ppppp pp pppp pp pp ppp pp pp
Height
Stack
I
Time
or e

Figure

4: \Delta k+1 (hu; ffli).
non-empty stack will turn out to be similar, except that we need to precede
this with another LOW or two.
[Correctness: Let I = \Delta k (hu; ffli). Note that by the definition of SS k ,
so the hypothesis of the LOW-\Delta Lemma is satisfied by
I. If \Delta k+1 (hu; ffli) is blocked, then (1) is immediately satisfied. If it is not
blocked, then neither is I, so I is at least 2 k steps past hu; ffli, by property
(1). Applying the LOW-\Delta Lemma, e
is at least 2 k steps past
I, hence 2 k+1 past hu; ffli. Thus, \Delta k+1 (hu; ffli) also satisfies (1). Clearly hu; ffli
is the earliest id of height zero at or after itself, so property (2) is trivially
satisfied by LOW k+1 (hu; ffli). Property (3) follows directly from the LOW-\Delta
To complete the definition of \Delta k+1 and LOW k+1 we must now define
them on all ids with non-empty stacks S 2 SS k+1 (as defined by \Delta k+1 's
action on ffl-ids).
Inductive Definition of \Delta k+1 and LOW k+1 on non-empty stacks:
Using I-LOW k we define \Delta k+1 (I) and LOW k+1 (I) for all I = hu; Si with
as the result of the following computations (see
Time
pppp pp ppp pp ppp
pp ppppp pppppp pp ppp
ppp pppp ppp ppp
pp ppppppp pppppp ppp ppp pp
ppp ppppppppppp ppp
pppp ppppppp ppp pp
Height
Stack I-LOW k (I)
e
e
e
or
or
I

Figure

5:

Figure

and
[Correctness: Property (1) follows immediately by applying the I-LOW-\Delta
Lemma twice. Property (2) is satisfied by LOW k+1 (I) since the two points to
which min is applied subsume all the low points of all the subcomputations
comprising \Delta k+1 . Property (3) is inapplicable.]
We remark that from the I-LOW-\Delta Lemma stack(J) above may consist
of three stack segments, even though stack(I) contains only two. This is the
main reason for defining I-LOW k on more than two stack segments.
Finally, we remark that I-LOW k is the identity function on ids with
empty stack, and is equal to LOW k when
CROW-PRAMs and DCFL Recognition 31
the above definition reduces to exactly the same computation as given earlier
for the empty stack case, since
in this case. Similarly, this definition of LOW k+1 (I) also suffices in the case
when ffl. Thus, one could use these more general definitions to
handle both cases.
This completes the definitions of \Delta and LOW, and the proof of their
correctness. To summarize, the key features of this construction are that
LOW k+1 and \Delta k+1 each require only a constant number of calls to the level
procedures, they guarantee at least 2 k+1 progress in the simulation, and
they need to be defined on domains of only polynomial size. In the next
two sections we will exploit these features to give fast implementations on
PRAMs, and small space implementations on PDAs.
6 CROW-PRAM Implementation
The one important issue ignored in the discussion so far is the question of
efficiently handling the stacks. To obtain the desired O(log n) running time,
we need to manipulate stacks of
length\Omega\Gamma n) in unit time. In particular,
when defining
SS k , it is necessary to be able to split S into two segments, each a stack
in SS k . This can be done by retaining the information splitting S into
components when S is originally constructed by
In fact, the decomposition information is really the only information about
S needed to apply the inductive definitions - the actual contents of the
stacks are never consulted in the definitions, except in the base cases. This
fact allows us to replace the actual stacks with abbreviations, avoiding the
explicit manipulation of long character strings, provided the decomposition
information is kept available.
We now introduce the more succinct notation for stacks, revise the algorithms
using this notation, and then discuss the CROW-PRAM implementation
using this notation.
By definition any stack S 2 SS k is a suffix of stack
surface configuration u. We can name S by specifying k; u, and a value h
giving the length of the suffix being considered.
stack reference of level k - 0, abbreviated "(k)-reference,"
is a pair (u; h) with
the stack reference is said to be valid. A (k)-reference (u; h) is said to have
base u, height h, and level k. For convenience, ffl will also be considered a
valid (k)-reference, denoting the empty stack of height 0.
For k - 0, the algorithm will maintain an array SUMMARY k indexed
by surface configurations. The value stored in SUMMARY 0 [u] will be the
actual symbols of stack ffli)). The value of SUMMARY k+1 [u] will be
a pair of valid (k)-references, which will turn out to (recursively) specify the
actual symbols of stack (\Delta k+1 (hu; ffli)).
A valid (k)-reference (u; h) may refer to any suffix of stack
Thus, it is convenient to extend the summary notation to handle references.
The summary of a valid (k)-reference
For it is the length h suffix of SUMMARY 0 [u]. For k - 1 it is
the pair of (k)-references from SUMMARY k [u] adjusted to height h. This
adjustment is carried out as follows. Suppose SUMMARY k [u] is the ordered
pair of (k)-references (v
is the ordered pair (v 1 it is the single
(k)-reference (v 2 ; h). This corresponds to popping the referenced stack until
the desired height h is reached.
Below, we define variants r k , L k , I-L k , MIN of the functions \Delta k , LOW k ,
respectively, of Section 5, that will operate using stack references
and their summary information in place of the stacks themselves.
The function MIN behaves like the version of Section 5, except that it now
returns the surface configuration and height (rather than the full id) of the
leftmost (earliest) of those of its arguments that are of minimum height. The
code for r k only needs to be provided for the case of an empty stack. (The
definition of \Delta k (hu; Si); S 6= ffl was given in Section 5 only to support the
definition of LOW k (hu; Si) and the associated correctness assertions; it was
not otherwise used.) Finally, we note that, in the code below, the contents
of global array SUMMARY k are always set by the function r k before being
referenced by L k .
CROW-PRAMs and DCFL Recognition 33
function r 0 (u: surface) returns (surface, (0)-reference)
comment: Returns the surface and reference corresponding to
and as a side effect, stores stack in the global
array


var
begin
if u is popping then


return (u; ffl)
let hu; ffli ' hv; oei where oe


R := (u; 1)
return (v; R)
function L 0 (u: surface, R: (0)-reference)
returns (surface, (0)-reference)
comment: Returns the surface and reference of the low point in the
interval (u; R) to r 0 (u; R).
var
string
begin


return (v; ffl)
function I-L k (u: surface, R 1 sequence of (k)-references)
returns (surface, sequence of (k)-references)
comment: Returns the surface and a sequence of (k)-references defining
the stack of an unblocked low point (if any) in a computation
starting from (u; R 1 procedure handles any
fixed number d of (k)-references.
var
R: (k)-reference
begin
for to d do
return (u; ffl)
function r k+1 (u: surface) returns (surface,
comment: Returns the surface and reference corresponding to
and as a side effect, stores the summary for
stack
var
1)-reference
begin


return (v 3 ; R)
CROW-PRAMs and DCFL Recognition 35
function L
returns (surface,
comment: Returns the surface and reference corresponding to the
low point in the interval (u; R) to r k+1 (u; R).
var
sequence of (k)-references
1)-reference
begin
let R be (w; h)


be the result of prepending R 2 to the sequence S 1
return
Correctness follows from the argument given in Section 5 using the correspondence
elucidated below. We inductively define a string b
R associated
with each valid (k)-reference R as follows. With each valid (0)-reference
the string b
R consists of the length h suffix of the string
stored in SUMMARY 0 [u]. Furthermore, for each k - 0 and each valid
associate (inductively) the string b
where


By induction on k, one can show that
R, the string associated with the (k)-reference R returned by r k (u), is exactly
stack as defined in Section 5, provided that in the algorithm of
Section 5, each stack b
S is decomposed as specified by SUMMARY [S]. (Re-
call that the exact decomposition used in I-LOW k was left unspecified in
Section 5. We note that, the proofs given there, in particular the proof of
Lemma 8, the I-LOW-\Delta Lemma, hold for any decomposition of a stack in
substrings each in SS k , although we only need the proofs to
hold for the specific decomposition given by SUMMARY .)
Finally, the functions r k and L k defined above can be used for a time
O(log n) parallel algorithm for DCFL recognition on a CROW-PRAM. The
algorithm tabulates r k , SUMMARY k and L k for successively higher values
of k.
for k := 0 to dlog cn e do
for all u 2 U do in parallel
Compute store in a table in global memory. As a
side effect, store SUMMARY k [u].
for all u; v 2 U and all h - 0 for which is a valid
(k)-reference do in parallel
Compute store in a table in global memory.
Each iteration of the loop can be performed with a constant number of
references to previously stored values of r k ; L k , and SUMMARY k .
The implementation of tables indexed by surface configurations and ref-
erences, and the initialization of a unique processor for every array entry are
done using now-standard parallel RAM programming techniques; see Gold-
schlager [17] or Wyllie [39] for examples. Each surface and reference can
be coded by an integer of O(log n) bits, which can be used as a table sub-
script. These techniques also suffice to implement the above algorithm on a
CROW-PRAM satisfying restrictions R1-R3.
Since there are only O(n) surfaces and O(n 2 ) references, the number of
array entries (and hence the number of processors) can be kept to O(n 3 ) by
reusing array space rather than having separate arrays for each value of k
from 0 to log n. The values of SUMMARY k , for example, can be discarded
as soon as the values of SUMMARY k+1 have been computed.
Thus we have shown the following theorem.
Theorem 9 Every DCFL can be recognized by a CROW-PRAM satisfying
restrictions R1-R3 in time O(log n) with O(n 3 ) processors.
Theorems 2 and 9 together establish Theorem 1. We also obtain the
following corollary.
CROW-PRAMs and DCFL Recognition 37
generalizations G1-G4 can be
simulated by CROW-PRAMs subject to restrictions R1-R3 with only a constant
time loss and with only a polynomial increase in number of processors

Proof: It was shown in Section 3 that generalized CROW-PRAMs satisfying
G1-G6 can be simulated by deterministic auxiliary PDAs with log n
space and polynomial time, and thus that languages recognized by such machines
are in Sudborough's class LOGDCFL of languages log space reducible
to deterministic context-free languages. A log space-bounded reduction can
be done on a CROW-PRAM in time O(log n) using the deterministic pointer-
jumping technique of Fortune and Wyllie [15]. See Cook and Dymond [8]
for a detailed description the simulation of log space by a parallel pointer
machine in O(log n) time, and see Lam and Ruzzo [21] for a simulation of
the later model by a O(log n) time-bounded CROW-PRAM. This simulation
is easily made to obey restrictions R1-R3. Finally, by Theorem 9, the resulting
language can be recognized by a CROW-PRAM also obeying restrictions
Following appearance of an earlier version of this paper, Monien, et al. [25]
gave a CREW-PRAM algorithm for DCFL recognition that, for any ffl ?
0, uses O(log n) time and n 2+ffl processors. Their algorithm uses functions
similar to ours, and suggests an approach to improving the processor bound
of the CROW-PRAM algorithm of Theorem 9.
7 Small Space Sequential Implementation
In Section 3 we presented an algorithm for simulating an O(log n) time
CROW-PRAM by a deterministic auxPDA using polynomial time and
O(log 2 n) stack height. This, combined with Theorem 9, yields an alternate
proof of the following result of Rytter.
Theorem 11 (Rytter [33].) L is accepted by a polynomial time logarithmic
space DauxPDA if and only if L is accepted by such a machine that
furthermore uses stack height O(log 2 n).
An analogous result was previously known for nondeterministic PDAs
(Ruzzo [32]), but the best result previous to Rytter's for stack height reduction
in DauxPDAs required superpolynomial time (Harju [18]; c.f. [32] for an
alternative proof).
Corollary 12 (Harju [18].) DCFLs are in DauxPDA space O(log n) and
stack height O(log 2 n).
The following result is also a corollary.
Corollary 13 (Cook [5]; von Braunm-uhl, et al. [38].) DCFLs are in
The time bound for the algorithm sketched above, while polynomial, is
not particularly attractive. As shown by von Braunm-uhl, Cook, Mehlhorn,
recognition is in simultaneous space S(n) and time
O(n 1+ffl =S(n)) on DTMs with random access to their input tapes, for any
log 2 n - S(n) - n. Their algorithm makes general use of its
space resource, i.e., it is not used as a pushdown store, or even as a stack (in
the stack automaton sense; Ginsburg, Greibach, and Harrison [16]).
The goal of the remainder of this section is to sketch an improvement to
our algorithm to achieve time bounds matching those of von Braunm-uhl, et
al., while still using a DauxPDA. Our modifications borrow some of the key
ideas from the von Braunm-uhl, et al. constructions.
First, we outline a more direct algorithm, bypassing the simulation of a
general CROW-PRAM. In Sections 5 and 6, we presented an algorithm for
simulating a DPDA, based on the procedures r k and L k . Our procedure r k
sets the global SUMMARY k array as a side effect, and L k reads from it. It is
easy to reformulate these procedures recursively. In a fully recursive version,
r k would return the summary information as an additional component of
its function value, and accesses to SUMMARY k in L k would be replaced by
appropriate calls to r k , to (re-)compute the desired stack summaries.
Recursive procedures have a straightforward implementation on a space-bounded
deterministic auxiliary PDA. The auxPDA's work tape needs to
be long enough to hold the local variables of a procedure, and the pushdown
CROW-PRAMs and DCFL Recognition 39
height must be d times as large, where d is the depth of recursion, to hold
d "stack frames", each holding copies of the local variables, return address,
etc.
For our procedures, the local variables consist of a few integers plus a
bounded number of surfaces, requiring O(log n) space. The recursion depth is
at most dlog 2 cne. Thus, our procedures can be implemented on a DauxPDA
using space O(log n) and pushdown height O(log 2 n). Furthermore, for our
procedures, each level k makes a bounded number of calls
on level k procedures. Since the depth of recursion is O(log n), the total
number of calls is at most (O(1)) O(log n) = n O(1) . Exclusive of recursive calls,
each procedure takes time O(log n) to manipulate the surfaces, etc., plus,
if necessary O(n) to read inputs. Thus, the total time for the algorithm is
polynomial.
The main idea in improving the time bound is to generalize the construction
in Section 5 to give, for any integer d - 2, procedures r k
d , etc., that
reflect computations of length at least d k , rather than 2 k as before. This
is easily done with the machinery we have already developed. For example,
d is basically the d-fold composition of f r k
d (\Delta)) with itself. Each level
O(d) calls on level k procedures. Thus, the number
of recursive calls, which is the main component of the running time, will be
log d
Again, to keep the induction simple, we can arrange that the stacks that
need to be considered are suffixes of those built by r k+1
d (u), which turn out
to be the concatenation of suffixes of at most d stacks built by r k
d (v), for
various v's. As before, it is important that the list of these v's provides a
succinct but useful "summary" of the stack contents.
One final refinement of this idea is to simulate S(n) steps of the DPDA
in the base case of our procedures, rather than just one step. Then r k
d will
simulate at least S(n) \Delta d k steps.
Implementation of these procedures on a DauxPDA with O(log n) work
tape and O(log 2 n) stack height is straightforward, as before.
Random access to the input tape is useful in our algorithm and in von
Braunm-uhl, et al.'s for the following reason. Simulation of pop moves requires
recomputation of portions of the stack, necessitating access to the
portions of the input read during the corresponding push moves. With ordinary
sequential access to the input tape, even though repositioning the tape
head may be
time-consuming(\Omega\Gamma n)), von Braunm-uhl, et al. show that DCFL
recognition is possible in simultaneous space S(n) and time O(n 2 =S(n)), for
log This is provably optimal. Our techniques appear likely
to be useful in this case as well, although we have not pursued this.

Acknowledgements

We thank Michael Bertol, Philippe Derome, Faith Fich, Klaus-J-orn Lange,
Prabhakar Ragde, and Marc Snir for careful reading of early drafts, and for
useful discussions. Special acknowledgement is due Allan Borodin, without
whom we would never have begun this research.



--R

A comparison of shared and nonshared memory models of parallel computation.
Cache coherence protocols: Evaluation using a multiprocessor simulation model.
The complexity of short two-person games
Characterizations of pushdown machines in terms of time-bounded computers
Deterministic CFL's are accepted simultaneously in polynomial time and log squared space.
Towards a complexity theory of synchronous parallel compu- tation
Upper and lower time bounds for parallel random access machines without simultaneous writes.
Parallel pointer machines.
Indirect addressing and the time relationships of some models of sequential computation.
Hardware complexity and parallel computa- tion
Pointers versus arithmetic in PRAMs.
Parallel random access machines with owned global memory and deterministic context-free language recognition
The complexity of computation on the parallel random access machine.
Towards understanding exclusive read.
Parallelism in random access machines.
Stack automata and com- piling
A universal interconnection pattern for parallel comput- ers
A simulation result for the auxiliary pushdown automata.
Introduction to Formal Language Theory.
Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM
The power of parallel pointer manipulation.

Implementing Cole's parallel mergesort algorithm on owner-write parallel random access machines
Logic and Algorithmic
Fast recognition of deterministic CFL's with a smaller number of processors.
On optimal OROW-PRAM algorithms for computing recursively defined functions
PRAM's towards realistic parallelism: BRAM's.
CREW PRAMs and decision trees.
Restricted CRCW PRAMs.
A characterization of the power of vector machines.
The owner concept for PRAMs.

On the recognition of context-free languages
Parallel time O(log n) recognition of unambiguous context-free languages
Simulation of parallel random access machines by circuits.
On the tape complexity of deterministic context-free lan- guages
Synchronous parallel computation - a survey
The recognition of deterministic CFL's in small time and space.
The Complexity of Parallel Computations.
--TR
Cache coherence protocols: evaluation using a multiprocessor simulation model
Upper and lower time bounds for parallel random access machines without simultaneous writes
Parallel RAMs with owned global memory and deterministic contex-free language recognition
Parallel time <italic>O</> (log <italic>n</>) recognition of unambiguous context-free languages
Parallel time <italic>O</>(log <italic>n</>) acceptance of deterministic CFLs on an exclusive-write P-RAM
The power of parallel pointer manipulation
The complexity of short two-person games
Toward understanding exclusive read
The owner concept for PRAMs
CREW PRAMs and decision trees
Fast recognition of deterministic cfl''s with a smaller number of processors
Restricted CRCW PRAMs
Parallel pointer machines
Pointers versus arithmetic in PRAMs
Stack automata and compiling
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
On the Tape Complexity of Deterministic Context-Free Languages
A universal interconnection pattern for parallel computers
Introduction to Formal Language Theory
Data-Independences of Parallel Random Access Machines
PRAM''s Towards Realistic Parallelism
Parallel Merge Sort on Concurrent-Read Owner-Write PRAM
Parallelism in random access machines
Deterministic CFL''s are accepted simultaneously in polynomial time and log squared space
The complexity of parallel computations

--CTR
Bertsch , M.-J. Nederhof, Fast parallel recognition of LR language suffixes, Information Processing Letters, v.92 n.5, p.225-229, December 2004
CROW-PRAM;owner write;parallel algorithms;DCFL recognition