Note ABES Approximate membership for words and trees Appartenance approchée à un langage de mots ou d’arbres Dtd Langages réguliers Vérification approchée (Property testing) 005.741 XML (langage de balisage) Bases de données Arbres (théorie des graphes) -- Informatique Automates L’objectif de cette thèse est d’obtenir 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 s’inspire du property testing, pour décider approximativement si un arbre d’arité non bornée est valide par rapport à une DTD ; ou plus généralement si un tel arbre est reconnu par un automate d’arbre.Nous avons d’abord étudié le cas simple des mots, c’est-à-dire l’appartenance approchée d’un mot à un langage régulier défini par un automate non-déterministe. Sous la distance d’édition entres les mots, nous proposons un algorithme (ou tester) résolvant l’appartenance approchée en un temps polynomial : en la taille de l’automate aussi bien qu’en la précision (où le paramètre d’erreur). Nous avons aussi amélioré le précédent algorithme d’Alon, Krivelevich, Newman, et Szegedy, (2000) pour l’approximation de l’appartenance à un langage régulier modulo la distance de Hamming. Notre amélioration consiste à rendre cet algorithme polynomial en la taille de l’automate non-déterministe. Ensuite nous avons considéré l’appartenance approchée d’un arbre à un automate d’arbre sous la distance d’édition standard. Notre algorithme résout ce problème avec une complexité en temps exponentielle en la hauteur de l’arbre. Enfin nous avons considéré la validation approchée de DTD par rapport à la « strong edit distance » ; et nous obtenons dans ce cas un algorithme polynomial 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ée d’un arbre à une DTD, sous la strong edit distance. Inspired by property testing, our objective is to obtain sublinear algorithms for deciding properties of XML databases approximatively. More precisely, we investigate the properties of whether an unranked tree is valid for a DTD, or more generally, whether it is recognized by a tree automaton. We start our studies by the simpler case of words and we considered the approximate membership problem for word non-deterministic automata. For this problem, we provide an efficient tester that runs in polynomial time in the size of the input automata and the error precision. We also improve the previous [Alon, Krivelevich, Newman, and Szegedy, 2000b] approximate membership tester for regular languages modulo the Hamming distance, so that it runs in polynomial time in the size of the input automata. Secondly, we study approximate membership testing for tree automata modulo the standard edit distance, and obtain a tester with run time exponential in the input tree depth. Next we consider approximate DTD validity modulo the strong edit distance. We then provide a tester that depends polynomially on the height of the tree. Finally, modulo the strong edit distance, we prove a linear lower bound on the depth of the input tree. Electronic Thesis or Dissertation Text en PDF 1616027 application/pdf https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2014/50376-2014-Ndione.pdf https://theses.fr/2014LIL10020/abes Ndione Antoine Mbaye Ndione 1982-06-30 FR 181220296 https://theses.fr/2014LIL10020 2014LIL10020 https://doi.org/10.70675/b1858e66zc506z4b3az8d31z7f5846ac95f5 2014-04-16 Informatique Lille 1 026404184 Doctorat Docteur es non oui Niehren Joachim MADS_DIRECTEUR_DE_THESE_1 140813055 Lemay Aurélien MADS_DIRECTEUR_DE_THESE_2 069891281 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Laboratoire d'informatique fondamentale de Lille (2002-2014) MADS_PARTENAIRE_DE_RECHERCHE_1 077703553 ddc:000 Niehren Joachim Lemay Aurélien École doctorale Sciences pour l'Ingénieur (Lille) Laboratoire d'informatique fondamentale de Lille (LIFL) PDF 1616027