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:
- 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)
- PDF:
- https://preview.aclanthology.org/revert-3132-ingestion-checklist/1991.iwpt-1.15.pdf