  We first present a minimal feature set for transition-based dependency
parsing, continuing a recent trend started by Kiperwasser and Goldberg (2016a)
and Cross and Huang (2016a) of using bi-directional LSTM features. We plug our
minimal feature set into the dynamic-programming framework of Huang and Sagae
(2010) and Kuhlmann et al. (2011) to produce the first implementation of
worst-case O(n^3) exact decoders for arc-hybrid and arc-eager transition
systems. With our minimal features, we also present O(n^3) global training
methods. Finally, using ensembles including our new parsers, we achieve the
best unlabeled attachment score reported (to our knowledge) on the Chinese
Treebank and the "second-best-in-class" result on the English Penn Treebank.
