Publications [#236921] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Klein, PN; Reif, JH, Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM, SIAM Journal on Computing, vol. 17 no. 3 (January, 1988), pp. 463-485, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/16)

   Abstract:
   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³ processors. The algorithm is easily generalized to permit parallel simulation of any deterministic auxiliary pushdown automaton that uses space s(n)≥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.