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.
Additional Information
- Michaël Rao
- Affiliation: École Normale Supérieure de Lyon, LIP (UMR 5668 CNRS, ENSL, Inria, UCBL, UDL), 46 allée d’Italie, 69364 Lyon Cedex 07, France
- MR Author ID: 714149
- Email: michael.rao@ens-lyon.fr
- Matthieu Rosenfeld
- Affiliation: École Normale Supérieure de Lyon, LIP (UMR 5668 CNRS, ENSL, Inria, UCBL, UDL), 46 allée d’Italie, 69364 Lyon Cedex 07, France
- Email: matthieu.rosenfeld@ens-lyon.fr
- Received by editor(s): February 24, 2015
- Received by editor(s) in revised form: May 29, 2015
- Published electronically: February 18, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 3051-3060
- MSC (2010): Primary 68R15
- DOI: https://doi.org/10.1090/mcom/3085
- MathSciNet review: 3522981