Determinacy and rewriting of functional top-down and MSO tree transformations

DOI10.1016/j.jcss.2016.11.001zbMath1356.68050OpenAlexW2557073715MaRDI QIDQ730500

Sebastian Maneth, Joost Engelfriet, Michael Benedikt

Publication date: 28 December 2016

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.11.001

zbMATH Keywords

MSO definable tree transducerstop-down tree transducersview-query determinacy

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Static analysis of XML security views and query rewriting
• Determinacy and query rewriting for conjunctive queries and views
• The equivalence problem for deterministic MSO tree transducers is decidable
• Compositions of extended top-down tree transducers
• Deciding equivalence of top-down XML transformations in polynomial time
• Macro forest transducers
• Extended multi bottom-up tree transducers
• Macro tree transducers
• Tree transducers, L systems, and two-way machines
• Transductions des langages de Chomsky
• On tree transducers for partial functions
• On injectivity of deterministic top-down tree 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.
• Tree acceptors and some of their applications
• A Survey on Decidable Equivalence Problems for Tree Transducers
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Streaming Tree Transducers
• The Power of Extended Top-Down Tree Transducers
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Equivalence of finite-valued tree transducers is decidable
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Determinacy and Subsumption for Single-Valued Bottom-Up Tree Transducers
• Generalized finite automata theory with an application to a decision problem of second-order logic

This page was built for publication: Determinacy and rewriting of functional top-down and MSO tree transformations