2023/10/23 by Shallit, Jeffrey, Shur, Arseny M., Zorcic, Stefan · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2310.15064
We revisit the topic of power-free morphisms, focusing on the properties of the class of complementary morphisms. Such morphisms are defined over a 2-letter alphabet, and map the letters 0 and 1 to complementary words. We prove that every prefix of the famous Thue-Morse word t gives a complementary morphism that is 3+-free and hence α-free for every real number α>3. We also describe, using a 4-state binary finite automaton, the lengths of all prefixes of t that give cubefree complementary morphisms. Next, we show that 3-free (cubefree) complementary morphisms of length k exist for all k\not∈ \3,6\. Moreover, if k is not of the form 3⋅2n, then the images of letters can be chosen to be factors of t. Finally, we observe that each cubefree complementary morphism is also α-free for some α<3; in contrast, no binary morphism that maps each letter to a word of length 3 (resp., a word of length 6) is α-free for any α<3. In addition to more traditional techniques of combinatorics on words, we also rely on the Walnut theorem-prover. Its use and limitations are discussed.