The copying power of one-state tree transducers

DOI10.1016/0022-0000(82)90019-8zbMath0495.68073MaRDI 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 homomorphisms; amount of nonclosure under copying operations; one-state deterministic top-down tree transducers; syntax-directed translation of context-free languages; tree transducer hierarchy

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

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