Linear context-free tree languages and inverse homomorphisms
From MaRDI portal
Publication:2280337
DOI10.1007/978-3-319-30000-9_37zbMATH Open1436.68185arXiv1510.04881OpenAlexW2970734988MaRDI QIDQ2280337FDOQ2280337
Authors: Johannes Osterholzer, Toni Dietze, Luisa Herrmann 
Publication date: 18 December 2019
Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)
Abstract: 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. A positive result can still be obtained: the linear monadic context-free tree languages are closed under inverse linear tree homomorphisms.
Full work available at URL: https://arxiv.org/abs/1510.04881
Recommendations
- Linear context-free tree languages and inverse homomorphisms
- Homomorphisms preserving deterministic context-free languages
- scientific article; zbMATH DE number 1456959
- Linear weighted tree automata with storage and inverse linear tree homomorphisms
- Closure properties of linear context-free tree languages with an application to optimality theory
Cites Work
- Title not available (Why is that?)
- IO and OI. II
- Initial Algebra Semantics and Continuous Algebras
- Linear context-free tree languages and inverse homomorphisms
- Mappings and grammars on trees
- Closure properties of linear context-free tree languages with an application to optimality theory
- The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
- Morphismes et bimorphismes d'arbres
- Weighted extended tree transducers
- The Power of Extended Top-Down Tree Transducers
- Title not available (Why is that?)
- A generalized approach to formal languages
- Formal computations of non deterministic recursive program schemes
- Un théorème de duplication pour les forets algébriques
- Title not available (Why is that?)
- Une propri\'et\'e des forêts alg\'ebriques « de greibach \ra
- Forêts Algébriques et Homomorphismes Inverses
- Multidimensional trees and a Chomsky–Schützenberger–Weir representation theorem for simple context-free tree grammars
- Complexity of Uniform Membership of Context-Free Tree Grammars
Cited In (10)
- Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016
- Semigroups of linear tree languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- On inferring linear single-tree languages
- Linearity and nondeletion on monadic context-free tree grammars
- Linear weighted tree automata with storage and inverse linear tree homomorphisms
- Linear context-free tree languages and inverse homomorphisms
- The partial clone of linear tree languages
- Height functions and linear languages
This page was built for publication: Linear context-free tree languages and inverse homomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2280337)
