DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2025.11

On Palindromic Periodicities

Authors: Gabriele Fici, Jeffrey Shallit, and Jamie Simpson

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

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.

Cite as

Gabriele Fici, Jeffrey Shallit, and Jamie Simpson. On Palindromic Periodicities. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.CPM.2025.11,
  author =	{Fici, Gabriele and Shallit, Jeffrey and Simpson, Jamie},
  title =	{{On Palindromic Periodicities}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.11},
  URN =		{urn:nbn:de:0030-drops-231051},
  doi =		{10.4230/LIPIcs.CPM.2025.11},
  annote =	{Keywords: Combinatorics on words, Palindrome, Symmetric word, Palindromic periodicity, Walnut, Thue-Morse word, Sturmian word, Episturmian word}
}

Search Results

Documents authored by Simpson, Jamie

On Palindromic Periodicities

Abstract

Cite as

Thanks for your feedback!

Could not send message