Idrissa Kaboré
Summary: La combinatoire des mots est une branche des mathématiques discrètes dédiée à l’étude des mots finis ou infinis. Elle entretient des liens étroits avec la dynamique symbolique, l’algèbre, la théorie des nombres, les groupes libres, la géométrie discrète, la combinatoire, l’algorithmique, la théorie des automates et les langages formels qui, tous, contribuent à son développement.
L’ensemble des mots finis sur un alphabet donné est muni d’une structure de monoïde libre et celui des mots infinis est muni d’une topologie métrique. L’objet de ce cours nous présenterons d’abord les notions et propriétés fondamentales sur les mots finis et infinis avec une attention particulière sur le théorème de Fine & Wilf. Ensuite, exposerons différentes méthodes de construction de mots infinis à partir de divers modèles (arithmétique, géométrique, algébrique, dynamique). L’étude des mots infinis repose souvent sur leur classification. L’une des notions combinatoires qui intervient dans cette classification est la complexité. Ici nous présenterons un développement approfondi sur la complexité. Nous terminerons par les mots sturmiens, la classe des mots infinis binaires non ultimement périodiques de complexité minimale.