Prefix palindromic length of the Sierpinski word

DOI10.1007/978-3-031-05578-2_6arXiv2201.09556MaRDI QIDQ6388995

Jérémy Scanvic, Dora Bulgakova, Anna E. Frid

Publication date: 24 January 2022

Abstract: The prefix palindromic length $p_{mathbfu}(n)$ of an infinite word $mathbfu$ is the minimal number of concatenated palindromes needed to express the prefix of length $n$ of $mathbfu$. This function is surprisingly difficult to study; in particular, the conjecture that $p_{mathbfu}(n)$ can be bounded only if $mathbfu$ is ultimately periodic is open since 2013. A more recent conjecture concerns the prefix palindromic length of the period doubling word: it seems that it is not $2$-regular, and if it is true, this would give a rare if not unique example of a non-regular function of a $2$-automatic word. For some other $k$-automatic words, however, the prefix palindromic length is known to be $k$-regular. Here we add to the list of those words the Sierpinski word $mathbfs$ and give a complete description of $p_{mathbfs}(n)$.

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

This page was built for publication: Prefix palindromic length of the Sierpinski word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6388995)