Paper: Efficient Parsing For Bilexical Context-Free Grammars And Head Automaton Grammars

ACL ID P99-1059
Title Efficient Parsing For Bilexical Context-Free Grammars And Head Automaton Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1999
Authors

Several recent stochastic parsers use bilexical grammars, where each word type idiosyncrat- ically prefers particular complements with par- ticular head words. We present O(n 4) parsing algorithms for two bilexical formalisms, improv- ing the prior upper bounds of O(n5). For a com- mon special case that was known to allow O(n 3) parsing (Eisner, 1997), we present an O(n 3) al- gorithm with an improved grammar constant.