Parallel time O(log N) acceptance of deterministic CFLs
- 1 November 1982
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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 2 processors. 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).Keywords
This publication has 12 references indexed in Scilit:
- Symmetric complementationPublished by Association for Computing Machinery (ACM) ,1982
- On the power of probabilistic choice in synchronous parallel computationsPublished by Springer Nature ,1982
- Hardware complexity and parallel computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- On uniform circuit complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- A unified approach to models of synchronous parallel machinesPublished by Association for Computing Machinery (ACM) ,1978
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- An efficient context-free parsing algorithmCommunications of the ACM, 1970
- On the translation of languages from left to rightInformation and Control, 1965
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965