Output details

Deciding equivalence of top-down XML transformations in polynomial time

<10> Originality: First canonical normal form for deterministic top-down tree transducers (DTOPs). This makes it possible to test equivalence of total transducers in polynomial time.

Significance: Has many applications: for instance, constructing a Gold-style learning algorithm (as presented in our PODS 2010 paper), and deciding the important database properties of determinacy and rewriting (as shown in our MFCS 2013 paper).

Rigour: Presents a new normal form for DTOPs in which any output symbol is produced as early as possible. Gives fine-grained complexity statements in terms of big-O notation. Decidability of equivalence is proved also for more general DTOPs with look-ahead.