Parsing to Noncrossing Dependency Graphs

Marco Kuhlmann and Peter Jonsson. Parsing to Noncrossing Dependency Graphs. Transactions of the Association for Computational Linguistics, 3:559–570, 2015.


We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restriction to noncrossing dependency graphs. Our main contribution is a cubic-time exact inference algorithm for this class. We extend this algorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most $k$ and show that the resulting optimization problem is NP-hard for $k ≥ 2$.