Deciding equivalence of top-down XML transformations in polynomial time

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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
Publication statusPublished - 2009

Keywords / Materials (for Non-textual outputs)

  • Minimization
  • Top–down tree transducer
  • Equivalence


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

Cite this