Macro tree transducers

DOI10.1016/0022-0000(85)90066-2zbMath0588.68039OpenAlexW2128517960MaRDI QIDQ1073576

Joost Engelfriet, Heiko Vogler

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/macro-tree-transducers(e0c0830a-277a-461c-988d-3df740ea50ff).html

zbMATH Keywords

context-free tree grammarstop-down tree transducersregular look-aheadsyntax-directed semantics

Mathematics Subject Classification ID

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

Related Items

Visibly Pushdown Transducers with Look-Ahead, The translation power of top-down tree-to-graph transducers, Closure properties of linear context-free tree languages with an application to optimality theory, Synthesized and inherited functions. A new computational model for syntax-directed semantics, Pushdown machines for the macro tree transducer, Tree Transformations and Dependencies, High level tree transducers and iterated pushdown tree transducers, Decision problems of tree transducers with origin, On the tree-transformation power of XSLT, A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, Visibly pushdown transducers, Deaccumulation techniques for improving provability, A Mechanized Theory of Regular Trees in Dependent Type Theory, Backward type inference for XML queries, The equivalence problem for letter-to-letter bottom-up tree transducers is solvable, Deciding origin equivalence of weakly self-nesting macro tree transducers, Characterizing attributed tree translations in terms of macro tree transducers, The generative power of delegation networks, Iterated linear control and iterated one-turn pushdowns, Look-ahead removal for total deterministic top-down tree transducers, A hierarchy of deterministic top-down tree transformations, An Algebra for Tree-Based Music Generation, A complete rewriting system for a monoid of tree transformation classes, XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles, Algebraic fusion of functions with an accumulating parameter and its improvement, 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, Multiple context-free tree grammars: lexicalization and characterization, Context-free hypergraph grammars have the same term-generating power as attribute grammars, Polynomial-time inverse computation for accumulative functions with multiple data traversals, Tree transducers with external functions, Verification of tree-processing programs via higher-order mode checking, Storage-to-tree transducers with look-ahead, On the complexity of typechecking top-down XML transformations, Composing stack-attributed tree transducers, Modulo constraints and the complexity of typechecking XML views, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, Unnamed Item, Basic tree transducers, Look-ahead on pushdowns, Unnamed Item, Determinacy and rewriting of functional top-down and MSO tree transformations, A Survey on Decidable Equivalence Problems for Tree Transducers, Regular Programming for Quantitative Properties of Data Streams, Streaming ranked-tree-to-string transducers, Join-Lock-Sensitive Forward Reachability Analysis for Concurrent Programs with Dynamic Process Creation, Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time, Deciding equivalence of top-down XML transformations in polynomial time, Decidability of the finiteness of ranges of tree transductions, The equivalence of bottom-up and top-down tree-to-graph transducers, Macro forest transducers, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Macro tree transducers, attribute grammars, and MSO definable tree translations., The complexity of the exponential output size problem for top-down and bottom-up tree transducers, On injectivity of deterministic top-down tree transducers, Modular tree transducers, Output string languages of compositions of deterministic macro tree transducers, An operational and denotational approach to non-context-freeness, A pumping lemma for output languages of macro tree transducers

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The copying power of one-state tree transducers
• Hypergrammars: An extension of macrogrammars
• A generalized approach to formal languages
• IO and OI. II
• Generalized sequential machine maps
• A syntax directed compiler for ALGOL 60
• On the power of list iteration
• Bounded nesting in macro grammars
• Bottom-up and top-down tree transformations— a comparison
• Initial Algebra Semantics and Continuous Algebras
• Top-down tree transducers with regular look-ahead
• Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
• An order-algebraic definition of knuthian semantics
• Composition of top-down and bottom-up tree transductions
• Three hierarchies of transducers
• A Characterization of Machine Mappings
• Algebraic automata and context-free sets
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Nested Stack Automata
• Mappings and grammars on trees
• Semantics of context-free languages: Correction
• Translations on a context free grammar