Output string languages of compositions of deterministic macro tree transducers

DOI10.1006/jcss.2001.1816zbMath1013.68124OpenAlexW2056475755MaRDI QIDQ1608323

Sebastian Maneth, Joost Engelfriet

Publication date: 4 August 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/9675d09e0af07aa58ce5a313e59df126195de745

zbMATH Keywords

macro tree transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Algebraic theory of languages and automata (68Q70)

Related Items

Deciding origin equivalence of weakly self-nesting macro tree transducers, The generative power of delegation networks, Multiple context-free tree grammars: lexicalization and characterization, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, A Survey on Decidable Equivalence Problems for Tree Transducers

Cites Work

• Fundamental properties of infinite trees
• Macro tree transducers
• High level tree transducers and iterated pushdown tree transducers
• The OI-hierarchy is closed under control
• Tree transducers, L systems, and two-way machines
• The IO- and OI-hierarchies
• Attribute grammars and recursive program schemes. I. II
• Iterated stack automata and complexity classes
• IO and OI. II
• On tree transducers for partial functions
• Hierarchy theorems for two-way finite state transducers
• Decidability of the finiteness of ranges of tree transductions
• The generating power of total deterministic tree transducers
• The translation power of top-down tree-to-graph transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• The Rational Index: A Complexity Measure for Languages
• Extension of tabled 0L-systems and languages
• Top-down tree transducers with regular look-ahead
• Three hierarchies of transducers
• Formal Languages: Origins and Directions
• Mappings and grammars on trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item