Longueur palindromique d'un mot

En combinatoire, et plus particulièrement en combinatoire des mots, la longueur palindromique d'une chaîne est le nombre minimum de palindromes dont la concaténation est égale à cette chaîne. Les mots de longueur palindromique égale à 1 sont les palindromes.

Exemples[modifier | modifier le code]

Notons $p(w)$ la longueur palindromique d'un mot $w$ . Le mot abaab est le produit des deux palindromes a et baab sans être lui-même un palindrome ; sa longueur palindromique est 2. Le mot abaca est de longueur palindromique $p$ (abaca)=3.

Chaque lettre est un palindrome, et un mot de longueur n est produit de n palindromes de longueur 1 ; la longueur palindromique d'un mot de longueur $n$ est au plus $n$ .

Le mot 010011 peut être exprimé de deux façons différentes comme produite de trois palindromes :(0)(1001)(1) et (010)(0)(11).

Une majoration[modifier | modifier le code]

Notons $p(w)$ la longueur palindromique d'un mot $w$ ^[1]. Alexander (ou Olexandr) Ravsky a donné, en 2003^[2], une formule précises pour le maximum des longueurs palindromiques des mots binaires de longueur donnée. Notons de maximum $K(n)$ :

K(n)=\max\{p(w)\mid |w|=n\}

.

Alors on a :

K(n)=[n/6]+[(n+4)/6]+1

pour

n\neq 11

et

K(11)=5

.

Par exemple, $K(30)=11$ ; ainsi tout mot binaire de longueur 30 est produit d'au plus 11 palindromes, et cette valeur est atteinte.

Algorithmes[modifier | modifier le code]

Le calcul de la longueur palindromique est un problème de combinatoire algorithmique des mots. Plusieurs algorithmes ont été présentés qui calculent la longueur palindromique d'un mot de longueur $n$ en temps $O(n\log \,n)$ ^[3]^,^[4]. En 2017, Borozdin, Kosolobov , Rubinchik et Shur^[5] présentent, au Symposium on Combinatorial Pattern Matching, un algorithme linéaire ; de plus c'est un algorithme en ligne, c'est-à-dire qu'il lit la chaîne séquentiellement et de gauche à droite et calcule la longueur palindromique de chaque préfixe après en avoir lu le dernier caractère. Toutefois, les auteurs disent eux-mêmes que la constante du terme linéaire est telle qu'en pratique un algorithme en $O(n\log \,n)$ est plus rapide.

Un algorithme simple, en temps quadratique et en place linéaire pour calculer la longueur palindromique $p(w)$ d'un mot $w$ de longueur n est basé sur la formule suivante :

p(w[1..j])=\min _{i}\{1+p(w[1..i-1])\mid i\leq j,w[i..j]\ {\text{est un palindrome}}\}

On remplit un tableau de taille $n$ , noté $P$ , où $P[i]$ est la longueur palindromique du préfixe $w[1..i]$ de longueur $i$ de $w$ . À chaque étape $j$ , on calcule l'ensemble $P_{j}$ des positions de départ des suffixes de $w[1..j]$ qui sont des palindromes ; on les obtient à partir des positions de départ de $P_{j-1}$ des suffixes de $w[1..j-1]$ en utilisant le fait que $w[i..j]$ est un palindrome si et seulement si $w[i+1..j-1]$ est un palindrome et $w[i]=w[j]$ . La place requise est clairement linéaire ; on utilise un temps en $O(|P_{j}|+|P_{j-1}|)$ à chaque étape, de sorte que le temps requis est proportionnel au nombre de facteurs palindromiques du mot. Ce nombre peut être quadratique, comme pour le mot $(ab)^{n/2}$ . L'algorithme peut être facilement adapté pour donner une factorisation en palindromes.

Mots infinis[modifier | modifier le code]

Le mot de Thue-Morse est un mot infini dont tous les préfixes d'une longueur une puissance de 4 est un palindrome ; ce sont

0
0110
0110100110010110
...

Les préfixes dont la longueur est 2 fois une puissance de 4 sont produits de deux palindromes. Frid, Puzynina et Zamboni ont montré^[6] que dans le mot de Thue-Morse, et plus généralement dans un mot qui ne contient pas en facteur des puissances arbitrairement élevées, il y a des préfixes de longueur palindromiques arbitrairement grande. Plus précisément, ils prouvent que pour un entier $k$ et un mot infini $w$ sans puissance $k$ -ième, et pour tout entier $m$ , il existe un préfixe $u$ de $w$ de longueur palindromique $p(u)>m$ .

Les auteurs se demandent s'il existe un mot infini non ultimement périodique pour lequel les longueurs palindromiques de tous ses préfixes est bornée. Anna Frid a prouvé^[7] que ceci est impossible dans le cas des mots sturmiens.

La suite des longueurs palindromiques $p_{n}(u)$ des préfixes de longueur n d'un mot infini u est 2-régulière dans le cas du mot de Thue-Morse qui est 2-automatique. Plus généralement, la suite $p_{n}(u)$ d'un mot $k$ -automatique ne qu'un nombre fini de palindromes est $k$ -régulière^[8]. Pour deux mots automatiques, à savoir le mot du pliage de papier et le mot de Rudin-Shapiro, la suite admet une forme explicite.

La suite des différences

d_{n}(u)=p_{n+1}(u)-p_{n}(u)

des longueurs palindromiques des préfixes de $u$ , avec la convention $d_{0}(u)=1$ ne prend que trois valeurs, à savoir -1,0, ou 1. Ceci résulte de l'encadrement

p_{n}(u)-1\leq p_{n+1}\leq p_{n}(u)+1

démontré dans cette forme par Saarela^[9]. Elle a la propriété suivante : Si un mot infini $k$ -automatique $u$ ne contient qu'un nombre fin de palindromes distincts, alors la suite des différences est également $k$ -automatique^[8]. L'hypothèse est remplie par les mots du pliage de papier et de Rudin-Shapiro. Les automates pour ces suites sont assez volumineux^[8].

Notes et références[modifier | modifier le code]

↑ On rencontre aussi les notations PL $(w)$ et $|w|_{\mathrm {pal} }$ .
↑ Ravsky 2003.
↑ Fici et al. 2014.
↑ I, Sugimoto, Inenaga, Bannai et Takeda 2014.
↑ Borozdin et al. 2017.
↑ Frid, Puzynina et Zamboni 2013.
↑ Frid 2018.
↑ ^{a b et c} Frid, Laborde et Peltomäki 2021.
↑ Saarela (2017).

Bibliographie[modifier | modifier le code]

2022 Dora V. Bulgakova, Anna E. Frid et Jérémy Scanvic, « Prefix palindromic length of the Sierpinski word », Developments in Language Theory,‎ 2022 (arXiv 2201.09556).
2021 Anna E. Frid, Enzo Laborde et Jarkko Peltomäki, « On prefix palindromic length of automatic words », Theoretical Computer Science, vol. 891,‎ 4 novembre 2021, p. 13-23 (DOI 10.1016/j.tcs.2021.08.016, arXiv 2009.02934).
2019 Petr Ambrož, Ondřej Kadlec, Zuzana Masáková et Edita Pelantová, « Palindromic length of words and morphisms in class P », Theoretical Computer Science, vol. 780,‎ 2019, p. 74–83 (DOI 10.1016/j.tcs.2019.02.024)
2018 Anna E. Frid, « Sturmian numeration systems and decompositions to palindromes », European Journal of Combinatorics, vol. 71,‎ 2018, p. 202–212 (DOI 10.1016/j.ejc.2018.04.003, arXiv 1710.11553).
2018 Michelangelo Bucci et Gwénaël Richomme, « Greedy Palindromic Lengths », International Journal of Foundations of Computer Science, vol. 29, n^o 03,‎ 2018, p. 331–356 (DOI 10.1142/S0129054118500077, arXiv 1606.05660).
2017 Kirill Borozdin, Dmitry Kosolobov, Mikhail Rubinchik et Arseny M. Shur, « Palindromic Length in Linear Time », dans Juha Kârkkäinen, Jakub Radoszewski et Wojciech Rytter (éditeurs), 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs), » (n^o 78), 2017 (ISBN 978-3-95977-039-2, ISSN 1868-8969, DOI 10.4230/LIPIcs.CPM.2017.23, lire en ligne), p. 23:1-23:12.
2017 Aleksi Saarela, « Palindromic Length in Free Monoids and Free Groups », dans S. Brlek, F. Dolce, C. Reutenauer, É. Vandomme (éditeurs), Combinatorics on Words. WORDS 2017, coll. « Lecture Notes in Computer Science » (n^o 10432), 2017 (DOI 10.1007/978-3-319-66396-8_19, lire en ligne), p. 203–213
2016 Mikhail Rubinchik et Arseny M. Shur, « EERTREE: An Efficient Data Structure for Processing Palindromes in Strings », dans Zsuzsanna Lipták et William F. Smyth (éditeurs), Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), coll. « Lecture Notes in Computer Science » (n^o 9538), 2016 (DOI 10.1007/978-3-319-29516-9_27), p. 321–333.
2015 Dmitry Kosolobov, Mikhail Rubinchik et Arseny M. Shur, « Pal^k is Linear Recognizable Online », dans Giuseppe F. Italiano, Tiziana Margaria-Steffen, Jaroslav Pokorný, Jean-JacquesQuisquater et Roger Wattenhofer (éditeurs), Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), coll. « Lecture Notes in Computer Science » (n^o 8939), 2015 (DOI 10.1007/978-3-662-46078-8_24), p. 289-301
2014 Gabriele Fici, Travis Gagie, Juha Kärkkäinen et Dominik Kempa, « A subquadratic algorithm for minimum palindromic factorization », Journal of Discrete Algorithms, vol. 28,‎ 2014, p. 41–48 (DOI 10.1016/j.jda.2014.08.001).
2014 Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai et Masayuki Takeda, « Computing palindromic factorizations and palindromic covers on-line », dans Alexander S. Kulikov, Sergei O. Kuznetsov, et Pavel A. Pevzner (éditeurs), Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), coll. « Lecture Notes in Computer Science » (n^o 8486) (DOI 10.1007/978-3-319-07566-2_16.), p. 150-161
2013 Anna E. Frid, Svetlana Puzynina et Luca Q. Zamboni, « On palindromic factorization of words », Advances in Applied Mathematics, vol. 50, n^o 5,‎ 2013, p. 737-748 (DOI 10.1016/j.aam.2013.01.002)
2003 Alex Ravsky, « On the palindromic decomposition of binary words », Journal of Automata, Languages and Combinatorics, vol. 8, n^o 1,‎ 2003, p. 75-83 (DOI 10.25596/jalc-2003-075, arXiv 1004.1278)

Articles connexes[modifier | modifier le code]

[1] On rencontre aussi les notations PL $(w)$ et $|w|_{\mathrm {pal} }$ .

[2] Ravsky 2003.

[FiciGagie2014-3] Fici et al. 2014.

[ISugimoto2014-4] I, Sugimoto, Inenaga, Bannai et Takeda 2014.

[5] Borozdin et al. 2017.

[6] Frid, Puzynina et Zamboni 2013.

[7] Frid 2018.

[flp-8] {a b et c} Frid, Laborde et Peltomäki 2021.

[Saarela2017-9] Saarela (2017).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]