Complexité palindromique

Lorsqu'on étudie une suite symbolique donnée, il est particulièrement intéressant de se concentrer sur ses facteurs palindromiques, c'est-à-dire les mots qui ont la propriété de se lire de la même façon de droite à gauche que de gauche à droite. En français, les mots "ressasser" et "radar" sont des palindromes. En géométrie discrète, les palindromes correspondent à des objets possédant des propriétés symétriques telles qu'être invariant sous une rotation d'angle π ou sous différentes réflexions.

Dans [1], Brlek, Hamel, Nivat et Reutenauer ont introduit la notion de défaut palindromique, une statistique sur les mots mesurant leur degré de plénitude (ou richesse) en palindromes. Plus précisément, soit w un mot fini. Alors il est facile de montrer que w contient au plus |w| + 1 palindromes distincts (incluant le palindrome vide ε). Le défaut de w est alors défini par

Un mot est appelé plein si D(w) = 0. Il est bien connu de la communauté que les mots sturmiens et episturmiens sont pleins. De plus, le mot de Thue-Morse n'est pas plein (on dit alors qu'il est lacunaire) et les positions auxquelles on manque les palindromes sont décrites de façon exacte dans [2]. Plus récemment, nous avons démontré que les codages de rotations, une généralisation naturelle des mots sturmiens, sont également pleins [3].

Un opérateur intéressant qui agit sur les palindromes est le clôture palindromique itérée. Soit w un mot fini. On définit la clôture palindromique de w comme le palindrome le plus court ayant w comme préfixe. On la note par w^( + ). Par exemple

puisque baab est le plus long palindrome suffixe de abaab. Une autre propriété remarquable du mot de Fibonacci est qu'il peut être construit en appliquant successivement la clôture palindromique et en ajoutant de façon alternée les lettres a et b:

(a)^( + )  =  a       (ab)^( + )  =  aba       (abaa)^( + )  =  abaaba       (abaabab)^( + )  =  abaababaaba       (abaababaabaa)^( + )  =  abaababaabaababaaba       ⋮

Plusieurs généralisations différentes de la clôture palindromique itérée ont été étudiées. Une d'entre elles se concentre sur les pseudopalindromes ou f-palindromes, une généralisation classique des palindromes. Soit f une involution sur un alphabet quelconque. Alors w est appelé f-palindrome si f(w) = w̃, où ⋅̃ dénote l'image miroir d'un mot (les lettres sont écrites dans l'ordre inverse). Par exemple, le mot ACGT, bien connu des biologistes, est un f-palindrome, où f est défini par A↔T et C↔G. Une abondante littérature est consacrée à la combinatoire des f-palindromes, en particulier en bio-informatique. Le lecteur intéressé par le sujet est référé à [5] pour plus de détails concernant mes travaux sur les f-palindromes et la clôture palindromique itérée.

Pavages

La combinatoire des mots fournit de précieux outils pour étudier les objets discrets tels que les polyominos. En particulier, il permet de caractériser les tuiles qui pavent le plan par translation de façon régulière. Beauquier et Nivat ont démontré dans [6] qu'un polyomino P pave le plan de façon périodique s'il admet au moins un mot de contour w (c'est-à-dire un mot sur l'alphabet {a, a, b, b} codant les déplacements droite, gauche, haut et bas respectivement) tel que

où ^⋅ dénote le chemin discret parcouru en sens inverse et au plus un des mots A, B et C est vide. De tels polyominos sont appelés tuiles. Par exemple, les deux polyominos qui suivent sont des tuiles:

Le polyomino à gauche est appelé tuile carrée, puisque le mots C est vide. D'autre part, le polyomino à droite est appelé tuile hexagonale, puisque chaque mot A, B et C sont non vides.

Au cours des dernières années, j'ai considéré principalement la famille des tuiles carrées, plus précisément celles admettant des pavages carrés multiples. Par exemple, la tuile de Fibonacci suivante est un 2-carré (ou tuile double carrée):

puisqu'elle admet deux pavages carrés distincts (indiqués par les points rouges et bleus). En 2008, il a été conjecturé dans [7] qu'il n'existe aucune tuile 3-carrée. Nous avons démontré dans [8] que cette conjecture est effectivement vérifiée. Finalement, nous avons également étudié en détail l'énumération des tuiles 2-carrées dans [9]. La figure ci-bas illustre les 100 premières tuiles doubles carrées :

Il reste plusieurs problèmes ouverts pour tout étudiant souhaitant s'initier à la géométrie discrète et la combinatoire des mots (voir par exemple [9]).

Références