Slow and Fast Parallel Recognition

Hans de Vreught, Job Honig


Abstract
In the first part of this paper a slow parallel recognizer is described for general CFG’s. The recognizer runs in 𝛩(n3/p(n)) time with p(n) = O(n2) processors. It generalizes the items of the Earley algorithm to double dotted items, which are more suited to parallel parsing. In the second part a fast parallel recognizer is given for general CFG’s. The recognizer runs in O(log n) time using O(n6) processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.
Anthology ID:
1991.iwpt-1.15
Volume:
Proceedings of the Second International Workshop on Parsing Technologies
Month:
February 13-25
Year:
1991
Address:
Cancun, Mexico
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
127–135
Language:
URL:
https://aclanthology.org/1991.iwpt-1.15
DOI:
Bibkey:
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.15.pdf