@article{kuhlmann-jonsson-2015-parsing,
    title = "Parsing to Noncrossing Dependency Graphs",
    author = "Kuhlmann, Marco  and
      Jonsson, Peter",
    editor = "Collins, Michael  and
      Lee, Lillian",
    journal = "Transactions of the Association for Computational Linguistics",
    volume = "3",
    year = "2015",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://preview.aclanthology.org/fix-sig-urls/Q15-1040/",
    doi = "10.1162/tacl_a_00158",
    pages = "559--570",
    abstract = "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 {\ensuremath{\geq}} 2."
}