Algorithms for Deterministic Incremental Dependency Parsing

5.1 Non-Projective Parsing

1. Describe the transitions of the non-projective list-based parser.
   For \(i\) at the head of \(\lambda_1\) and \(j\) first in the buffer: LEFT-ARC adds \(j \to i\), RIGHT-ARC adds \(i \to j\), and NO-ARC adds nothing; each moves \(i\) to \(\lambda_2\). SHIFT\(_\lambda\) concatenates \(\lambda_1.\lambda_2\), appends \(j\), and empties \(\lambda_2\). Arcs require that the dependent has no head and no cycle results (\(\neg[i \to^* j]\) or \(\neg[j \to^* i]\)).
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §5.1, pp. 530–533
2. What is the complexity of the non-projective list-based algorithm, and why?
   \(O(n^2)\) time: there are at most \(n\) shifts, and between the \((i-1)\)th and \(i\)th shift each other transition shrinks \(\lambda_1\), so at most \(i\) of them: \(\sum_i (i + 1)\) transitions. Space is \(O(n)\). The acyclicity check is near-constant with union-find (\(O(\alpha(n))\) amortized).
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §5.1, pp. 530–533