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
Editors:
Masaru Tomita, Martin Kay, Robert Berwick, Eva Hajicova, Aravind Joshi, Ronald Kaplan, Makoto Nagao, Yorick Wilks
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
127–135
Language:
URL:
https://aclanthology.org/1991.iwpt-1.15
DOI:
Bibkey:
Cite (ACL):
Hans de Vreught and Job Honig. 1991. Slow and Fast Parallel Recognition. In Proceedings of the Second International Workshop on Parsing Technologies, pages 127–135, Cancun, Mexico. Association for Computational Linguistics.
Cite (Informal):
Slow and Fast Parallel Recognition (de Vreught & Honig, IWPT 1991)
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.15.pdf