Deciding Equivalence of Top-Down XML Transformations in Polynomial Time.
Sebastian Maneth, Helmut Seidl · 2007
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.