Linear Context-Free Tree Languages and Inverse Homomorphisms

Johannes OsterholzerJohannes Osterholzer, Toni DietzeToni Dietze, Luisa HerrmannLuisa Herrmann

DOI Link

Johannes Osterholzer, Toni Dietze, Luisa Herrmann
Linear Context-Free Tree Languages and Inverse Homomorphisms
In Adrian-Horia DediuJan Janoušek, Carlos Martín-Vide, Bianca Truthe, eds., Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, 478-489, 2016. Springer

Details
Bibtex

KurzfassungAbstract
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.
Projekt:Project: QuantLA
Forschungsgruppe:Research Group: Computational LogicComputational Logic

The final publication is available at Springer via http://dx.doi.org/https://doi.org/10.1007/978-3-319-30000-9_37.

@inproceedings{ODH2016,
  author    = {Johannes Osterholzer and Toni Dietze and Luisa Herrmann},
  title     = {Linear Context-Free Tree Languages and Inverse Homomorphisms},
  editor    = {Adrian-Horia {DediuJan} Janou{\v{s}}ek and Carlos
               Mart{\'{\i}}n-Vide and Bianca Truthe},
  booktitle = {Language and Automata Theory and Applications},
  series    = {Lecture Notes in Computer Science},
  volume    = {9618},
  publisher = {Springer},
  year      = {2016},
  pages     = {478-489},
  doi       = {https://doi.org/10.1007/978-3-319-30000-9_37}
}