On prefix palindromic length of automatic words

DOI10.1016/J.TCS.2021.08.016zbMATH Open1522.68439arXiv2009.02934MaRDI QIDQ6348553

Jarkko Peltomäki, Enzo Laborde, Anna E. Frid

Publication date: 7 September 2020

Abstract: The prefix palindromic length $mathrm{PPL}_{mathbfu}(n)$ of an infinite word $mathbfu$ is the minimal number of concatenated palindromes needed to express the prefix of length $n$ of $mathbfu$. Since 2013, it is still unknown if $mathrm{PPL}_{mathbfu}(n)$ is unbounded for every aperiodic infinite word $mathbfu$, even though this has been proven for almost all aperiodic words. At the same time, the only well-known nontrivial infinite word for which the function $mathrm{PPL}_{mathbfu}(n)$ has been precisely computed is the Thue-Morse word $mathbft$. This word is $2$-automatic and, predictably, its function $mathrm{PPL}_{mathbft}(n)$ is $2$-regular, but is this the case for all automatic words? In this paper, we prove that this function is $k$-regular for every $k$-automatic word containing only a finite number of palindromes. For two such words, namely the paperfolding word and the Rudin-Shapiro word, we derive a formula for this function. Our computational experiments suggest that generally this is not true: for the period-doubling word, the prefix palindromic length does not look $2$-regular, and for the Fibonacci word, it does not look Fibonacci-regular. If proven, these results would give rare (if not first) examples of a natural function of an automatic word which is not regular.

Mathematics Subject Classification ID

Combinatorics on words (68R15) Automata sequences (11B85)

This page was built for publication: On prefix palindromic length of automatic words