Title :
On CKY-parsing of context-free grammars in parallel
Author :
Chandwani, M. ; Puranik, M. ; Chaudhari, N.S.
Author_Institution :
Dept. of Comput. Eng., SGS Inst. of Technol. & Sci., Indore, India
Abstract :
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(n2) processors. The proposed algorithm uses a very simple procedure, and provides multiple parses for ambiguous languages
Keywords :
context-free grammars; parallel algorithms; CKY-parsing algorithm; PRAM models; ambiguous languages; context-free grammars; parallel algorithm; parallel random access machine; parallel time; processors; sentence; string; Artificial intelligence; Binary trees; Production;
Conference_Titel :
TENCON '92. ''Technology Enabling Tomorrow : Computers, Communications and Automation towards the 21st Century.' 1992 IEEE Region 10 International Conference.
Conference_Location :
Melbourne, Vic.
Print_ISBN :
0-7803-0849-2
DOI :
10.1109/TENCON.1992.271967
