@article{ebce904bc6f8441882b7ca182be0761a,
title = "Deciding equivalence of top-down XML transformations in polynomial time",
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.",
keywords = "Equivalence, Minimization, Top-down tree transducer, XML",
author = "Joost Engelfriet and Sebastian Maneth and Helmut Seidl",
note = "Funding Information: Funding support for P.S.-B. came from a Royal Society university research fellowship. L.S. and R.V. were partially supported by grants from the FONDECYT (1110597) and the Millennium Institute for Fundamental and Applied Biology (MIFAB). C.U. was funded by a doctoral fellowship from CONICYT and also by Beca Gastos Operacionales CONICYT 21110394. Funding support for P.V.D. came from the Instituto Milenio de Oceanograf{\'i}a. The influx cell sorter was purchased with FONDEQUIP EQM130267.",
year = "2009",
month = aug,
doi = "10.1016/j.jcss.2009.01.001",
language = "English",
volume = "75",
pages = "271--286",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "5",
}