We say a finite word x is a palindromic periodicity if there exist two palindromes p and s such that |x| ≥ |ps| and x is a prefix of the infinite periodic word (ps)ω = pspsps···. In this paper we examine the palindromic periodicities occurring in some classical infinite words, such as Sturmian words, episturmian words, the Thue–Morse word, the period-doubling word, the Rudin–Shapiro word, the paperfolding word, and the Tribonacci word, and prove a number of results about them. We also prove results about words with the smallest number of distinct palindromic periodicities.
Fici, G., Shallit, J., Simpson, J. (2025). On Palindromic Periodicities. In P. Bonizzoni, V. Mäkinen (a cura di), 36th Annual Symposium on Combinatorial Pattern Matching CPM 2025, June 17–19, 2025, Milan, Italy. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.CPM.2025.11].
On Palindromic Periodicities
Fici G.
;
2025-01-01
Abstract
We say a finite word x is a palindromic periodicity if there exist two palindromes p and s such that |x| ≥ |ps| and x is a prefix of the infinite periodic word (ps)ω = pspsps···. In this paper we examine the palindromic periodicities occurring in some classical infinite words, such as Sturmian words, episturmian words, the Thue–Morse word, the period-doubling word, the Rudin–Shapiro word, the paperfolding word, and the Tribonacci word, and prove a number of results about them. We also prove results about words with the smallest number of distinct palindromic periodicities.| File | Dimensione | Formato | |
|---|---|---|---|
|
On Palindromic Periodicities.pdf
accesso aperto
Tipologia:
Versione Editoriale
Dimensione
1.05 MB
Formato
Adobe PDF
|
1.05 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


