On the complexity of typechecking top-down XML transformations

DOI10.1016/j.tcs.2004.10.035zbMath1080.68021OpenAlexW2143127574MaRDI QIDQ555775

Wim Martens, Frank Neven

Publication date: 10 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.035

zbMATH Keywords

structural recursion on treestop-down recursive transformations

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Visibly pushdown transducers, Frontiers of tractability for typechecking simple XML transformations, On the minimization of XML schemas and tree automata for unranked trees, Schemas for unordered XML on a DIME, Conjunctive query containment over trees using schema information, Typechecking top-down XML transformations: Fixed input or output schemas, Polynomial-time inverse computation for accumulative functions with multiple data traversals, Modulo constraints and the complexity of typechecking XML views, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, A Survey on Decidable Equivalence Problems for Tree Transducers, Classes of Tree Homomorphisms with Decidable Preservation of Regularity, Deciding equivalence of top-down XML transformations in polynomial time

Cites Work

• Frontiers of tractability for typechecking simple XML transformations
• Macro tree transducers
• A note on the reduction of two-way automata to one-way automata
• An observation on time-storage trade off
• Haskell overloading is DEXPTIME-complete
• Typechecking for XML transformers
• XML with data values: Typechecking revisited.
• A formal model for an expressive fragment of XSLT
• Query automata over finite trees
• Alternating Pushdown and Stack Automata
• Deciding Equivalence of Finite Tree Automata
• Typechecking XML views of relational databases
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item