Prefix palindromic length of the Thue-Morse word

MaRDI QIDQ5212137zbMATH OpenFDO

Authors Anna Frid

Publication date 27 January 2020

Full work available at URL https://arxiv.org/abs/1906.09392, https://cs.uwaterloo.ca/journals/JIS/VOL22/Frid/frid4.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

automatic wordpalindromic lengthregular sequenceThue-Morse word

Mathematics Subject Classification ID

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

Abstract: The prefix palindromic length $PP{L}_u(n)$ of an infinite word $u$ is the minimal number of concatenated palindromes needed to express the prefix of length $n$ of $u$. In a 2013 paper with Puzynina and Zamboni we stated the conjecture that $PP{L}_u(n)$ is unbounded for every infinite word $u$ which is not ultimately periodic. Up to now, the conjecture has been proven for almost all words, including all words avoiding some power $p$. However, even in that simple case the existing upper bound for the minimal number $n$ such that $PP{L}_u(n)>K$ is greater than any constant to the power $K$. Precise values of $PP{L}_u(n)$ are not known even for simplest examples like the Fibonacci word. In this paper, we give the first example of such a precise computation and compute the function of the prefix palindromic length of the Thue-Morse word, a famous test object for all functions on infinite words. It happens that this sequence is $2$-regular, which raises the question if this fact can be generalized to all automatic sequences.

Recommendations

• On prefix palindromic length of automatic words
• Prefix palindromic length of the Sierpinski word
• First lower bounds for palindromic length
• On palindromic factorization of words
• Words with many palindrome pair factors
• On palindromic length of Sturmian sequences
• Palindromic length of words and morphisms in class \(\mathcal{P}\)
• Greedy palindromic lengths
• Palindromic length of words with many periodic palindromes
• Palindromic length in free monoids and free groups

Cites work

• A subquadratic algorithm for minimum palindromic factorization
• Automatic Sequences
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• Enumeration and decidable properties of automatic sequences
• First lower bounds for palindromic length
• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• On palindromic factorization of words
• Palindromic length in free monoids and free groups
• Palindromic length in linear time
• Palindromic length of words and morphisms in class \(\mathcal{P}\)
• Sturmian numeration systems and decompositions to palindromes
• The ring of k-regular sequences
• Uniform tag sequences

Cited in

(9)

• Palindromic length in free monoids and free groups
• Monochromatic arithmetic progressions in binary Thue-Morse-like words
• Prefix palindromic length of the Sierpinski word
• Borders, palindrome prefixes, and square prefixes
• On prefix palindromic length of automatic words
• First lower bounds for palindromic length
• Palindromic length of words and morphisms in class \(\mathcal{P}\)
• Combinatorial properties of f-palindromes in the Thue-Morse sequence
• Greedy palindromic lengths

Describes a project that uses

Uses Software

• OEIS
• EERTREE

This page was built for publication: Prefix palindromic length of the Thue-Morse word

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