Linear Context-Free Tree Languages and Inverse Homomorphisms
Aus International Center for Computational Logic
Linear Context-Free Tree Languages and Inverse Homomorphisms
Johannes OsterholzerJohannes Osterholzer, Toni DietzeToni Dietze, Luisa HerrmannLuisa Herrmann
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
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
- 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
@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}
}