Ouvrir le menu principal

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.

ExemplesModifier

Notons   la longueur palindromique d'un mot  . 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  (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   est au plus  .

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 majorationModifier

Notons   la longueur palindromique d'un mot  [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   :

 .

Alors on a :

  pour   et  .

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

AlgorithmesModifier

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   en temps  [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   est plus rapide.

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

 

On remplit un tableau de taille  , noté  , où   est la longueur palindromique du préfixe   de longueur   de  . À chaque étape  , on calcule l'ensemble   des positions de départ des suffixes de   qui sont des palindromes ; on les obtient à partir des positions de départ de   des suffixes de   en utilisant le fait que   est un palindrome si et seulement si   est un palindrome et  . La place requise est clairement linéaire ; on utilise un temps en   à 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  . L'algorithme peut être facilement adapté pour donner une factorisation en palindromes.

Mots infinisModifier

Le mot de Thue-Morse est un mot infini dont tous les préfixes dont la longueur est 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 :

Soit   un entier positif et   un mot infini. Si   est sans puissance  -ième, alors pour tout entier  , il existe un préfixe   de   de longueur palindromique  .

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.

Notes et référencesModifier

  1. On rencontre aussi les notations PL  et  .
  2. Ravsky 2003.
  3. Fici et al. 2014.
  4. I, Sugimoto, Inenaga, Bannai et Takeda 2014.
  5. Borozdin et al. 2017.
  6. Frid, Puzynina et Zamboni 2013.
  7. Frid 2018.

BibliographieModifier

  • 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,‎ , 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,‎ , 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, no 03,‎ , 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), » (no 78), (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 Combinatorics on Words. WORDS 2017, coll. « Lecture Notes in Computer Science » (no 10432), (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 » (no 9538), (DOI 10.1007/978-3-319-29516-9_27), p. 321–333.
  • 2015 Dmitry Kosolobov, Mikhail Rubinchik et Arseny M. Shur, « Palk 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 » (no 8939), (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,‎ , 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 » (no 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, no 5,‎ , 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, no 1,‎ , p. 75-83 (DOI 10.25596/jalc-2003-075, arXiv 1004.1278)

Articles connexesModifier