Linear Context-Free Tree Languages and Inverse Homomorphisms

Publikation: Beitrag in FachzeitschriftKonferenzartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer104454
FachzeitschriftInformation and Computation
Jahrgang269
PublikationsstatusVeröffentlicht - 2019
Peer-Review-StatusJa

Externe IDs

Scopus 85071551102

Schlagworte

Schlagwörter

  • context-free tree grammars, homomorphisms