Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as dynamic oracle. Unlike existing algorithms, it is applicable if the training corpus contains non-projective structures. We then show that for a projective training corpus, the time complexity can be improved from cubic to linear.
Original languageEnglish
Pages (from-to)283-296
Number of pages14
JournalTransactions of the Association for Computational Linguistics
Volume7
DOIs
Publication statusPublished - 31 May 2019

Keywords

  • Formal language theory
  • Automata theory

Fingerprint

Dive into the research topics of 'Calculating the optimal step in shift-reduce dependency parsing: from cubic to linear time'. Together they form a unique fingerprint.

Cite this