Le développement du Web a motivé l’apparition de nombreux types de formats de données semi-structurées pour les problèmes liés aux technologies du Web, comme le traitement des documents ou la gestion de base de données. Nous étudions ici la conversion des données semi-structurées d’un schéma à un autre. Pour le traitement de documents, c’est la technologie XML qui offre la solution la plus puissante à ce problème. En XML, les données semi-structurées sont des arbres de données dont les schémas peuvent être définis par des automates d’arbres avec contraintes sur les valeurs de données. Les transformations de documents sont spécifiées en XSLT, un langage fonctionnel muni de requêtes logiques XPath. Le cœur de XSLT correspond aux transducteurs d’arbres à macros avec navigation par requêtes XPath. Nous proposons de nouveaux algorithmes pour l’apprentissage des transducteurs d’arbres, basés sur des méthodes d’inférence grammaticale. Nous abordons la restriction de schéma, l’anticipation (lookahead), ou la concaténation dans la sortie. 1. Nous donnons une forme normale et un algorithme d’apprentissage dans le modèle de Gold avec des ressources limitées pour les transducteurs d’arbres de haut en bas déterministes avec une inspection de domaine régulière. 2. Nous montrons comment apprendre des fonctions rationnelles, décrites par les transducteurs de mots déterministes avec anticipation. Nous proposons une nouvelle forme normale qui permet un apprentissage avec des ressources polynomiales. 3. Pour les transducteurs arbre-vers-mot linéaires, qui permet la concaténation dans sa sortie, nous présentons une forme normale, et montrons comment décider l’équivalence en temps polynomial.
Directeurs de thèse : Joachim Niehren, Aurélien Lemay (co-encadrant) Rapporteurs : Olivier Carton, Helmut Seidl Examinateurs : Sebastian Maneth, Sophie Tison
Thèse de l'équipe LINKS soutenue le 07/11/2016
français
English