Answers are grounded in this paper and cite their sources.
Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n⁴) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n⁵). For a common special case that was known to allow O(n³) parsing (Eisner, 1997), we present an O(n³) algorithm with an improved grammar constant.
No takes yet. Share an insight, caveat, or question.
Eisner et al. (1999) studied this question.