×

A powerful abelian square-free substitution over 4 letters. (English) Zbl 1172.68035

Summary: In 1961, Paul Erdös [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 6, 221–254 (1961; Zbl 0100.02001)] posed the question whether abelian squares can be avoided in arbitrarily long words over a finite alphabet. An abelian square is a non-empty word \(u\nu\), where \(u\) and \(\nu\) are permutations (anagrams) of each other. The case of the four letter alphabet \(\Sigma_4={a,b,c,d}\) turned out to be the most challenging and remained open until 1992 when the author presented an abelian square-free (a-2-free) endomorphism \(g_{85}\) of \(\Sigma^*_4\). The size of this \(g_{85}\), i.e., \(|g_{85} (abcd)|\), is equal to \(4\times 85\) (uniform modulus). Until recently, all known methods for constructing arbitrarily long a-2-free words on \(\Sigma_4\) have been based on the structure of \(g_{85}\) and on the endomorphism \(g_{98}\) of \(\Sigma^*_4\) found in 2002.
In this paper, a great many new a-2-free endomorphisms of \(\Sigma^*_4\) are reported. The sizes of these endomorphisms range from \(4 \times102\) to \(4\times 115\). Importantly, twelve of the new a-2-free endomorphisms, of modulus \(m=109\), can be used to construct an a-2-free (commutatively functional) substitution \(\sigma_{109}\) of \(\Sigma^*_4\) with 12 image words for each letter.
The properties of \(\sigma_{109}\) lead to a considerable improvement for the lower bound of the exponential growth of \(c_n\), i.e., of the number of a-2-free words over 4 letters of length \(n\). It is obtained that \(c_n>\beta^{-50}\beta^n\) with \(\beta =12^{1/m} \simeq 1.02306\). Originally, in 1998, Carpi established the exponential growth of \(c_n\) by showing that \(c_n>\beta^{-t}\beta^n\) with \(\beta=2^{19/t}=2^{19/(85^3-85)} \simeq 1.000021\), where \(t=85^3-85\) is the modulus of the substitution that he constructs starting from \(g_{85}\).

MSC:

68Q45 Formal languages and automata

Citations:

Zbl 0100.02001
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Thue, A., Über unendliche Zeichenreihe, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7, 1-22 (1906)
[2] Carpi, A., On abelian power-free morphisms, Internat. J. Algebra Comput., 3, 151-167 (1993) · Zbl 0784.20029
[3] Crochemore, M., Sharp characterizations of square-free morphisms, Theoret. Comput. Sci., 18, 221-226 (1982) · Zbl 0482.68085
[4] V. Keränen, On the k-freeness of morphisms on free monoids, in: Annales Academiæ Scientiarum Fennicæ, Ser. A. I. Mathematica Dissertationes, vol. 61, Finnish Science Academy, 1986, 55 pages; V. Keränen, On the k-freeness of morphisms on free monoids, in: Annales Academiæ Scientiarum Fennicæ, Ser. A. I. Mathematica Dissertationes, vol. 61, Finnish Science Academy, 1986, 55 pages · Zbl 0604.20056
[5] Keränen, V., On the k-freeness of morphisms on free monoids, (Brandenburg, F.; Vidal-Naquet, G.; Wirsing, M., Proc. STACS’87. Proc. STACS’87, Lecture Notes in Comp. Sci., vol. 274 (1987), Springer-Verlag: Springer-Verlag Berlin), 180-188
[6] Leconte, M., A characterization of power-free morphisms, Theoret. Comput. Sci., 38, 117-122 (1985) · Zbl 0572.68066
[7] Leconte, M., Kth power-free codes, (Nivat, M.; Perrin, D., Proc. Automata on Infinite Words’84. Proc. Automata on Infinite Words’84, Lecture Notes in Comp. Sci., vol. 192 (1985), Springer-Verlag: Springer-Verlag Berlin), 172-187 · Zbl 0571.68054
[8] Richomme, G.; Wlazinski, F., Some results on k-power-free morphisms, Theoret. Comput. Sci., 273, 119-142 (2002) · Zbl 1014.68127
[9] F. Wlazinski, Ensembles de test et morphismes sans répétition, Thèse. Université de Picardie Jules Verne \(-\); F. Wlazinski, Ensembles de test et morphismes sans répétition, Thèse. Université de Picardie Jules Verne \(-\)
[10] Berstel, J., Some recent results on square-free words, (Fontet, M.; Melhorn, K., Proc. STACS’84. Proc. STACS’84, Lecture Notes in Comp. Sci., vol. 166 (1984), Springer-Verlag: Springer-Verlag Berlin), 14-25
[11] Hedlund, G., Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tidskr., 15, 148-150 (1967) · Zbl 0153.33101
[12] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, Massachusetts · Zbl 0514.20045
[13] Salomaa, A., Jewels of Formal Language Theory (1981), Computer Science Press: Computer Science Press Rockville, Maryland · Zbl 0487.68063
[14] Mirkin, S., Expandable DNA repeats and human disease, Nature, 447, 932-940 (2007)
[15] Keränen, V., Mathematica in word pattern avoidance research, (Mylläri, A.; Edneral, V.; Ourusoff, N., CADE 2007, Computer Algebra and Differential Equations. CADE 2007, Computer Algebra and Differential Equations, Acta Academiae Aboensis, Ser. B, Mathematica et physica, vol. 67 (2007), A˚bo Akademi University Press), 12-27, Available online at http://urn.fi/URN:ISBN:978-951-765-403-6
[16] Erdös, P., Some unsolved problems, Magyar Tud. Kutató Int. Közl., 6, 221-254 (1961) · Zbl 0100.02001
[17] Pleasants, P., Non-repetitive sequences, Proc. Camb. Phil. Soc., 68, 267-274 (1970) · Zbl 0237.05010
[18] Keränen, V., Abelian squares are avoidable on 4 letters, (Kuich, W., Proc. ICALP’92. Proc. ICALP’92, Lecture Notes in Comp. Sci, vol. 623 (1992), Springer-Verlag: Springer-Verlag Berlin), 41-52 · Zbl 1425.68331
[19] Entringer, R.; Jackson, D.; Schatz, J., On non-repetitive sequences, J. Combin. Theory Ser. A, 16, 159-164 (1974) · Zbl 0279.05001
[20] Dekking, F., Strongly non-repetitive sequences and progression-free sets, J. Combin. Theory Ser. A, 27, 181-185 (1979) · Zbl 0437.05011
[21] Currie, J.; Aberkane, A., A cyclic binary morphism avoiding abelian fourth powers, Theoret. Comput. Sci., 410, 44-52 (2009) · Zbl 1161.68044
[22] Avgustinovich, S.; Frid, A., Words avoiding abelian inclusions, J. Autom. Lang. Comb., 7, 3-9 (2002) · Zbl 1021.68069
[23] Cassaigne, J.; Currie, J., Words strongly avoiding fractional powers, European J. Combin., 20, 725-737 (1999) · Zbl 0948.68140
[24] Currie, J., The number of binary words avoiding abelian fourth powers grows exponentially, Theoret. Comput. Sci., 319, 441-446 (2004) · Zbl 1068.68113
[25] Aberkane, A.; Currie, J.; Rampersad, N., The number of ternary words avoiding abelian cubes grows exponentially, J. Integer Seq., 7, 13 pages (2004), Article 04.2.7 · Zbl 1101.68741
[26] Justin, J.; Pirillo, G.; Varricchio, S., Unavoidable regularities and finiteness conditions for semigroups, (Bertoni, A.; Bohm, C.; Miglioli, P., Proc. 3rd Italian Conf. on Theoret. Comp. Sci. ’89 (1989), World Scientific: World Scientific Singapore), 350-355
[27] Pirillo, G.; Varricchio, S., On uniformly repetitive semigroups, Semigroup Forum, 49, 125-129 (1994) · Zbl 0805.20052
[28] Cori, R.; Formisano, M., Partially abelian square-free words, RAIRO Inform. Théor. Appl., 24, 509-520 (1990) · Zbl 0719.68033
[29] Dickert, V., Research topics in the theory of free partially commutative monoids, Bull. Eur. Assoc. Theor. Comput. Sci., 40, 479-491 (1990)
[30] Laakso, T., Musical rendering of an infinite repetition-free string, (Gefwert, C.; Orponen, P.; Seppänen, J., Logic, Mathematics and the Computer. Logic, Mathematics and the Computer, Proc. Finnish Artificial Intelligence Society, vol. 14 (1996), Hakapaino: Hakapaino Helsinki), 292-297
[31] R. Rivest, Abelian square-free dithering for iterated hash functions, MIT, 2005. Available online at http://people.csail.mit.edu/rivest/publications.html; R. Rivest, Abelian square-free dithering for iterated hash functions, MIT, 2005. Available online at http://people.csail.mit.edu/rivest/publications.html
[32] Andreeva, E.; Bouillaguet, C.; Fouque, P.; Hoch, J.; Kelsey, J.; Shamir, A.; Zimmer, S., Second preimage attacks on dithered hash functions, (Smart, N., Advances in Cryptology-EUROCRYPT 2008. Advances in Cryptology-EUROCRYPT 2008, Lecture Notes in Comp. Sci., vol. 4965 (2008), Springer, Berlin / Heidelberg), 270-288 · Zbl 1149.94302
[33] Carpi, A., On the number of abelian square-free words on four letters, Discrete Appl. Math., 81, 155-167 (1998) · Zbl 0894.68113
[34] Carpi, A., On abelian squares and substitutions, Theoret. Comput. Sci., 218, 61-81 (1999) · Zbl 0916.68117
[35] V. Keränen, A-2-free endomorphisms and substitutions over 4 letters, 2007. Available online at http://south.rotol.ramk.fi/keranen/words2007/a2f.html; V. Keränen, A-2-free endomorphisms and substitutions over 4 letters, 2007. Available online at http://south.rotol.ramk.fi/keranen/words2007/a2f.html
[36] Keränen, V., New abelian square-free DT0L-languages over 4 letters, (Demidov, V.; Keränen, V., Proc. IAS 2002 (2002), Murmansk State Pedagogical Institute and Rovaniemi Polytechnic), Available online at http://south.rotol.ramk.fi/keranen/ias2002/ias2002papers.html · Zbl 1051.68118
[37] Keränen, V., On abelian square-free DT0L-languages over 4 letters, (Harju, T.; Karhumäki, J., Proc. WORDS’03, 4th International Conference on Combinatorics on Words (2003), TUCS General Publication: TUCS General Publication Turku), 95-109 · Zbl 1051.68118
[38] V. Keränen, Suppression of unfavourable factors in pattern avoidance, in: B. Autin, Y. Papegay (Eds.), eProc. (CD) IMS’06, 8th International Mathematica Symposium, 2006, TMJ (in press); V. Keränen, Suppression of unfavourable factors in pattern avoidance, in: B. Autin, Y. Papegay (Eds.), eProc. (CD) IMS’06, 8th International Mathematica Symposium, 2006, TMJ (in press)
[39] S. Mäkelä, Patterns in words, M.Sc. Thesis. Univ. Turku, 2002 (in Finnish); S. Mäkelä, Patterns in words, M.Sc. Thesis. Univ. Turku, 2002 (in Finnish)
[40] P. Ochem, T. Reix., Upper bound on the number of ternary square-free words, in: Proc. Workshop on Words and Automata, St Petersburg Department of Steklov Institute of Mathematics, 2006. Available online at http://www.lri.fr/ ochem/publi.htm; P. Ochem, T. Reix., Upper bound on the number of ternary square-free words, in: Proc. Workshop on Words and Automata, St Petersburg Department of Steklov Institute of Mathematics, 2006. Available online at http://www.lri.fr/ ochem/publi.htm
[41] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L-systems (1980), Academic Press: Academic Press New York, London, Toronto, Sydney, San Fransisco · Zbl 0365.68072
[42] Keränen, V., New abelian square-free endomorphisms and a powerful substitution over 4 letters, (Arnoux, P.; Bédaride, N.; Cassaigne, J., Proc. WORDS’07, 6th International Conference on Combinatorics on Words (2007), Institut de Mathématiques de Luminy: Institut de Mathématiques de Luminy Marseille), 189-200
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.