A Learning Algorithm for Top-Down XML Transformations

Abstract : A generalization from string to trees and from languages to translations is given of the classical result that any regular language can be learned from examples: it is shown that for any deterministic top-down tree transformation there exists a sample set of polynomial size (with respect to the minimal transducer) which allows to infer the translation. Until now, only for string transducers and for simple relabeling tree transducers, similar results had been known. Learning of deterministic top-down tree transducers (DTOPs) is far more involved because a DTOP can copy, delete, and permute its input subtrees. Thus, complex dependencies of labeled input to output paths need to be maintained by the algorithm. First, a Myhill-Nerode theorem is presented for DTOPs, which is interesting on its own. This theorem is then used to construct a learning algorithm for DTOPs. Finally, it is shown how our result can be applied to XML transformations (e.g. XSLT programs). For this, a new DTD-based encoding of unranked trees by ranked ones is presented. Over such encodings, DTOPs can realize many practically interesting XML transformations which cannot be realized on first-child/next-sibling encodings.

A preliminary extended version can be found at http://www.grappa.univ-lille3.fr/~niehren/Papers/learn-dtop/long.pdf .

Type de document :
Communication dans un congrès
ACM. 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun 2010, Indianapolis, United States. ACM Press, pp.285-296, 2010
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00460489
Contributeur : Joachim Niehren <>
Soumis le : mardi 22 juin 2010 - 13:33:23
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 22 octobre 2012 - 12:45:58

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00460489, version 2

Collections

Citation

Aurélien Lemay, Sebastian Maneth, Joachim Niehren. A Learning Algorithm for Top-Down XML Transformations. ACM. 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun 2010, Indianapolis, United States. ACM Press, pp.285-296, 2010. 〈inria-00460489v2〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

310