Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticle

DOI

Open Access permissions

Open

Author(s)

School/Research organisations

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.
Close

Details

Original languageEnglish
Pages (from-to)283-296
Number of pages14
JournalTransactions of the Association for Computational Linguistics
Volume7
DOIs
Publication statusPublished - 31 May 2019

    Research areas

  • Formal language theory, Automata theory

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Regular transductions with MCFG input syntax

    Nederhof, M. J. & Vogler, H., 23 Sep 2019, Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing. Maletti, A. & Vogler, H. (eds.). Dresden: Association for Computational Linguistics, p. 56-64 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. Hybrid grammars for parsing of discontinuous phrase structures and non-projective dependency structures

    Gebhardt, K., Nederhof, M. J. & Vogler, H., Sep 2017, In : Computational Linguistics. 43, 3, p. 465-520 56 p.

    Research output: Contribution to journalArticle

  3. A probabilistic model of Ancient Egyptian writing

    Nederhof, M. J. & Rahman, F., 1 Jul 2017, In : Journal of Language Modelling. 5, 1, p. 131-163

    Research output: Contribution to journalArticle

  4. A derivational model of discontinuous parsing

    Nederhof, M. J. & Yli-Jyra, A., 2017, Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Drewes, F., Martin-Vide, C. & Truthe, B. (eds.). Cham: Springer, p. 299-310 (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10168).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Non-self-embedding linear context-free tree grammars generate regular tree languages

    Nederhof, M. J., Teichmann, M. & Vogler, H., 12 Dec 2016, In : Journal of Automata, Languages Combinatorics. 21, 3, p. 203-246

    Research output: Contribution to journalArticle

ID: 259065142

Top