On CKY-parsing of context-free grammars in parallel
Manohar Chandwani, Madhuvanti Puranik, Narendra S. Chaudhari · 2003
A parallel version of the CKY-parsing algorithm for context-free grammar is presented. The algorithm uses parallel random access machine (PRAM) models of computation and parses a string (or sentence) of length n in parallel time O(n log n), employing O(n/sup 2/) processors. The proposed algorithm uses a very simple procedure, and provides multiple parses for ambiguous languages.>