2022/01/24 by Dora V. Bulgakova, Bulgakova, Dora V., Anna E. Frid +3
Computer Science · Mathematics · #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2201.09556
openalex publication_date 2022/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The prefix palindromic length pu(n) of an infinite word u is the minimal number of concatenated palindromes needed to express the prefix of length n of u. This function is surprisingly difficult to study; in particular, the conjecture that pu(n) can be bounded only if u 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 s and give a complete description of ps(n).