Deciding equivalence of top-down XML transformations in polynomial time

DOI10.1016/j.jcss.2009.01.001zbMath1167.68032OpenAlexW2164592058MaRDI QIDQ1021574

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

Publication date: 8 June 2009

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.2009.01.001

zbMATH Keywords

XMLequivalenceminimizationtop-down tree transducer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Data structures (68P05)

Related Items (11)

Definability results for top-down tree transducers ⋮ EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS ⋮ Deciding origin equivalence of weakly self-nesting macro tree transducers ⋮ How to decide functionality of compositions of top-down tree transducers ⋮ Definability Results for Top-Down Tree Transducers ⋮ Functionality of compositions of top-down tree transducers is decidable ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ Determinacy and rewriting of functional top-down and MSO tree transformations ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Largest common prefix of a regular tree language ⋮ Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of typechecking top-down XML transformations
• The equivalence problem for deterministic MSO tree transducers is decidable
• An efficient automata approach to some problems on context-free grammars.
• Macro forest transducers
• Macro tree transducers
• Tree transducers, L systems, and two-way machines
• Top-down tree transducers with two-way tree walking look-ahead
• Minimization algorithms for sequential transducers
• Tree pattern query minimization
• Top-down tree transducers with deterministic top-down look-ahead
• Generalized sequential machine maps
• Top-down tree transducers with regular look-ahead
• Minimal Ascending and Descending Tree Automata
• Containment and equivalence for a fragment of XPath
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Mappings and grammars on trees
• Translations on a context free grammar

This page was built for publication: Deciding equivalence of top-down XML transformations in polynomial time