• Acyclicity: there are no directed cycles in G. • Node 0 is a root, i.e., there are no arcs of the form (i, l, 0) in A.
transition-based parsers (Yamada and Matsumoto, 2003;Nivre et al., 2004), which are the focus of this work, use local training to make greedy decisions that deterministically select the next parser state.