×

Power-free complementary binary morphisms. (English) Zbl 07874976

Summary: 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 \(\alpha\)-free for every real number \(\alpha >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 \notin \{3, 6\}\). Moreover, if \(k\) is not of the form \(3 \cdot 2^n\), then the images of letters can be chosen to be factors of 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.

MSC:

68Rxx Discrete mathematics in relation to computer science
68Qxx Theory of computing
20Mxx Semigroups

Software:

Walnut

References:

[1] Allouche, J.; Shallit, J. O., Automatic Sequences: Theory, Applications, Generalizations, 2003, Cambridge University Press · Zbl 1086.11015
[2] Badkobeh, G.; Crochemore, M., Infinite binary words containing repetitions of odd period, Inf. Process. Lett., 115, 543-547, 2015 · Zbl 1328.68154
[3] Bean, D. A.; Ehrenfeucht, A.; McNulty, G., Avoidable patterns in strings of symbols, Pac. J. Math., 85, 261-294, 1979 · Zbl 0428.05001
[4] Berstel, J.; Séébold, P., A characterization of overlap-free morphisms, Discrete Appl. Math., 46, 275-281, 1993 · Zbl 0824.68093
[5] (Berthé, V.; Rigo, M., Combinatorics, Words and Symbolic Dynamics. Combinatorics, Words and Symbolic Dynamics, Encyclopedia of Mathematics and Its Applications, 2016, Cambridge University Press) · Zbl 1404.11003
[6] Brandenburg, F., Uniformly growing k-th power-free homomorphisms, Theor. Comput. Sci., 23, 69-82, 1983 · Zbl 0508.68051
[7] Bruyère, V.; Hansel, G.; Michaux, C.; Villemaire, R., Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin. Bull. Belg. Math. Soc. Simon Stevin, Bull. Belg. Math. Soc. Simon Stevin, 1, 577-238, 1994, Corrigendum: · Zbl 0804.11024
[8] Crochemore, M., Sharp characterizations of squarefree morphisms, Theor. Comput. Sci., 18, 221-226, 1982 · Zbl 0482.68085
[9] Currie, J. D.; Rampersad, N., There are k-uniform cubefree binary morphisms for all \(k \geq 0\), Discrete Appl. Math., 157, 2548-2551, 2009 · Zbl 1211.05006
[10] Dejean, F., Sur un théorème de Thue, J. Comb. Theory, Ser. A, 13, 90-99, 1972 · Zbl 0245.20052
[11] Du, C. F.; Shallit, J. O.; Shur, A. M., Optimal bounds for the similarity density of the Thue-Morse word with overlap-free and \((7 / 3)\)-power-free infinite binary words, Int. J. Found. Comput. Sci., 26, 1147-1166, 2015 · Zbl 1341.68143
[12] Karhumäki, J.; Shallit, J. O., Polynomial versus exponential growth in repetition-free binary words, J. Comb. Theory, Ser. A, 105, 335-347, 2004 · Zbl 1065.68080
[13] Keränen, V., On k-repetition freeness of length uniform morphisms over a binary alphabet, Discrete Appl. Math., 9, 297-300, 1984 · Zbl 0547.68082
[14] Kobayashi, Y., Repetition-free words, Theor. Comput. Sci., 44, 175-197, 1986 · Zbl 0596.20058
[15] Leconte, M., A characterization of power-free morphisms, Theor. Comput. Sci., 38, 117-122, 1985 · Zbl 0572.68066
[16] Meleshko, J.; Ochem, P.; Shallit, J.; Shan, S. L., Pseudoperiodic words and a question of Shevelev, Discret. Math. Theor. Comput. Sci., 25, Article #6 pp., 2023 · Zbl 07908406
[17] Mousavi, H., Automatic theorem proving in Walnut, 2016, Preprint, available at
[18] Petrova, E. A.; Shur, A. M., Constructing premaximal ternary square-free words of any level, (Rovan, B.; Sassone, V.; Widmayer, P., Mathematical Foundations of Computer Science 2012—37th International Symposium, MFCS 2012, Proceedings, 2012, Springer), 752-763 · Zbl 1365.68364
[19] Richomme, G.; Séébold, P., Conjectures and results on morphisms generating k-power-free words, Int. J. Found. Comput. Sci., 15, 307-316, 2004 · Zbl 1067.68118
[20] Richomme, G.; Wlazinski, F., Some results on k-power-free morphisms, Theor. Comput. Sci., 273, 119-142, 2002 · Zbl 1014.68127
[21] Richomme, G.; Wlazinski, F., Overlap-free morphisms and finite test-sets, Discrete Appl. Math., 143, 92-109, 2004 · Zbl 1073.68069
[22] Richomme, G.; Wlazinski, F., Existence of finite test-sets for k-power-freeness of uniform morphisms, Discrete Appl. Math., 155, 2001-2016, 2007 · Zbl 1129.68053
[23] Shallit, J., Fife’s theorem revisited, (Mauri, G.; Leporati, A., DLT ’11: Proceedings of the 15th International Conf. on Developments in Language Theory, 2011, Springer), 397-405 · Zbl 1221.68145
[24] Shallit, J., The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut, London Mathematical Society Lecture Note Series, 2022, Cambridge University Press
[25] Shallit, J. O.; Shur, A. M., Subword complexity and power avoidance, Theor. Comput. Sci., 792, 96-116, 2019 · Zbl 1447.68014
[26] Shur, A. M., The structure of the set of cube-free Z-words in a two-letter alphabet, Izv. Math., 64, 847-871, 2000 · Zbl 0972.68131
[27] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Nor. Vidensk. Selsk. Skr. Mat. Nat. Kl., 1, 1-67, 1912 · JFM 44.0462.01
[28] Wlazinski, F., A test-set for k-power-free binary morphisms, RAIRO Theor. Inform. Appl., 35, 437-452, 2001 · Zbl 1010.68102
[29] Wlazinski, F., Reduction in non-\((k + 1)\)-power-free morphisms, RAIRO Theor. Inform. Appl., 50, 3-20, 2016 · Zbl 1362.68243
[30] Wlazinski, F., A uniform cube-free morphism is k-power-free for all integers \(k \geq 4\), RAIRO Theor. Inform. Appl., 51, 205-216, 2017 · Zbl 1453.68147
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.