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 à partir 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. / Storage, management and sharing of data are central issues in computer science. Structuring data in trees has become a standard (XML, JSON). To ensure preservation and quick exchange of data, one must identify new mechanisms to automatize such transformations. We focus on the study of tree to words transformations represented by finite state machines. We define sequential tree to words transducers, that use each node of the input tree exactly once to produce an output. Using reduction to the equivalence problem of morphisms applied to context-free grammars (Plandowski, 95), we prove that equivalence of sequential transducers is decidable in polynomial time. We introduce the concept of earliest transducer, sequential transducers normal form, which aim to produce output "as soon as possible" during the transduction. Using normalization and minimization algorithms, we prove the existence of a canonical transducer, unique, minimal and earliest, for each transduction of our class. Deciding the existence of a transducer representing a sample, i.e. pairs of input and output of a transformation, is proved NP-hard. Thus, we propose a learning algorithm that generate a canonical transducer from a sample, or fail, while remaining polynomial. This algorithm is based on grammatical inference techniques and the adaptation of a Myhill-Nerode theorem.

L’échange d’informations entre périphériques variés et sur internet soulève de nombreux problèmes par le volume et l’hétéroclisme des données échangées. La plupart de ces échanges utilisent le format XML. Afin de les faciliter, des traitements intelligents, comme la classification et la transformation automatiques, ont été développés. Le but de cette thèse est double : proposer un framework d'apprentissage pour la classification de documents XML et étudier l'apprentissage de transformations de documents XML. Le choix d’utiliser la Programmation Logique Inductive a été fait. Même si les méthodes d'apprentissage ont alors un surcoût algorithmique non négligeable (certaines opérations deviennent NP-dures), la représentation relationnelle semble adaptée aux documents XML de par son expressivité. Notre framework pour la classification fait suite à l'étude de familles de clauses pour la représentation de structures arborescentes. Il repose sur une réécriture des opérations de base de la PLI que sont la theta-subsomption et le moindre généralisé [Plotkin1971]. Nos algorithmes sont polynomiaux en temps dans la taille de leur entrée là où ceux standards sont exponentiels. Ils permettent une identification à la limite [Gold1967] de nos familles de clauses. Notre seconde contribution débute par la modélisation d’une famille de clauses dans la lignée des programmes fonctionnels [Paulson91]. Ces clauses sont une adaptation à la PLI des scripts d'édition et prennent en compte un contexte. Elles permettent la représentation de transformations de documents XML. Leurs apprentissages sont possibles grâce à deux algorithmes de type A*, approche courante en PLI (HOC-Learner [Santos2009]). / The recent proliferation of XML documents in databases and web applications rises some issues due to the numerous data exchanged and their diversity. To ease their uses, some smart means have been developed such as automatic classification and transformation. This thesis has two goals:• To propose a framework for the XML documents classification task.• To study the XML documents transformation learning.We have chosen to use Inductive Logic Programming. The expressiveness of logic programs grants flexibility in specifying the learning task and understandability to the induced theories. This flexibility implies a high computational cost, constraining the applicability of ILP systems. However, XML documents being trees, a good concession can be found.For our first contribution, we define clauses languages that allow encoding xml trees. The definition of our classification framework follows their studies. It stands on a rewriting of the standard ILP operations such as theta-subsumption and least general generalization [Plotkin1971]. Our algorithms are polynomials in time in the input size whereas the standard ones are exponentials. They grant an identification in the limit [Gold1967] of our languages.Our second contribution is the building of methods to learn XML documents transformations. It begins by the definition of a clauses class in the way of functional programs [Paulson91]. They are an ILP adaptation of edit scripts and allow a context. Their learning is possible thanks to two A*-like algorithms, a common ILP approach (HOC-Learner [Santos2009]).