Article3084

PublikationenPublications

• Nach AutorBy Author
  • Luisa HerrmannLuisa Herrmann
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

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
Information and Computation, 269, 2019

• Details
• Bibtex

• KurzfassungAbstract
  We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. In fact, we prove a stronger result: we encode Dyck words into a linear 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.
• Projekt:Project: QuantLA
• Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{ODH2019,
  author    = {Johannes Osterholzer and Toni Dietze and Luisa Herrmann},
  title     = {Linear context-free tree languages and inverse homomorphisms},
  journal   = {Information and Computation},
  volume    = {269},
  publisher = {Elsevier},
  year      = {2019},
  doi       = {https://doi.org/10.1016/j.ic.2019.104454}
}