Linear context-free tree languages and inverse homomorphisms

DOI10.1016/j.ic.2019.104454zbMath1436.68185arXiv1510.04881OpenAlexW2970734988MaRDI QIDQ2280337

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)

Full work available at URL: https://arxiv.org/abs/1510.04881

zbMATH Keywords

counterexampletree languageclosure propertypreimagecontext-freenesslinear homomorphism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (3)

Special issue: selected papers of the 10th international conference on language and automata theory and applications, LATA 2016 ⋮ Linear context-free tree languages and inverse homomorphisms ⋮ Linear weighted tree automata with storage and inverse linear tree homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equivalence of tree adjoining grammars and monadic linear context-free tree grammars
• Morphismes et bimorphismes d'arbres
• Un théorème de duplication pour les forets algébriques
• A generalized approach to formal languages
• IO and OI. II
• Linear context-free tree languages and inverse homomorphisms
• Closure properties of linear context-free tree languages with an application to optimality theory
• Complexity of Uniform Membership of Context-Free Tree Grammars
• Multidimensional trees and a Chomsky–Schützenberger–Weir representation theorem for simple context-free tree grammars
• The Power of Extended Top-Down Tree Transducers
• Formal computations of non deterministic recursive program schemes
• Une propri\'et\'e des forêts alg\'ebriques « de greibach \ra
• Initial Algebra Semantics and Continuous Algebras
• Forêts Algébriques et Homomorphismes Inverses
• Mappings and grammars on trees

This page was built for publication: Linear context-free tree languages and inverse homomorphisms