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

Let be a language composed by all words of a given length $n$. A de Bruijn sequence of span $n$ is a cyclic string such that all words in the language appears exactly once as factors of this sequence. One of the algorithms to construct the lexicographically minimal de Bruijn sequence is due to Fredricksen and Maiorana and it use the Lyndon words in the language. This thesis studies how to generalize the concept of de Bruijn sequence for a language composed by a subset of words of length $n$, particularly the languages of all words of length $n$ without factors in a list of forbidden factors. Firstly, we study the case of words without the factor 11. We give a new proof of the algorithm of Fredricksen and Maiorana which allows us to extend this result to the case of words without the factor $1^i$ for any $i$. We characterize for which languages of words of length $n$ exists a de Bruijn sequence, and we also study some symbolic dynamical properties of these languages, particularly of the languages defined by forbidden factors. For these kinds of languages, we present an algorithm to produce a de Bruijn sequence, using the Lyndon words of the language. These results use the notion of de Bruijn graph and reduce the problem to construct an Eulerian cycle in this graph. We study the problem of construct the lexicographically minimal de Bruijn sequence in a language with forbidden factors using the de Bruijn graph. We study two algorithms, a simple and efficient greedy algorithm which works with some sets of languages, and a more complex algorithm which solves this problem for any Eulerian labelled graph.Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien