Generalized Syntax Directed Translation, Tree Transducers, and Linear Space

DOI10.1137/0207030MaRDI QIDQ4158495zbMATH OpenOpenAlexFDO

Authors Brenda S. Baker

Publication date 1978

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0207030

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Trees (05C05) Formal languages and automata (68Q45)

Cited in

(12)

• Macro tree transducers
• Tree transducers, L systems, and two-way machines
• Systolic trees and systolic language recognition by tree automata
• Tree transducers with external functions
• Decidability of the finiteness of ranges of tree transductions
• The translation power of top-down tree-to-graph transducers
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Transductions of dags and trees
• Three hierarchies of transducers
• Conversion and parsing of tree transducers for syntactic pattern analysis
• Branching synchronization grammars with nested tables
• Semantic-syntax-directed translation and its application to image processing

This page was built for publication: Generalized Syntax Directed Translation, Tree Transducers, and Linear Space

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