Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes (Q2354723): Difference between revisions

Recently, the concept of privileged words that can occur as factors in infinite words was introduced. The shortest privileged words are the empty word and the letters of the alphabet; a word is then defined as privileged if it is a complete first return to a shorter privileged word. In this very interesting paper, the author shows similarities between privileged words and palindromes, that is, words that coincide with their reversals. He establishes connections between privileged words and rich words, that is, words that contain the maximum possible number of distinct palindromes. Furthermore, the author studies the Thue-Morse word's privileged complexity function, that is, the function that counts the number of distinct privileged factors of each given length in the fixed point of the morphism \(0 \mapsto 01, 1 \mapsto 10\), starting at 0. He proves a recursive formula for that function and shows that it is unbounded with arbitrarily large gaps of 0s. This demonstrates a behavior drastically different from that of the Thue-Morse word's palindromic complexity function that counts the number of distinct palindromes of each given length.