Parallel time O(log N) acceptance of deterministic CFLs
John H. Reif · 1982
We give a parallel RAM algorithm for simulating a deterministic auxiliary pushdown machine. If the pushdown machine uses space s(n) ≥ log n and time 2O(s(n))then our parallel simulation algorithm takes time O(s(n)) and requires 2processors. Thus any deterministic context free language is accepted in time O(log n) by our parallel RAM algorithm using a polynomial number of processors. (Our algorithm can easily be extended to also accept the LR(k) languages in time O(log n) and 2O(k)Processors. Our simulation algorithm is near optimal for parallel RAMs, since we show that the language accepted in time T(n) by a parallel RAM is accepted by a deterministic auxiliary pushdown machine with space T(n) and time 2O(T(n)2).