Avoidability of long 𝑘-abelian repetitions

Rao, Michaël; Rosenfeld, Matthieu

doi:10.1090/mcom/3085

Avoidability of long $k$-abelian repetitions
HTML articles powered by AMS MathViewer

by Michaël Rao and Matthieu Rosenfeld PDF

Math. Comp. 85 (2016), 3051-3060 Request permission

Abstract:

We study the avoidability of long $k$-abelian-squares and $k$-abelian-cubes on binary and ternary alphabets. For $k=1$, these are Mäkelä’s questions. We show that one cannot avoid abelian-cubes of abelian period at least $2$ in infinite binary words, and therefore answering negatively one question from Mäkelä. Then we show that one can avoid $3$-abelian-squares of period at least $3$ in infinite binary words and $2$-abelian-squares of period at least 2 in infinite ternary words. Finally, we study the minimum number of distinct $k$-abelian-squares that must appear in an infinite binary word.

References

Arturo Carpi, On abelian power-free morphisms, Internat. J. Algebra Comput. 3 (1993), no. 2, 151–167. MR 1233218, DOI 10.1142/S0218196793000123
Arturo Carpi, On the number of abelian square-free words on four letters, Discrete Appl. Math. 81 (1998), no. 1-3, 155–167. MR 1492008, DOI 10.1016/S0166-218X(97)88002-X
F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, J. Combin. Theory Ser. A 27 (1979), no. 2, 181–185. MR 542527, DOI 10.1016/0097-3165(79)90044-X
R. C. Entringer, D. E. Jackson, and J. A. Schatz, On nonrepetitive sequences, J. Combinatorial Theory Ser. A 16 (1974), 159–164. MR 332533, DOI 10.1016/0097-3165(74)90041-7
Paul Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), 291–300. MR 98702
Paul Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221–254. MR 177846
A. A. Evdokimov, Strongly asymmetric sequences generated by a finite number of symbols. , Dokl. Akad. Nauk SSSR 179 (1968), 1268–1271 (Russian). MR 0234842
Aviezri S. Fraenkel and R. Jamie Simpson, How many squares must a binary sequence contain?, Electron. J. Combin. 2 (1995), Research Paper 2, approx. 9. MR 1309124
Juhani Karhumaki, Aleksi Saarela, and Luca Q. Zamboni, On a generalization of Abelian equivalence and complexity of infinite words, J. Combin. Theory Ser. A 120 (2013), no. 8, 2189–2206. MR 3102181, DOI 10.1016/j.jcta.2013.08.008
Veikko Keränen, Abelian squares are avoidable on $4$ letters, Automata, languages and programming (Vienna, 1992) Lecture Notes in Comput. Sci., vol. 623, Springer, Berlin, 1992, pp. 41–52. MR 1250629, DOI 10.1007/3-540-55719-9_{6}2
Veikko Keränen, New abelian square-free DT0L-languages over 4 letters., Manuscript (2003).
M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997. With a foreword by Roger Lyndon and a preface by Dominique Perrin; Corrected reprint of the 1983 original, with a new preface by Perrin. MR 1475463, DOI 10.1017/CBO9780511566097
P. A. B. Pleasants, Non-repetitive sequences, Proc. Cambridge Philos. Soc. 68 (1970), 267–274. MR 265173, DOI 10.1017/s0305004100046077
Michaël Rao, On some generalizations of abelian power avoidability, Theoret. Comput. Sci. 601 (2015), 39–46. MR 3396334, DOI 10.1016/j.tcs.2015.07.026
A. Thue, Über die gegenseitige lage gleicher teile gewisser zeichenreihen., Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania 10 (1912), 1–67.