Macro tree transducers, attribute grammars, and MSO definable tree translations.

DOI10.1006/inco.1999.2807zbMath1045.68585OpenAlexW2086959507MaRDI QIDQ1854312

Sebastian Maneth, Joost Engelfriet

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1383ea1c2136ba64f03b2d0976324a777f3b2f8f

zbMATH Keywords

monadic second-order logic

Mathematics Subject Classification ID

Related Items (33)

A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ Decision Problems of Tree Transducers with Origin ⋮ Tree Transformations and Dependencies ⋮ Definable transductions and weighted logics for texts ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Decision problems of tree transducers with origin ⋮ EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS ⋮ A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead ⋮ Deciding origin equivalence of weakly self-nesting macro tree transducers ⋮ Characterizing attributed tree translations in terms of macro tree transducers ⋮ Deciding whether an attributed translation can be realized by a top-down transducer ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ Balancedness of MSO transductions in polynomial time ⋮ Extended Multi Bottom-Up Tree Transducers ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Copyless cost-register automata: structure, expressiveness, and closure properties ⋮ Compositions of extended top-down tree transducers ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Polynomial-time inverse computation for accumulative functions with multiple data traversals ⋮ GETGRATS ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ Streamable regular transductions ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Regular Programming for Quantitative Properties of Data Streams ⋮ Streaming ranked-tree-to-string transducers ⋮ Copyful Streaming String Transducers ⋮ Extended multi bottom-up tree transducers ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Linear deterministic multi bottom-up tree transducers ⋮ Output string languages of compositions of deterministic macro tree transducers ⋮ An operational and denotational approach to non-context-freeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• Fundamental properties of infinite trees
• Increasing modularity and language-independency in automatically generated compilers
• Macro tree transducers
• High level tree transducers and iterated pushdown tree transducers
• Composition and evaluation of attribute coupled grammars
• Tree transducers, L systems, and two-way machines
• The formal power of one-visit attribute grammars
• Attribute grammars and recursive program schemes. I. II
• The string generating power of context-free hypergraph grammars
• On multiple context-free grammars
• Tree transducers with external functions
• Rational tree relations
• The generating power of total deterministic tree transducers
• Monadic second-order definable graph transductions: a survey
• The translation power of top-down tree-to-graph transducers
• Logical description of context-free graph languages
• Attributed tree transducers cannot induce all deterministic bottom-up tree transformations
• Semantic evaluation from left to right
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Handbook of Graph Grammars and Computing by Graph Transformation
• Three hierarchies of transducers
• Semantics of context-free languages
• Translations on a context free grammar

This page was built for publication: Macro tree transducers, attribute grammars, and MSO definable tree translations.