On the complexity of typechecking top-down XML transformations

DOI10.1016/J.TCS.2004.10.035MaRDI QIDQ555775zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1953124
• Typechecking top-down XML transformations: Fixed input or output schemas
• Frontiers of tractability for typechecking simple XML transformations
• Typechecking for XML transformers
• XML with data values: Typechecking revisited.

Cites work

• A formal model for an expressive fragment of XSLT
• A note on the reduction of two-way automata to one-way automata
• Alternating Pushdown and Stack Automata
• An observation on time-storage trade off
• Deciding Equivalence of Finite Tree Automata
• Frontiers of tractability for typechecking simple XML transformations
• Haskell overloading is DEXPTIME-complete
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1953123 (Why is no real title available?)
• scientific article; zbMATH DE number 2080402 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2241906 (Why is no real title available?)
• Macro tree transducers
• Query automata over finite trees
• Typechecking for XML transformers
• Typechecking XML views of relational databases
• XML with data values: Typechecking revisited.

Cited in

(25)

• Deciding equivalence of top-down XML transformations in polynomial time
• Typechecking for XML transformers
• XML with data values: Typechecking revisited.
• Visibly pushdown transducers
• Conjunctive query containment over trees using schema information
• Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
• Modulo constraints and the complexity of typechecking XML views
• A survey on decidable equivalence problems for tree transducers
• XML Type Checking Using High-Level Tree Transducer
• On the Complexity of Verifying Consistency of XML Specifications
• scientific article; zbMATH DE number 2080402 (Why is no real title available?)
• Type checking of tree walking transducers
• Node query preservation for deterministic linear top-down tree transducers
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• Typechecking XML views of relational databases
• A simple and efficient step towards type-correct XSLT transformations
• Database Theory - ICDT 2005
• Database Theory - ICDT 2005
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• Distributed XML design
• An algebraic approach to the equivalence checking of deterministic top-down tree 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
• Typechecking top-down XML transformations: Fixed input or output schemas

This page was built for publication: On the complexity of typechecking top-down XML transformations

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