High level tree transducers and iterated pushdown tree transducers

DOI10.1007/BF02915449zbMath0633.68073OpenAlexW2061491534MaRDI QIDQ1096399

Heiko Vogler, Joost Engelfriet

Publication date: 1988

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02915449

zbMATH Keywords

tree grammarstree transducerssyntax-directed semantics of programming languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

The translation power of top-down tree-to-graph transducers ⋮ Transducers and the decidability of independence in free monoids ⋮ A hierarchy of deterministic top-down tree transformations ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Tree-stack automata ⋮ Iterated stack automata and complexity classes ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ Deterministic top-down tree transducers with iterated look-ahead ⋮ Functional programs as compressed data ⋮ Verification of tree-processing programs via higher-order mode checking ⋮ Composing stack-attributed tree transducers ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Weighted automata with storage ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ Principal abstract families of weighted tree languages ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ Modular tree transducers ⋮ Output string languages of compositions of deterministic macro tree transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Macro tree transducers
• Pushdown machines for the macro tree transducer
• The OI-hierarchy is closed under control
• Tree transducers, L systems, and two-way machines
• The formal power of one-visit attribute grammars
• The IO- and OI-hierarchies
• Attribute grammars and recursive program schemes. I. II
• A generalized approach to formal languages
• IO and OI. I
• Some definitional suggestions for automata theory
• Generalized sequential machine maps
• Pushdown tree automata
• An automata-theoretical characterization of the OI-hierarchy
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• An order-algebraic definition of knuthian semantics
• Three hierarchies of transducers
• Semantics of context-free languages
• Tree generating regular systems
• Full AFLs and nested iterated substitution
• Mappings and grammars on trees
• Translations on a context free grammar