Linear Context-Free Tree Languages and Inverse Homomorphisms
Publikation: Beitrag in Fachzeitschrift › Konferenzartikel › Beigetragen › Begutachtung
Beitragende
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.
Details
Originalsprache | Englisch |
---|---|
Aufsatznummer | 104454 |
Fachzeitschrift | Information and Computation |
Jahrgang | 269 |
Publikationsstatus | Veröffentlicht - 2019 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85071551102 |
---|
Schlagworte
Schlagwörter
- context-free tree grammars, homomorphisms