Minimisation d'automates non-déterministes, recherche d'expressions dans un texte et comparaison de génomes / Fabien Coulon ; sous la dir. de Jean-Marc Champarnaud

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 2004

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Théorie des automates mathématiques

Exploration de données

Langages algébriques

Logiciels -- Vérification

Génome -- Méthode comparative

Théorie des graphes

Algorithmes

Champarnaud, Jean-Marc (19..-.... ; auteur en informatique) (Directeur de thèse / thesis advisor)

Université de Rouen Normandie (1966-....) (Organisme de soutenance / degree-grantor)

Relation : Minimisation d'automates non-déterministes, recherche d'expressions dans un texte et comparaison de génomes / Fabien Coulon ; sous la direction de Jean-Marc Champarnaud / Grenoble : Atelier national de reproduction des thèses , 2004

Résumé / Abstract : Cette thèse débute par la minimisation des automates non-déterministes. Je fournis la preuve d'une technique présentée sans démonstration par Sengoku ainsi que différentes heuristiques, basées sur le calcul de simulations d'états, combinant langages gauches et droits. Ce travail débouche sur une technique de réduction des automates de Büchi. Parallèlement, je m'intéresse à la maîtrise de la complexité en espace de la déterminisation en optimisant la déterminisation partielle. Les thèmes suivants sont plus applicatifs. Le premier concerne la recherche approchée d'expressions secondaires dans le génome au moyen de grammaires algébriques. Je présente une adaptation de l'algorithme de Valiant, puis un algorithme de type CYK pour la recherche approchée d'une hélice simple. Je termine par la recherche d'équipes de gènes communes entre différents génomes, dont un problème sous-jacent est la recherche de composantes connexes communes à plusieurs graphes. J'y présente notre nouvel algorithme traitant le cas de graphes d'intervalles.

Résumé / Abstract : The initial topic of this thesis is automata minimization. I prove a technique for full minimization that was given unproved by Sengoku, together with heuristics based on state simulations, that combine left and right languages. This work provides a reduction technique for B\"uchi automata. On the other hand, I focus on managing the space complexity of determinisation by an optimized partial determinization.The following is more involved in practical applications. First, I focus on secondary expression search in genome, based on context-free grammars. I give an adaptation of Valiant's algorithm, and a CYK algorithm for single hairpin approximate search. Finally, I investigate gene-team search between several genomes. An underlying problem is the common connected set search between several graphs. I describe our new algorithm that is specific to interval graphs.