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

Mark Jan Nederhof, Markus Teichmann, Heiko Vogler

Research output: Contribution to journalArticlepeer-review


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
Issue number3
Publication statusPublished - 12 Dec 2016


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

Cite this