Scholars@Duke

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

Publication ,  Journal Article
Klein, PN; Reif, JH
Published in: SIAM Journal on Computing
January 1, 1988
Published version (DOI)

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.

Duke Scholars

John H. Reif
Author John H. Reif Computer Science

Published In

SIAM Journal on Computing

DOI

10.1137/0217027

ISSN

0097-5397

Publication Date

January 1, 1988

Volume

17

Issue

3

Start / End Page

463 / 485

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Klein, P. N., & Reif, J. H. (1988). Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM. SIAM Journal on Computing, 17(3), 463–485. https://doi.org/10.1137/0217027
Klein, P. N., and J. H. Reif. “Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM.” SIAM Journal on Computing 17, no. 3 (January 1, 1988): 463–85. https://doi.org/10.1137/0217027.
Klein PN, Reif JH. Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM. SIAM Journal on Computing. 1988 Jan 1;17(3):463–85.
Klein, P. N., and J. H. Reif. “Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM.” SIAM Journal on Computing, vol. 17, no. 3, Jan. 1988, pp. 463–85. Scopus, doi:10.1137/0217027.
Klein PN, Reif JH. Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM. SIAM Journal on Computing. 1988 Jan 1;17(3):463–485.

Published In

SIAM Journal on Computing

DOI

10.1137/0217027

ISSN

0097-5397

Publication Date

January 1, 1988

Volume

17

Issue

3

Start / End Page

463 / 485

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics