Dans ce travail, nous nous intéressons à divers problèmes de la combinatoire des mots, portant principalement sur deux familles: les mots équilibrés et les mots lisses infinis. Il est facile de vérifier que l'intersection entre ces deux familles de mots est vide; c'est pourquoi nous les traiterons de façon indépendante. Dans la première partie, nous étudions les mots équilibrés et des familles de mots dérivées de ces derniers. Les mots infinis sturmiens, aussi appelés des suites sturmiennes, sont étudiés depuis plus de cent ans et sont caractérisés de plusieurs façons : pour un alphabet à deux lettres, ce sont exactement les suites équilibrées non ultimement périodiques et les suites de complexité minimale, c'est-à-dire les suites ayant seulement (n + 1) facteurs de longueur n. Une autre propriété caractéristique des suites sturmiennes est qu'elles décrivent une droite discrète. Les suites épisturmiennes ont récemment été introduites comme étant l'une des généralisations sur plus de 2 lettres des suites sturmiennes : un mot de Christoffel est la version finie d'une suite sturmienne. Dans un premier temps, nous introduisons donc une généralisation des mots de Christoffel sur un alphabet à plus de 2 lettres. Pour ce faire, nous utilisons la propriété qu'un mot de Christoffel est l'image d'une lettre par morphisme sturmien. Nous appelons les mots ainsi obtenus des mols épichristoffels. Il est intéressant de remarquer que ces mots ne sont généralement pas équilibrés, tout comme les suites épisturmiennes. Nous montrons comment obtenir des mots épichristoffels, comment les reconnaître et nous montrons que certaines propriétés des mots de Christoffel se généralisent bien aux mots épichristoffels. Dans un deuxième temps, nous nous intéressons aux mots équilibrés, en lien avec la conjecture de Fraenkel. Cette conjecture énonce que pour un alphabet à k lettres, avec k ≥ 3, il n'existe qu'un unique mot infini équilibré, à permutation des lettres et à décalage près, ayant des fréquences de lettres toutes différentes. Par exemple, pour l'alphabet {1, 2, 3}, ce mot est (1213121)w. Nous montrons que la conjecture est vraie si elle est restreinte à la famille des suites épisturmiennes et du coup, nous caractérisons les suites épisturmiennes équilibrées. Nous approchons ensuite la conjecture de Fraenkel en travaillant sur la superposition de mots de Christoffel. Nous traduisons les travaux de R. Simpson et de R. Morikawa sur les suites de Beatty en terme de mots de Christoffel et nous fournissons les détails passés sous silence dans leurs preuves. Nous obtenons ainsi une condition nécessaire et suffisante pour que deux mots de Christoffel se superposent. Comme un mot équilibré à k lettres peut être vu comme la superposition de k mots équilibrés sur 2 lettres, cette condition nous permet de nous approcher de la conjecture de Fraenkel, sans toutefois la prouver. Nous prouvons toutefois une formule donnant le nombre de superpositions pour deux mots de Christoffel superposables et nous montrons de nouvelles propriétés concernant les mots de Christoffel. La deuxième partie de ce travail porte sur l'étude des mots lisses infinis, principalement les mots lisses extrémaux, c'est-à-dire le plus petit et le plus grand selon l'ordre lexicographique. Nous caractérisons ces mots sur des alphabets à deux lettres de même parité. Pour ce faire, nous décrivons d'abord des algorithmes qui permettent de les construire en temps linéaire selon le nombre d'opérations. Nous montrons ensuite des propriétés de fermeture et dee récurrence pour les mots lisses en général sur un alphabet de même parité, nous fournissons une formule explicite pour la fréquence des lettres dans les mots extrémaux et nous décrivons la factorisation de Lyndon pour une sous-classe des mots extrémaux. Ces résultats sont forts intéressants puisque les propriétés démontrées ne sont pour la plupart que des conjectures pour les mots lisses sur l'alphabet {1, 2}. Par ailleurs, nous montrons que les mots lisses maximaux sur des alphabets contenant deux lettres paires et certains mots de Kolakoski généralisés coïncident. Du coup, nous prouvons plusieurs propriétés concernant la factorisation de Lyndon, les fréquences, la fermeture de l'ensemble des facteurs sous l'image miroir et la récurrence pour les mots de Kolakoski généralisés. Finalement, nous étudions les mots lisses infinis en lien avec les surfaces discrètes. Nous montrons que les seuls pavages lisses du quart de plan décrivant un morceau de surface discrète sont engendrés par des mots de Kolakoski généralisés. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, Mot de Christoffel, Suite sturmienne, Mot épichristoffel, Suite épisturmienne, Conjecture de Fraenkel, Suite équilibrée, Mot lisse, Mot de Kolakoski, Mot de Lyndon, Mot extrémal, Surface discrète.

Lorsqu'on s'intéresse à l'étude de la structure combinatoire d'un mot infini w, une stratégie classique consiste à calculer sa fonction de complexité, c'est-à-dire à décrire le nombre de mots de longueur n qui apparaissent dans w, pour chaque entier n ≥ 0. Récemment, des chercheurs se sont intéressés à un raffinement de cette notion en introduisant la fonction de complexité palindromique: pour chaque entier n ≥ 0, nous calculons le nombre de palindromes de longueur n apparaissant dans w. Rappelons qu'un palindrome est un mot qui se lit de la même façon de gauche à droite que de droite à gauche (par exemple, "radar" et "ressasser" sont des palindromes de la langue française). La connaissance des palindromes apparaissant dans un mot permet de déduire de nombreuses informations précieuses sur sa structure. Par exemple, un mot admettant une infinité de palindromes préfixes est nécessairement récurrent (tout facteur apparaît une infinité de fois) et son langage est fermé sous l'opération miroir. D'autre part, nous étudions également les occurrences de facteurs antipalindromiques (une généralisation de la notion de palindrome), qui semblent naturellement en interaction avec les palindromes usuels. En particulier, nous décrivons les complexités palindromique et antipalindromique de quelques familles importantes de mots: les mots périodiques, les mots sturmiens, le mot de Thue-Morse et les suites de Rote. Dans un deuxième temps, nous étudions le défaut palindromique des mots finis et infinis. Il s'agit d'une mesure de "richesse" ou de "pauvreté" en palindromes des mots. Nous montrons en particulier que certains mots associés aux suites de Rote, à l'instar des mots sturmiens (Droubay, Justin et Pirillo, 2001), sont aussi pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale, et nous établissons aussi des conditions sous lesquelles les mots périodiques sont pleins. Une section supplémentaire est consacrée à l'étude des lacunes du mot de Thue-Morse, qui admet une infinité de palindromes, mais dont le défaut est infini (c'est-à-dire qu'il possède une infinité de lacunes palindromiques). En dernier lieu, nous mentionnons quelques problèmes ouverts dans ce passionnant champ de recherche. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire, Mots, Palindromes, Antipalindromes, Complexité, Défaut.

L'objet de cette thèse est d'étudier les liens entre la géométrie discrète et la combinatoire des mots. Le fait que les figures discrètes soient codées par des mots sur l'alphabet à quatre lettres Σ = {0.1.0,1}, codage introduit par Freeman en 1961, justifie l'utilisation de la combinatoire des mots dans leur étude. Les droites discrètes sont des objets bien connus des combinatoriciens, car étant identifiés par les mots Sturmiens. dont on trouve déjà une description assez complète dans les travaux de Christoffel à la fin du XIXe siècle à la suite de travaux précurseurs de Bernouilli et Markov. Alors que l'on comprend bien la structure des droites discrètes, on connait beaucoup moins bien les courbes en général. Cet ouvrage porte sur l'étude de propriétés géométriques de courbes fermées, codées sur l'alphabet Σ . On s'intéresse tout d'abord à la représentation des chemins dans le plan discret Z² et de ceux qui codent les polyominos. Dans un premier temps, l'emploi d'une structure arborescente quaternaire permet d'élaborer un algorithme optimal afin de tester si un mot quelconque sur Σ code un polyomino ou non. Ce résultat est fondamental d'abord parce qu'il est nouveau, élégant et qu'il se généralise en dimension supérieure. En outre, la linéarité de ce test rend les algorithmes subséquents vraiment efficaces. À la suite de résultats précurseurs de Lyndon. Spitzer et Viennot sur la factorisation des mots, il existe une interprétation combinatoire de la convexité discrète. En géométrie algorithmique, des algorithmes linéaires furent établis par McCallum et Avis en 1979, puis par Melkman en 1987, pour calculer l'enveloppe convexe d'un polygone. Debled-Rennesson et al. ont obtenu en 2003, un algorithme linéaire pour décider de la convexité discrète d'un polyomino par des méthodes arithmétiques. Nous avons obtenu grâce aux propriétés spécifiques des mots de Lyndon et de Christoffel un algorithme linéaire pour tester si un polyomino est digitalement convexe. L'algorithme obtenu est extrêmement simple et s'avère dix fois plus rapide que celui de Debled-Rennesson et al. Finalement, le calcul de la plus longue extension commune à deux mots en temps constant -obtenu par Gusfield à l'aide des arbres suffixes -et le théorème de Fine et Wilf permettent d'élaborer de nouveaux algorithmes qui, grâce à la caractérisation de Beauquier-Nivat, testent si un polyomino pave le plan par translation. En particulier, on obtient un algorithme optimal en O(n) pour détecter les pseudo-carrés. Dans le cas des pseudo-hexagones ayant des facteurs carrés pas trop longs on obtient également un algorithme linéaire optimal, tandis que pour les pseudo-hexagones quelconques nous avons obtenu un algorithme en O(n(log n)³) que nous croyons ne pas être optimal. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, Géométrie discrète, Droites digitales, Pavages du plan, Algorithmique.

Ce mémoire fait partie du domaine de la combinatoire des mots et plus particulièrement de l'étude de la complexité palindromique (le nombre de facteurs palindromes) des mots infinis. La conjecture de Hof, Knill et Simon, énoncée pour la première fois en 1995, donne une caractérisation des points fixes dont la complexité palindromique est infinie. Récemment, elle a été résolue pour les points fixes sur un alphabet binaire (Tan, 2007). Dans ce mémoire, nous la démontrons pour les points fixes de morphismes uniformes sur un alphabet binaire (ce n'est pas plus général que le résultat de Tan). De plus, notre approche permet d'obtenir une démonstration d'un résultat similaire pour les points fixes contenant une infinité d'antipalindromes. Afin d'atteindre notre objectif, nous établissons un ensemble de résultats combinatoires sur les mots. En effet, nous faisons une étude des ƒ-palindromes et de certaines équations qui en contiennent. Ensuite, nous introduisons les morphismes de classe P, P¹ et ƒ-P et nous démontrons notamment que l'ensemble des morphismes de classe P¹ est un monoïde. Nous rassemblons également les résultats d'un travail précédent sur les morphismes conjugués. Finalement, nous étudions les chevauchements de mots et nous construisons un graphe de chevauchements, assise de notre démonstration de la conjecture. Toutes ces recherches ont contribué au développement d'un outil informatique voué à l'étude de questions soulevées en combinatoire des mots. Ce dernier est constitué d'un ensemble de classes et de fonctions écrites en langage Python annexées à ce mémoire. Elles seront bientôt incluses dans un paquetage sur la combinatoire des mots associé au logiciel libre Sage. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, ƒ-palindrome, Complexité palindromique, Conjecture de Hof, Knill et Simon, Point fixe de morphisme, Chevauchement, Automates.

Ce travail se consacre principalement à l'étude d'équations sur les mots ainsi qu'à leur application en géométrie discrète. Comme le rappelle Freeman en 1961, tout chemin dans le plan discret, que l'on peut voir comme une liste de déplacements parmi {→, ↑, ←, ↓}, peut être représenté par un mot pour lequel chaque lettre représente l'un des quatre déplacements élémentaires possibles. Ce point de vue offre entre autre la possibilité de décrire plusieurs objets de la géométrie discrète, tels les polyominos par exemple, en termes d'équations sur les mots. Dans cet ouvrage, nous utilisons cette correspondance pour étudier les pavages du plan par translation dont il est bien connu qu'il en existe deux réguliers : les pavages hexagonaux et les pavages carrés. Ce résultat important fut établi par Beauquier et Nivat et a permis d'étudier les pavages du point de vue algorithmique. Une classe importante est apparue naturellement, à savoir celle des polyominos qui pavent le plan par translation de plusieurs manières. Alors qu'il existe des polyominos pavants à la manière d'un hexagone d'un nombre arbitraire de façons, il en est tout autrement pour le cas des carrés: nous présentons et résolvons la conjecture selon laquelle un polyomino pave comme un carré d'au plus deux façons, puis nous étudions plus en détail la structure de ces derniers. Puisque les contours sont codés sur un alphabet fini, la combinatoire des mots s'impose comme l'outil principal pour traiter ces problèmes de nature géométrique. ______________________________________________________________________________

L'objet de cette thèse est l'étude des liens existant entre la combinatoire de l'écriture d'un nombre réel en base entière ou sous la forme d'une fraction continue et le caractère algébrique ou transcendant de ce nombre réel (une conjecture de Borel prévoit que tout irrationnel algébrique est un nombre absolument normal: ses écritures en bases entières ont la même propriété que celle d'une suite aléatoire de chiffres).

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous donnons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence dé palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Palindrome, pseudopalindrome, clôture pseudopalindromique itérée, codages de rotations, symétries, chemins discrets, pavages.

Cette thèse, constituée d'une série d'articles, considère des questions issues de la géométrie discrète en les traitant du point de vue de la combinatoire des mots qui s'avère un outil puissant et approprié pour les résoudre. Nous utilisons les mots soit pour représenter un chemin dans Z2 ou Z3, soit pour coder la suite des virages d'un chemin ou le contour d'une figure discrète fermée. Parmi les thèmes abordés, on compte les pavages du plan par polyominos, la notion de complexité en facteurs palindromes et la génération de droites discrètes 3D. La première partie concerne les pavages du plan où nous étudions le nombre de pavages réguliers du plan par une tuile carrée, c'est-à-dire une tuile ayant quatre tuiles adjacentes identiques. Il s'avère que certaines tuiles carrées pavent le plan de deux façons distinctes et elles sont appelées doubles carrées. Nous démontrons d'abord qu'il y a au plus deux tels pavages réguliers par une tuile carrée. Ensuite, nous considérons deux familles particulières de tuiles doubles carrées : les tuiles de Christoffel et les tuiles de Fibonacci. Ces deux familles décrivent les plus petits exemples de tuiles doubles carrées et peuvent être définies à partir des mots de Christoffel et du mot de Fibonacci par des règles de substitution et de concaténation. Les tuiles de Fibonacci définissent aussi une fractale, obtenue par un chemin auto-évitant, dont nous avons calculé plusieurs statistiques, comme le rapport de l'aire de la fractale sur l'aire de son enveloppe convexe. Dans l'article suivant, nous démontrons que tout double carré indécomposable est invariant sous une rotation de 180 degrés. Cette propriété géométrique est équivalente au fait que le mot de contour de la tuile se factorise en un produit de palindromes. Notre preuve repose sur une méthode de génération exhaustive des tuiles doubles carrées. La deuxième partie concerne la complexité palindromique - le nombre de facteurs palindromes distincts -, un sujet propre à la combinatoire des mots. Nous y considérons quatre classes de complexité palindromique qui découlent naturellement de la notion de défaut. Nous caractérisons notamment les mots de complexité palindromique minimale sur un alphabet à deux lettres et nous démontrons que les mots infinis obtenus par codage de rotations sur deux intervalles atteignent la complexité palindromique maximale. Dans une troisième partie, nous proposons une méthode basée sur des algorithmes de fractions continues multidimensionnelles pour la génération de droite discrètes 3D 6-connexes. Les expérimentations illustrent que la complexité en facteurs des mots ainsi générés serait linéaire. Cela se compare avantageusement aux autres définitions de droites discrètes 3D 6-connexes dont la complexité en facteurs est quadratique. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire des mots, géométrie discrète, pavage, polyomino, complexité palindromique, droite discrète, algorithme de fractions continues multidimensionnelles.

Les polyominos sont souvent représentés par des mots de quatre lettres ou des mots de changements de direction décrivant leur contour. La combinatoire des mots classique y joue donc un rôle descriptif important, particulièrement dans le choix d'un représentant canonique. Les mots de Lyndon fournissent, de façon naturelle, un tel représentant. Une approche systématique pour le calcul de propriétés des polyominos, basée sur une version originale d'une discrétisation du théorème de Green classique en calcul bivarié, est élaborée. Ceci nous a naturellement amené à analyser les propriétés géométriques d'ensembles du réseau discret de rondeur maximale. Pour une taille donnée, ces ensembles minimisent le moment d'inertie par rapport à un axe passant par leur centre de gravité. Nous introduisons la notion de quasi-disque et montrons entre autres que ces ensembles minimaux sont des poIyominos fortement-convexes. Nous développons également un algorithme permettant de les engendrer systématiquement. Un autre aspect concerne des propriétés sur les contours d'ensembles discrets donnant lieu à une nouvelle démonstration d'un résultat de Daurat et Nivat sur les points dits saillants et rentrants d'un polyomino. Nous présentons également une généralisation de ce résultat aux réseaux hexagonaux et montrons que le résultat est faux pour les autres réseaux semi-réguliers. Nous poursuivons par l'introduction d'opérations de mélange spéciaux sur des mots décrivant des chemins discrets selon la suite de leurs changements de direction. Ces opérations de mélange permettent d'engendrer des courbes fractales du type courbe de dragon et d'analyser certains de leurs invariants. Finalement, une généralisation aux dimensions supérieures des algorithmes précédents basés sur le théorème de Green discret, est présentée. Plus particulièrement, nous développons une version discrète du théorème de Stokes basée sur des familles de poids sur les hypercubes de dimension k dans l'espace discret Zn, k ≤ n. Quelques applications sont également décrites. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Géométrie discrète, Combinatoire des mots, Ensembles discrets, Polyominos, Quasi-disques, Chemins polygonaux, Courbes de dragon, Théorème de Green discret, Théorème de Stokes discret, Algorithmes.

Dans cette thèse nous traitons des mots interdits minimaux, qui sont les plus petits mots qui n'apparaissent pas comme facteur d'un mot donné, et de leurs applications. Dans la première partie de la thèse nous exposons les propriétés des mots interdits minimaux, et nous considérons quelques cas particuliers, comme celui d'un mot fini, d'un ensemble fini de mots finis, et d'un langage factoriel régulier. Nous présentons aussi les procédures pour le calcul des objets considérés. Ensuite, nous généralisons les mots interdits minimaux au cas de l'existence d'une période, qui détermine les positions des occurrences des facteurs modulo un entier fixé. Ceux-ci sont appelés mots interdits minimaux périodiques. Nous étudions leurs propriétés principales et avec des algorithmes de test de ces propriétés. Dans la deuxième partie de la thèse nous montrons deux applications des mots interdits minimaux. La première est reliée aux systèmes contraints. Nous donnons une construction en temps polynomial de l'ensemble des séquences qui satisfont la contrainte définie par une liste finie de blocs interdits, avec un ensemble spécifié de positions de bit sans contrainte. Nous donnons aussi une construction en temps linéaire d'une présentation à états finis d'un système contraint défini par une liste périodique de blocs interdits. La deuxième application est relative à un problème de biologie : la reconstruction d'une séquence génomique à partir d'un ensemble de ses fragments. Nous donnons une formalisation théorique de ce problème qui le rend résoluble en temps linéaire en utilisant les mots interdits minimaux. Nous prouvons aussi que notre algorithme résout un cas particulier du "problème de la plus petite sur-séquence" (Shortest Superstring Problem).