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. However, the closure can be proved for the linear monadic context-free tree languages.
展开▼
