Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticlepeer-review

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. Calculating the optimal step of arc-eager parsing for non-projective trees

    Nederhof, M. J., 19 Apr 2021, Proceedings of the 16th Conference of the European Chapter of the Association of Computational Linguistics (EACL 2021). Association for Computational Linguistics, p. 2273–2283

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

  2. A derivational model of discontinuous parsing

    Nederhof, M-J. & Yli-Jyrä, A., 10 Aug 2020, In: Information and Computation. In press, 104619.

    Research output: Contribution to journalArticlepeer-review

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

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

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 journalArticlepeer-review

  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 journalArticlepeer-review

ID: 249016829

Top