Deciding equivalence of top-down XML transformations in polynomial time

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


Many useful XML transformations can be expressed by deterministic top-down tree transducers. A normal form is presented for such transducers (extended with the facility to inspect their input trees). A transducer in normal form has a unique canonical form which can be obtained by a minimization procedure, in polynomial time. Thus, equivalence of transducers in normal form can be decided in polynomial time. If the transducer is total, the normal form can be obtained in polynomial time as well.

Original languageEnglish
Pages (from-to)271-286
Number of pages16
JournalJournal of Computer and System Sciences
Issue number5
StatePublished - Aug 2009


  • Equivalence
  • Minimization
  • Top-down tree transducer
  • XML


Dive into the research topics of 'Deciding equivalence of top-down XML transformations in polynomial time'. Together they form a unique fingerprint.

Cite this