Thus, transition-based parsers normally run in linear or quadratic time, using greedy deterministic search or fixed-width beam search Attardi, 2006;Johansson and Nugues, 2007;Titov and Henderson, 2007), and graph-based models support exact inference in at most cubic time, which is efficient enough to make global discriminative training practically feasible (McDonald et al., 2005a;McDonald et al., 2005b).
one problem that still has not found a satisfactory solution in data-driven dependency parsing is the treatment of discontinuous syntactic constructions, usually modeled by non-projective dependency trees, as illustrated in Figure 1.