Paper: The Complexity Of Parsing With Extended Categorial Grammars

ACL ID C90-2041
Title The Complexity Of Parsing With Extended Categorial Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1990
Authors

Instead of incorporating a gap-percolation mecha- nism for handling certain "movement" phenomena, the extended categorial grammars contain special in- ference rules for treating these problems. The Lam- bek categorial grammar is one representative of the grammar family under consideration. It allows for a restricted use of hypothetical reasoning. We define a modification of the Cocke-Younger-Kasami (CKY) parsing algorithm which covers this additional de- ductive power and analyze its time complexity.