Graphes et cycles de de Bruijn dans des langages avec des restrictions

Soit un langage composee par tous les mots d’une longueur donnee n. Un cycle de de Bruijn d’ordre n est un mot cyclic tels que tous les mots dans le langage apparait exactement une fois comme facteurs de cet cycle. Un de l’algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est du a Fredricksen et a Maiorana, lequel utilise les mots de Lyndon dans le language. Cette these etudie comment generaliser le concept de cycles de de Bruijn pour un language composee par un sous-ensemble de mots de longueur n, particularment les languages de tous les mots de longueur n sans facteurs dans une liste de facteurs interdits. Premierement, nous etudie le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l’algorithme de Fredricksen et de Maiorana qui nous en permet de prolonger ce resultat au cas des mots sans facteur 1i pour n’importe quelle i. Nous caracterisons pour quelles langues des mots de longueur n existe un cycle de de Bruijn, et nous etudions egalement quelques proprietes de la dynamique symbolique de ces languages, particularment des languages definies par des facteurs interdits. Pour ces genres de languages, nous presentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du language. Ces resultats utilisent la notion du graphe de de Bruijn et reduit le probleme a construire un cycle Eulerian dans ce graphe. Nous etudions le probleme de la construction du cycle minimal dans un language avec des facteurs interdits employant le graphe de de Bruijn. Nous etudions deux algorithmes, un algorithme avide simple et efficace qui fonctionne avec quelques ensembles de langues, et un algorithme plus complexe qui resout ce probleme pour n’importe quel graphe Eulerian