Slow and Fast Parallel Recognition
Hans
de Vreught
author
Job
Honig
author
1991-feb" 13-25"
text
Proceedings of the Second International Workshop on Parsing Technologies
Association for Computational Linguistics
Cancun, Mexico
conference publication
In the first part of this paper a slow parallel recognizer is described for general CFG’s. The recognizer runs in $Θ(n^3/p(n))$ time with $p(n) = O(n^2)$ 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(n^6)$ processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.
de-vreught-honig-1991-slow
https://aclanthology.org/1991.iwpt-1.15
1991-feb" 13-25"
127
135