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.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.1136 |
| Date | January 2008 |
| Creators | Paquin, Geneviève |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | French |
| Type | Thèse acceptée, PeerReviewed |
| Format | application/pdf |
| Relation | http://www.archipel.uqam.ca/1136/ |
Page generated in 0.002 seconds