Deciding equivalence of top-down XML transformations in polynomial time
From MaRDI portal
Publication:1021574
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
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