Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticlepeer-review

Author(s)

Mark Jan Nederhof, Markus Teichmann, Heiko Vogler

School/Research organisations

Abstract

For the class of linear context-free tree grammars, we define a decidable property called self-embedding. We prove that each non-self-embedding grammar in this class generates a regular tree language and show how to construct the equivalent regular tree grammar.
Close

Details

Original languageEnglish
Pages (from-to)203-246
JournalJournal of Automata, Languages Combinatorics
Volume21
Issue number3
DOIs
Publication statusPublished - 12 Dec 2016

    Research areas

  • Context-free tree grammar, Regular tree grammar, Self-embedding, Natural language processing

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

Related by journal

  1. Confluent monadic string-rewriting systems and automatic structures

    Otto, F. & Ruskuc, N., 2001, In: Journal of Automata, Languages Combinatorics. 6, p. 375-388

    Research output: Contribution to journalArticlepeer-review

ID: 248206212

Top