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

Mark Jan Nederhof, Markus Teichmann, Heiko Vogler

Research output: Contribution to journal › Article › peer-review

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.
Original languageEnglish
Pages (from-to)203-246
JournalJournal of Automata, Languages Combinatorics
Volume21
Issue number3
DOIs
Publication statusPublished - 12 Dec 2016

Keywords

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

Access to Document

  • Nederhof_2016_Grammars_JALC_AAM

    © 2016, Institut für Informatik, Justus-Liebig-Universität Giessen. This work has been made available online by kind permission of the publisher. This is the author created manuscript following peer review accepted at JALC and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.25596/jalc-2016-203

    Accepted author manuscript, 590 KB

    Cite this