Deciding Equivalence of Top-Down XML Transformations in Polynomial Time

Many useful XML transformations can be formulated through deterministic top-down tree transducers. A canonical form for such transducers is presented which allows to decide equivalence of their induced transformations in polynomial time. If the transducer is total, the canonical form can be obtained in polynomial time as well.

back to publications
back to project page