Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticle

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

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 journalArticle

ID: 248206212

Top