However, our formalism is more flexible and our algorithm more practical.
we make the following contributions: • theoretically, we show that for a large class of modern shift-reduce parsers, dynamic programming is in fact possible and runs in polynomial time as long as the feature functions are bounded and monotonic (which almost always holds in practice); • practically, dynamic programming is up to five times faster (with the same accuracy) as conventional beam-search on top of a stateof-the-art shift-reduce dependency parser; • as a by-product, dynamic programming can output a forest encoding exponentially many trees, out of which we can draw better and longer k-best lists than beam search can; • finally, better and faster search also leads to better and faster learning.