2013/09/07 by Harju, Tero, Huova, Mari, Zamboni, L. Q.
#68R15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1309.1886
We regard a finite word u=u1u2⋯ un up to word isomorphism as an equivalence relation on \1,2,…, n\ where i is equivalent to j if and only if xi=xj. Some finite words (in particular all binary words) are generated by "\it palindromic" relations of the form k∼ j+i-k for some choice of 1≤ i≤ j≤ n and k∈ \i,i+1,…,j\. That is to say, some finite words u are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function μ(u) defined as the least number of palindromic relations required to generate u. We show that every aperiodic infinite word must contain a factor u with μ(u)≥ 3, and that some infinite words x have the property that μ(u)≤ 3 for each factor u of x. We obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast for the Thue-Morse word, we show that the function μ is unbounded.