@article{nederhof-2019-calculating,
    title = "Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time",
    author = "Nederhof, Mark-Jan",
    editor = "Lee, Lillian  and
      Johnson, Mark  and
      Roark, Brian  and
      Nenkova, Ani",
    journal = "Transactions of the Association for Computational Linguistics",
    volume = "7",
    year = "2019",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://preview.aclanthology.org/ingest-emnlp/Q19-1018/",
    doi = "10.1162/tacl_a_00268",
    pages = "283--296",
    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."
}