Parallel Time $O(\log n)$ Acceptance of Deterministic CFL s on an Exclusive-Write P-RAM
Philip N. Klein, John H. Reif · SIAM Journal on Computing · 1988
We give an algorithm for accepting a deterministic context-free language on the P-RAM, an exclusive-write, concurrent-read model of parallel computation. Whereas on inputs of length n, a deterministic push-down automaton will use time linear in n, our algorithm runs in time $O(\log n)$ on $n^3 $ processors. The algorithm is easily generalized to permit parallel simulation of any deterministic auxiliary pushdown automaton that uses space $s(n) \geqq \log n$ and time $2^{O(s(n))} $. The simulation runs in time $O(s(n))$ on $2^{O(s(n))} $ processors, and is nearly optimal, since we observe that any language accepted by a P-RAM in time $T(n)$ is accepted by a deterministic auxiliary pushdown automaton in space $T(n)$ and time $2^{O(T(n)^2 )} $.