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.
2025
Settore INFO-01/A - Informatica
978-3-95977-369-0
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/688827
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact