Linear Context-Free Tree Languages and Inverse Homomorphisms

Autor:	Osterholzer, Johannes, Dietze, Toni, Herrmann, Luisa
Rok vydání:	2015
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
Popis:	We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. The proof is by contradiction: we encode Dyck words into a context-free tree language and prove that its preimage under a certain linear tree homomorphism cannot be generated by any context-free tree grammar. A positive result can still be obtained: the linear monadic context-free tree languages are closed under inverse linear tree homomorphisms. Comment: 30 pages, 1 figure; fixed a variable collision (t') in Section 7
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1510.04881 Zobrazit plný text záznamu View this record from Arxiv