Complexité palindromique des mots et des arbres

Ce mémoire concerne l'étude des palindromes, soit les mots qui se lisent de la même façon de gauche à droite et de droite à gauche. On s'intéresse au nombre de facteurs palindromes d'un mot, c'est-à-dire de suites contiguës de lettres qui sont des palindromes. On élargit la portée de théorèmes connus aux σ-palindromes, une variante qui permet de considérer des transformations différentes de l'image miroir. On choisit alors σ comme une permutation involutive des lettres de l'alphabet et un σ-palindrome est un point fixe de la composition du miroir et de σ. On expose des algorithmes permettant de calculer le nombre de σ-palindromes et le σ-défaut, une mesure de densité en σ-palindromes originaux. On établit aussi une relation entre le σ-défaut et le nombre de facteurs et de σ-palindromes de chaque longueur, qui s'applique tant aux mots finis qu'aux mots infinis qui sont aussi périodiques, fermés par la composition de σ et de l'opérateur miroir, uniformément récurrents ou points fixes de morphismes primitifs. On considère ensuite des arbres finis dont les arêtes sont étiquetées par des lettres. La trace d'un chemin de l'arbre définit un mot qui appartient au langage de l'arbre. On se penche sur le nombre maximal de palindromes que peut contenir un tel arbre. On remarque alors que ce nombre est plus grand que l'analogue pour les mots. On fournit enfin une borne asymptotique du nombre de palindromes dans les arbres ayant une certaine structure et on survole la résolution du problème général, récemment découverte.\ud ______________________________________________________________________________ \ud MOTS-CLÉS DE L’AUTEUR : Combinatoire des mots, palindromes, complexité palindromique, pseudopalindromes, défaut palindromique, arbres