Algorithms for Deterministic Incremental Dependency Parsing

2 Dependency Parsing

1. When is a dependency graph well-formed, in Nivre’s definition?
   ROOT: node 0 has no head. SINGLE-HEAD: every node has at most one head and one label. ACYCLICITY: there are no cycles. Such a graph is a dependency forest; if also connected, a dependency tree rooted at 0. A forest becomes a tree by attaching all other roots to node 0.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §2, pp. 515–517
2. Define PROJECTIVITY for a dependency graph.
   For every arc \((i, l, j)\) and every node \(k\) between \(i\) and \(j\), \(k\) is reachable from \(i\) (\(i \to^* k\)). Equivalently, every node’s projection (the nodes reachable from it) is continuous, the dependency analogue of banning discontinuous constituents.
   • Nivre, 2008, Algorithms for Deterministic Incremental Dependency Parsing (Computational Linguistics), §2, pp. 515–517