Efficient parsing for bilexical context-free grammars and head automation grammars

摘要

Several recent stochastic parsers use bilexical grammars,where each word type idiosyncratically prefers particular complements with particular head words.We present O(n~4) parsing algorithms for two bilexical formalisms,improving the prior upper bounds of O(n~5).For a common special case that was known to allow O(n~3) parsing (Eisner,1997),we present an O(n~3) algorithm with an improved grammar constant.