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

DOI10.1016/J.JCSS.2016.11.001MaRDI QIDQ730500zbMATH OpenOpenAlexFDO

Authors Sebastian Maneth, Michael Benedikt, Joost Engelfriet

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

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

Recommendations

• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Determinacy and subsumption for single-valued bottom-up tree transducers
• Determinacy and query rewriting for conjunctive queries and views
• Rewriting Conjunctive Queries Determined by Views
• Datalog Rewritings of Regular Path Queries using Views

Cites work

• scientific article; zbMATH DE number 3714978 (Why is no real title available?)
• scientific article; zbMATH DE number 3566209 (Why is no real title available?)
• scientific article; zbMATH DE number 3594667 (Why is no real title available?)
• scientific article; zbMATH DE number 3597890 (Why is no real title available?)
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• A survey on decidable equivalence problems for tree transducers
• Bottom-up and top-down tree transformations— a comparison
• Compositions of extended top-down tree transducers
• Deciding equivalence of top-down XML transformations in polynomial time
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Determinacy and query rewriting for conjunctive queries and views
• Determinacy and subsumption for single-valued bottom-up tree transducers
• Equivalence of finite-valued tree transducers is decidable
• Extended multi bottom-up tree transducers
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph structure and monadic second-order logic. A language-theoretic approach
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Macro forest transducers
• Macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• On injectivity of deterministic top-down tree transducers
• On tree transducers for partial functions
• Static analysis of XML security views and query rewriting
• The Power of Extended Top-Down Tree Transducers
• The equivalence problem for deterministic MSO tree transducers is decidable
• Top-down tree transducers with regular look-ahead
• Transductions des langages de Chomsky
• Tree acceptors and some of their applications
• Tree transducers, L systems, and two-way machines
• Weighted extended tree transducers

Cited in

(2)

• When is a functional tree transduction deterministic?
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730500)