
























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 $\mathbf{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 $\mathbf{t}$ that give cubefree complementary morphisms. Next, we show that $3$-free (cubefree) complementary morphisms of length $k$ exist for all $k\not\in \{3,6\}$. Moreover, if $k$ is not of the form $3\cdot2^n$, then the images of letters can be chosen to be factors of $\mathbf{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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。