The copying power of one-state tree transducers

DOI10.1016/0022-0000(82)90019-8zbMath0495.68073OpenAlexW2022505233MaRDI QIDQ1169826

Joost Engelfriet, Sven Skyum

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90019-8

zbMATH Keywords

tree homomorphismsamount of nonclosure under copying operationsone-state deterministic top-down tree transducerssyntax-directed translation of context-free languagestree transducer hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Multiple context-free tree grammars: lexicalization and characterization ⋮ Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations ⋮ Macro tree transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree transducers, L systems, and two-way machines
• Copying theorems
• Intercalation lemmas for tree transducer languages
• Description of developmental languages using recurrence systems
• Decomposition Theorems for Various Kinds of Languages Parallel in Nature
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Composition of top-down and bottom-up tree transductions
• Three hierarchies of transducers
• On extensions of ALGOL-like languages
• Tree transducers, L systems and two-way machines (Extended Abstract)
• An extension of ALGOL-like languages