liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Parsing to Noncrossing Dependency Graphs
Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2492-9872
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-5288-3330
2015 (English)In: Transactions of the Association for Computational Linguistics, ISSN 2307-387X, Vol. 3, 559-570 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Association for Computational Linguistics, 2015. Vol. 3, 559-570 p.
Keyword [en]
natural language processing, algorithms, complexity theory
National Category
Language Technology (Computational Linguistics)
Identifiers
URN: urn:nbn:se:liu:diva-124718OAI: oai:DiVA.org:liu-124718DiVA: diva2:902487
Available from: 2016-02-11 Created: 2016-02-11 Last updated: 2016-03-09

Open Access in DiVA

No full text

Other links

link to article

Search in DiVA

By author/editor
Kuhlmann, MarcoJonsson, Peter
By organisation
Human-Centered systemsFaculty of Science & EngineeringSoftware and Systems
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 214 hits
ReferencesLink to record
Permanent link

Direct link