Deciding equivalence of top-down XML transformations in polynomial time

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume75
Issue number5
DOIs
Publication statusPublished - 2009

Keywords

  • Minimization
  • Top–down tree transducer
  • Equivalence

Fingerprint

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

Cite this