Paper: Polynomial Time Parsing Of Combinatory Categorial Grammars

ACL ID P90-1001
Title Polynomial Time Parsing Of Combinatory Categorial Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors

In this paper we present a polynomial time pars- ing algorithm for Combinatory Categorial Grammar. The recognition phase extends the CKY algorithm for CFG. The process of generating a representation of the parse trees has two phases. Initially, a shared for- est is build that encodes the set of all derivation trees for the input string. This shared forest is then pruned to remove all spurious ambiguity.