Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM

DOI10.1137/0217027zbMath0652.68066OpenAlexW2052746194MaRDI QIDQ3798245

John H. Reif, Philip N. Klein

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217027

zbMATH Keywords

context-free languagePRAMparallel simulationpushdown automatonmodel of parallel computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (4)

Fast parallel recognition of LR language suffixes ⋮ Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition ⋮ Parallel recognition and ranking of context-free languages ⋮ Fast recognition of deterministic cfl's with a smaller number of processors

This page was built for publication: Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM