Linear Context-Free Tree Languages and Inverse Homomorphisms

From International Center for Computational Logic

Toggle side column

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
  • 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}
}