Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM


Journal Article

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 n3 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 2O(s(n)). The simulation runs in time O(s(n)) on 2O(s(n)) processors and is nearly optimal.

Full Text

Duke Authors

Cited Authors

  • Klein, PN; Reif, JH

Published Date

  • January 1, 1988

Published In

Volume / Issue

  • 17 / 3

Start / End Page

  • 463 - 485

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/0217027

Citation Source

  • Scopus