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

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