Thèse
Normalisation et Apprentissage de Transductions d’Arbres en Mots
Résumé
Le stockage et la gestion de données sont des questions centrales en informatique. La structuration sous forme d’arbres est devenue la norme (XML, JSON). Pour en assurer la pérennité et l’échange efficace des données, il est nécessaire d’identifier de nouveaux mécanismes de transformations automatisables.
Nous nous concentrons sur l’étude de transformations d’arbres en mots représentées par des machines à états finies. Nous définissons les transducteurs séquentiels d’arbres en mots ne pouvant utiliser qu’une et unique fois chaque nœud de l’arbre d’entrée pour décider de la production.
En réduisant le problème d’équivalence des transducteurs séquentiels à celui des morphismes appliqués à des grammaires algébriques (Plandowski, 95), nous prouvons qu’il est décidable en temps polynomial.
Cette thèse introduit la notion de transducteur travailleur, forme normalisée de transducteurs séquentiels, cherchant à produire la sortie le «plus tôt possible» dans la transduction. A l’aide d’un algorithme de normalisation et de minimisation, nous prouvons qu’il existe un représentant canonique, unique transducteur travailleur minimal, pour chaque transduction de notre classe.
La décision de l’existence d’un transducteur séquentiel représentant un échantillon, i.e. paires d’entrées et sorties d’une transformation, est prouvée NP-difficile. Nous proposons un algorithme d’apprentissage produisant à par- tir d’un échantillon le transducteur canonique le représentant, ou échouant, le tout en restant polynomial. Cet algorithme se base sur des techniques d’inférence grammaticales et sur l’adaptation du théorème de Myhill-Nerode.
[pdf] [slides]
Publications
Conférences internationales
Learning Sequential Tree-to-Word Transducers
Slawek Staworko, Grégoire Laurence, Joachim Niehren et Aurélien Lemay et Marc Tommasi.
In Proceedings of the 8th International Conference on Language and Automata Theory and Applications, 2014 [pdf] [slides]
Normalization of Sequential Top-Down Tree-to-Word Transducers
Grégoire Laurence, Aurélien Lemay, Joachim Niehren, Slawek Staworko et Marc Tommasi.
In Proceedings of the 5th International Language and Automata Theory and Applications. 2009 [pdf] [slides]
Equivalence of Deterministic Nested Word to Word Transducers
Slawek Staworko, Grégoire Laurence, Joachim Niehren et Aurélien Lemay.
In Proceedings of the 17th International Symposium on Fundamentals of Computation Theory. 2009 [pdf] [slides]
Mémoire
Apprentissage de fonctions reconnaissables d’arbres.
Mémoire de DEA (Master thesis). Laboratoire d’Informatique Fondamentale de Lille [pdf]
