Report
Power-free Complementary Binary Morphisms
| العنوان: | Power-free Complementary Binary Morphisms |
|---|---|
| المؤلفون: | Shallit, Jeffrey, Shur, Arseny M., Zorcic, Stefan |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Formal Languages and Automata Theory |
| الوصف: | 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 $\alpha$-free for every real number $\alpha>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 $\alpha$-free for some $\alpha<3$; in contrast, no binary morphism that maps each letter to a word of length 3 (resp., a word of length 6) is $\alpha$-free for any $\alpha<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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2310.15064 |
| رقم الانضمام: | edsarx.2310.15064 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |