Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Formation doctorale

Thèse de

Antoine Ndione

mercredi 16 avril 2014
Amphithéâtre de l'IRCICA

Appartenance approchée à un langage de mots ou d’arbres

Directeur de Thèse : Joachim Niehren Rapporteurs : Michel de Rougemont, Tugkan Batu Membres : Fréderic Magniez, Aurélien Lemay, Sophie Tison

Lobjectif de cette thèse est dobtenir des algorithmes sous linéaire permettant de répondre à des problèmes de décision dans les bases de données XML. Plus précisément, on sinspire du property testing, pour décider approximativement si un arbre darité non bornée est valide par rapport à une DTD ; ou plus généralement si un tel arbre est reconnu par un automate darbre.

On a conduit nos études en étudiant dabord le cas plus simple des mots. On a alors considéré lappartenance approché dun mot à un langage régulier représenté par un automate non-déterministe. Pour résoudre ce problème, et par rapport à la distance dédition entres les mots, nous proposons un algorithme (ou tester) dont la complexité en temps est polynomial en la taille de lautomate aussi bien quen la précision (où le paramètre derreur). Nous avons aussi améliorer le précédent algorithme d Alon, Krivelevich, Newman, et Szegedy , ( 2000) pour lapproximation de lappartenance à un langage régulier modulo la distance de Hamming. Notre amélioration consiste à rendre cet algorithme polynomial en la taille de lautomate non-déterministe

Ensuite nous avons considérer l’appartenance approché d’un arbre à une automate d’arbre sous la distance standard d’édition. Pour ce problème nous proposons un algorithme dont la complexité en temps est exponentielle en la hauteur de l’arbre. Enfin nous avons considérer la validation approchée de DTD par rapport à la «  strong edit distance » ; et nous obtenons dans ce cas un algorithme polynomiale en la hauteur de l’arbre. Nous complétons nos résultats en prouvant une borne inférieure linéaire en la taille de l’arbre, pour la complexité de tout algorithme décidant l’appartenance approché d’un arbre à une DTD, sous la strong edit distance.

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster