Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticle

DOI

Open Access permissions

Open

Author(s)

Kilian Gebhardt, Mark Jan Nederhof, Heiko Vogler

School/Research organisations

Abstract

We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of both components together, discontinuous structures result. Several types of hybrid grammars are characterized. We also discuss grammar induction from treebanks. The main advantage over existing frameworks is the ability of hybrid grammars to separate discontinuity of the desired structures from time complexity of parsing. This permits exploration of a large variety of parsing algorithms for discontinuous structures, with different properties. This is confirmed by the reported experimental results, which show a wide variety of running time, accuracy and frequency of parse failures.
Close

Details

Original languageEnglish
Pages (from-to)465-520
Number of pages56
JournalComputational Linguistics
Volume43
Issue number3
Early online date15 Sep 2017
DOIs
Publication statusPublished - Sep 2017

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

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

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

Related by journal

  1. Splittability of bilexical context-free grammars is undecidable

    Nederhof, M. J. & Satta, G., Dec 2011, In : Computational Linguistics. 37, 4, p. 867-879 13 p.

    Research output: Contribution to journalArticle

  2. A general technique to train language models on language models

    Nederhof, M. J., Jun 2005, In : Computational Linguistics. 31, 2, p. 173-185 13 p.

    Research output: Contribution to journalArticle

ID: 249016829

Top