Output string languages of compositions of deterministic macro tree transducers

DOI10.1006/JCSS.2001.1816MaRDI QIDQ1608323zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet, Sebastian Maneth

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) Algebraic theory of languages and automata (68Q70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 2087226
• scientific article; zbMATH DE number 1330139
• scientific article; zbMATH DE number 1954390
• scientific article; zbMATH DE number 3965457
• Pushdown machines for the macro tree transducer

Cites work

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

Cited in

(10)

• Multiple context-free tree grammars: lexicalization and characterization
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Deciding origin equivalence of weakly self-nesting macro tree transducers
• A survey on decidable equivalence problems for tree transducers
• scientific article; zbMATH DE number 1330139 (Why is no real title available?)
• scientific article; zbMATH DE number 1954390 (Why is no real title available?)
• scientific article; zbMATH DE number 2087226 (Why is no real title available?)
• A pumping lemma for output languages of macro tree transducers
• Polyregular functions: characterisations and refutations
• The generative power of delegation networks

This page was built for publication: Output string languages of compositions of deterministic macro tree transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1608323)