Présentation

• Un mot est palindrome lorsqu'il se lit indifféremment de gauche à droite ou de droite à gauche. Le caractère palindrome est une forme de régularité connue depuis longtemps; nous nous proposons d'en explorer quelques aspects.
• Ce sujet propose l'étude de plusieurs algorithmes concernant les palindromes, qui ont en commun d'avoir un coût linéaire en la taille du mot auquel ils sont appliqués:
  • l'algorithme de Manacher détermine tous les préfixes palindromes d'un mot u.
  • l'algorithme de Galil et Seiferas décide si un mot u donné se décompose en produit de palindromes non triviaux (i.e. de longueur au moins égale à 2); si c'est le cas, il donne une telle décomposition
• En complément:
  • une question d'oral de Cachan, mêlant automates finis et palindromes (et beaucoup d'erreurs);
  • une caractérisation des langages équilibrés, due à Coven et Hedlund, faisant intervenir des palindromes.