%0 Conference Proceedings
%T Slow and Fast Parallel Recognition
%A de Vreught, Hans
%A Honig, Job
%S Proceedings of the Second International Workshop on Parsing Technologies
%D 1991
%8 feb 13 25
%I Association for Computational Linguistics
%C Cancun, Mexico
%F de-vreught-honig-1991-slow
%X In the first part of this paper a slow parallel recognizer is described for general CFG’s. The recognizer runs in Θ(n³/p(n)) time with p(n) = O(n²) 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⁶) processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.
%U https://aclanthology.org/1991.iwpt-1.15
%P 127-135