Typechecking for XML transformers

DOI10.1016/S0022-0000(02)00030-2zbMath1026.68045MaRDI QIDQ1394797

Dan Suciu, Tova Milo, Victor Vianu

Publication date: 25 June 2003

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

zbMATH Keywords

typechecking problem

Mathematics Subject Classification ID

Database theory (68P15)

Related Items (43)

Deciding definability by deterministic regular expressions ⋮ Decision Problems of Tree Transducers with Origin ⋮ Tree Transformations and Dependencies ⋮ Controlled Term Rewriting ⋮ Deciding determinism of caterpillar expressions ⋮ Term Rewriting with Prefix Context Constraints and Bottom-Up Strategies ⋮ Complementing deterministic tree-walking automata ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Decision problems of tree transducers with origin ⋮ On the tree-transformation power of XSLT ⋮ Well-definedness and semantic type-checking for the nested relational calculus ⋮ Automata for XML -- a survey ⋮ Frontiers of tractability for typechecking simple XML transformations ⋮ Backward type inference for XML queries ⋮ Deciding origin equivalence of weakly self-nesting macro tree transducers ⋮ Deterministic Caterpillar Expressions ⋮ Characterizing attributed tree translations in terms of macro tree transducers ⋮ One-variable context-free hedge automata ⋮ XML with data values: Typechecking revisited. ⋮ State complexity of the concatenation of regular tree languages ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ Typechecking top-down XML transformations: Fixed input or output schemas ⋮ Nondeterministic and co-nondeterministic implies deterministic, for data languages ⋮ Synthesis of deterministic top-down tree transducers from automatic tree relations ⋮ Polynomial-time inverse computation for accumulative functions with multiple data traversals ⋮ XML graphs in program analysis ⋮ Verification of tree-processing programs via higher-order mode checking ⋮ Structural properties of XPath fragments ⋮ On the complexity of typechecking top-down XML transformations ⋮ Operational state complexity of nested word automata ⋮ A programmable editor for developing structured documents based on bidirectional transformations ⋮ Modulo constraints and the complexity of typechecking XML views ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Boolean operations and inclusion test for attribute-element constraints ⋮ Tree Automata over Infinite Alphabets ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Automata on Gauss Words ⋮ The time complexity of typechecking tree-walking tree transducers ⋮ Two-way pebble transducers for partial functions and their composition ⋮ Macro forest transducers ⋮ Efficient inclusion checking for deterministic tree automata and XML schemas

Uses Software

• XPath

Cites Work

• Regular path queries with constraints
• Complexity results for two-way and multi-pebble automata and their logics
• Regular expression types for XML
• Alternation
• Translations on a context free grammar
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Typechecking for XML transformers