We define a restricted class of non-projective trees that 1) covers many natural
language sentences; and 2) can be parsed exactly with a generalization of the
popular arc-eager system for projective trees (Nivre, 2003). Crucially, this
generalization only adds constant overhead in run-time and space keeping the
parser’s total run-time linear in the worst case. In empirical experiments, our
proposed transition-based parser is more accurate on average than both the
arc-eager system or the swap-based system, an unconstrained non-projective
transition system with a worst-case quadratic runtime (Nivre, 2009).