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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs
Linköping University, Department of Computer and Information Science, Human-Centered systems.
Linköping University, Department of Computer and Information Science, Human-Centered systems. (Natural Language Processing)ORCID iD: 0000-0002-2492-9872
2017 (English)In: Proceedings of the 15th International Conference on Parsing Technologies, 2017Conference paper, Published paper (Refereed)
Abstract [en]

Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint-crossing (1ec) graphs, which has high coverage on standard data sets. Our main contribution is a characterization of 1ec graphs as a subclass of the graphs with pagenumber at most 3. Building on this we show how to extend an existing parsing algorithm for 1-endpoint-crossing trees to the full class. While the runtime complexity of the extended algorithm is polynomial in the length of the input sentence, it features a large constant, which poses a challenge for practical implementations.

Place, publisher, year, edition, pages
2017.
National Category
Language Technology (Computational Linguistics)
Identifiers
URN: urn:nbn:se:liu:diva-141168ISBN: 978-1-945626-73-9 (print)OAI: oai:DiVA.org:liu-141168DiVA: diva2:1144052
Conference
International Conference on Parsing Technologies
Available from: 2017-09-25 Created: 2017-09-25 Last updated: 2017-09-25

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Kurtz, RobinKuhlmann, Marco
By organisation
Human-Centered systems
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar

Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf