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

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

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

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

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

↑ 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

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

[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]