The complexity of Cbω-words of the form w̃xw

AbstractLet pn(∞) denote the number of Cbω-words of the form w̃xw with gap n and pn(k) denote the number of C∞-words of the form w̃xw with length 2k+n and gap n, where n is the length of the word x. [S. Brlek, A. Ladouceur, A note on differentiable palindromes, Theoret. Comput. Sci. 302 (2003) 167–178] proved that C∞-palindromes are characterized by the left palindromic closure of the prefixes of the well-known Kolakoski sequences and revealed an interesting perspective for understanding some of the conjectures. In fact, they found all infinite C∞-palindromes and established p0(k)=p1(k)=2 for all k∈N, where N is the set of positive integers. [Y.B. Huang, About the number of C∞-words of form w̃xw, Theoret. Comput. Sci. 393 (2008) 280–286] obtained pn(k)=6 for all k∈N and n=2,3,4, and gave all Cbω-words of the form w̃xw with gap less than 5, which imply pn(∞)=2 for n=0,1, and pn(∞)=6 for n=2,3,4. In this paper, we prove the following intriguing results: (1) If w̃xw∈Cbω and ∣x∣≥7 then the first and last letters of the word x are the same; (2) pn(∞)=14 for n≥5; (3) For every positive integer n, there exists a positive integer H(n) such that for all k∈N, if k>H(n) then pn(k)=p5(k) if k is odd and pn(k)=p6(k) if k is even, which would help us understand better the complexity of finite C∞-words of the form w̃xw. Moreover, we provide all twenty eight Cbω-words of the form w̃xw