Article3084: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Luisa Herrmann (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Johannes |ErsterAutorNachname=Osterholzer |FurtherAuthors=Toni Dietze; Luisa Herrmann }} {{Article |Referiert=1…“) |
Luisa Herrmann (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
|ErsterAutorVorname=Johannes | |ErsterAutorVorname=Johannes | ||
|ErsterAutorNachname=Osterholzer | |ErsterAutorNachname=Osterholzer | ||
|FurtherAuthors=Toni Dietze | |FurtherAuthors=Luisa Herrmann; Toni Dietze | ||
}} | }} | ||
{{Article | {{Article | ||
| Zeile 16: | Zeile 16: | ||
|Abstract=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. | |Abstract=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. | ||
|DOI Name=https://doi.org/10.1016/j.ic.2019.104454 | |DOI Name=https://doi.org/10.1016/j.ic.2019.104454 | ||
|Projekt=QuantLA | |||
|Forschungsgruppe=Computational Logic | |Forschungsgruppe=Computational Logic | ||
}} | }} | ||
Version vom 11. April 2022, 14:38 Uhr
Linear context-free tree languages and inverse homomorphisms
Johannes OsterholzerJohannes Osterholzer, Luisa HerrmannLuisa Herrmann, Toni DietzeToni Dietze
Johannes Osterholzer, Luisa Herrmann, Toni Dietze
Linear context-free tree languages and inverse homomorphisms
Information and Computation, 269, 2019
Linear context-free tree languages and inverse homomorphisms
Information and Computation, 269, 2019
- 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{OHD2019,
author = {Johannes Osterholzer and Luisa Herrmann and Toni Dietze},
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}
}
