Transformations de mots, d'arbres et de statistiques
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
We live in a world of exchange where errors are everywhere. Being able to verify approximately if a property is close or far to be satisfied is essential therefore. This leads to develop techniques to exchange huge and imperfect data. The subject of this thesis is the study of approximated processes that are taking errors into account, and of the comparison between exact and approximated processes as far as complexity is concerned. From a theoretical point of view, the heart of data exchange is the transformation of words and trees. This thesis shows that it is possible to decide the approximate equivalence of Finite State Machines for a particular distance, and extends the decision to a type of linear tree transducers inspired by XSLT. To that end, a method to approximate instances (word or tree), languages and transducers of these instances is introduced. Its main interest lies in the possibility of linking the edit distance with moves between two transducers with the geometrical distance (L1 norm) between their embeddings. This geometrical embedding also enables to decide the approximate consistency of an instance in constant time, i. E. Independently from the input size. Finally, the implementation of data exchange is illustrated: weighted transductions are used to simulate computations of distances between languages, and tree transductions are used to build maps of log files and to visualize results of an OLAP query.
Abstract FR:
Nous vivons dans un monde d'échange où les erreurs sont partout. Il est donc essentiel de pouvoir vérifier approximativement si on est « proche » ou « loin » de satisfaire une propriété particulière. La motivation est alors de développer des techniques pour s'échanger des données gigantesques mais aussi imparfaites. Le sujet de cette thèse est l'étude de traitements approchés, qui prennent en compte les erreurs, et la comparaison, du point de vue de la complexité, entre traitements exacts et approchés. D'un point de vue théorique, le cœur de l'échange de donnée est la transformation de mots et d'arbres. Cette thèse montre que l'on sait décider l'équivalence approchée des machines à états finis pour une distance particulière, puis étend la décision à un type de transducteurs linéaires d’arbres inspirés par XSLT. Pour ce faire, une méthode d'approximation des instances (mots ou arbres), des automates, et des transducteurs linéaires de ces instances est proposée. Son intérêt majeur est la possibilité de pouvoir relier la distance d'édition avec déplacements entre deux transducteurs à la distance géométrique (la norme L_1) entre leurs représentations. Cette approximation géométrique permet aussi de décider de la consistance approchée d'une instance en temps constant, ie indépendamment de la taille de l'entrée. L’implémentation d’un nouvel outil de visualisation et d’échange de structures est finalement illustrée : les transducteurs pondérés simulent le calcul de certaines distances, et des transductions sont proposées pour la création de cartes d’audience et la visualisation de résultats de requêtes OLAP.