Pushdown machines for the macro tree transducer

DOI10.1016/0304-3975(86)90052-6zbMath0619.68065OpenAlexW2079625718MaRDI QIDQ1089810

Heiko Vogler, Joost Engelfriet

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/pushdown-machines-for-the-macro-tree-transducer(1433b707-a9eb-439e-986d-fc83cc997d27).html

zbMATH Keywords

attribute grammarspushdown machinesindexed grammarsmacro grammarsmacro tree transducersstorage type simulationtree- to-string transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55)

Related Items (28)

Synthesized and inherited functions. A new computational model for syntax-directed semantics ⋮ Transducers and the decidability of independence in free monoids ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ The OI-hierarchy is closed under control ⋮ Branching synchronization grammars with nested tables ⋮ Weighted iterated linear control ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ A hierarchy of deterministic top-down tree transformations ⋮ Unnamed Item ⋮ Word-mappings of level 2 ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Unnamed Item ⋮ Tree-stack automata ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ 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 ⋮ An implementation of syntax directed functional programming on nested- stack machines ⋮ Storage-to-tree transducers with look-ahead ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Basic tree transducers ⋮ Look-ahead on pushdowns ⋮ Weighted automata with storage ⋮ Linear weighted tree automata with storage and inverse linear tree homomorphisms ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ Principal abstract families of weighted tree languages ⋮ Complete formal systems for equivalence problems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended macro grammars and stack controlled machines
• Macro tree transducers
• 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
• IO and OI. II
• Some definitional suggestions for automata theory
• Generalized sequential machine maps
• Proof of correctness of data representations
• Pushdown tree automata
• Tree automata and attribute grammars
• On the power of list iteration
• On deterministic indexed languages
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Attribute Grammars and Mathematical Semantics
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• An order-algebraic definition of knuthian semantics
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• Full AFLs and nested iterated substitution
• Mappings and grammars on trees
• Semantics of context-free languages: Correction
• Translations on a context free grammar

This page was built for publication: Pushdown machines for the macro tree transducer