Abelian combinatorics on words: A survey

Lothaire, 1997 Lothaire, 2002 Lothaire, 2005 Pytheas Fogg, 2002, vol. 1794 Allouche, 2003 Choffrut, 1997, Combinatorics of words, 329 2010, vol. 135 Rigo, 2014 Morse, 1938, Symbolic dynamics, Amer. J. Math., 60, 1, 10.2307/2371264 Arnoux, 1991, Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, 119, 199, 10.24033/bsmf.2164 Droubay, 2001, Episturmian words and some constructions by de Luca and Rauzy, Theoret. Comput. Sci., 255, 10.1016/S0304-3975(99)00320-5 de Luca, 1997, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci., 183, 45, 10.1016/S0304-3975(96)00310-6 Mignosi, 1992, Repetitions in the fibonacci infinite word, RAIRO Theor. Inform. Appl., 26, 199, 10.1051/ita/1992260301991 Lind, 1995 Parikh, 1966, On context-free languages, J. ACM, 13, 570, 10.1145/321356.321364 Kamae, 2002, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems, 22, 1191, 10.1017/S014338570200055X Coven, 1973, Sequences with minimal block growth, Math. Systems Theory, 7, 138, 10.1007/BF01762232 Richomme, 2011, Abelian complexity of minimal subshifts, J. Lond. Math. Soc., 83, 79, 10.1112/jlms/jdq063 Richomme, 2010, Balance and Abelian complexity of the Tribonacci word, Adv. Appl. Math., 45, 212, 10.1016/j.aam.2010.01.006 Turek, 2015, Abelian complexity function of the tribonacci word, J. Integer Seq., 18, 15.3.4 Shallit, 2021, Abelian complexity and synchronization, Integers, 21, A36 Cassaigne, 2000, Imbalances in Arnoux-Rauzy sequences, Ann. Inst. Fourier, 50, 1265, 10.5802/aif.1792 Madill, 2013, The abelian complexity of the paperfolding word, Discrete Math., 313, 831, 10.1016/j.disc.2013.01.005 Blanchet-Sadri, 2014, Abelian complexity of fixed point of morphism 0 ↦ 012, 1 ↦ 02, 2 ↦ 1, Integers, 14, A11 Rauzy, 1982, Suites à termes dans un alphabet fini, 1 Currie, 2011, Recurrent words with constant Abelian complexity, Adv. Appl. Math., 47, 116, 10.1016/j.aam.2010.05.001 Saarela, 2009, Ultimately constant abelian complexity of infinite words, J. Autom. Lang. Comb., 14, 255 Pansiot, 1984, Bornes inférieures sur la complexité des facteurs des mots infinis engendrés par morphismes itérés, 230 Adamczewski, 2003, Balances for fixed points of primitive substitutions, Theoret. Comput. Sci., 307, 47, 10.1016/S0304-3975(03)00092-6 Blanchet-Sadri, 2014, On the asymptotic abelian complexity of morphic words, Adv. Appl. Math., 61, 46, 10.1016/j.aam.2014.08.005 Whiteland, 2019, Asymptotic abelian complexities of certain morphic binary words, J. Autom. Lang. Comb., 24, 89 Blanchet-Sadri, 2016, Computing abelian complexity of binary uniform morphic words, Theoret. Comput. Sci., 640, 41, 10.1016/j.tcs.2016.05.046 Kamae, 2006, Maximal pattern complexity of words over l letters, European J. Combin., 27, 125, 10.1016/j.ejc.2004.07.006 Kamae, 2015, Abelian maximal pattern complexity of words, Ergodic Theory Dynam. Systems, 35, 142, 10.1017/etds.2013.51 Richmond, 2009, Counting abelian squares, Electron. J. Combin., 16, 10.37236/161 Holub, 2013, Abelian powers in paper-folding words, J. Combin. Theory Ser. A, 120, 872, 10.1016/j.jcta.2013.01.012 Cassaigne, 2011, Avoiding abelian powers in binary words with bounded abelian complexity, Internat. J. Found. Comput. Sci., 22, 905, 10.1142/S0129054111008489 Krieger, 2007, Every real number greater than 1 is a critical exponent, Theoret. Comput. Sci., 381, 177, 10.1016/j.tcs.2007.04.037 Fici, 2016, Abelian powers and repetitions in Sturmian words, Theoret. Comput. Sci., 635, 16, 10.1016/j.tcs.2016.04.039 Peltomäki, 2020, All growth rates of abelian exponents are attained by infinite binary words, vol. 170, 79:1 Fraenkel, 1998, How many squares can a string contain?, J. Combin. Theory Ser. A, 82, 112, 10.1006/jcta.1997.2843 Brlek, 2022 Li, 2022, On the number of k-powers in a finite word, Adv. Appl. Math., 139, 10.1016/j.aam.2022.102371 Kociumaka, 2016, Maximum number of distinct and nonequivalent nonstandard squares in a word, Theoret. Comput. Sci., 648, 84, 10.1016/j.tcs.2016.08.010 Simpson, 2018 Christodoulakis, 2014, On the average number of regularities in a word, Theoret. Comput. Sci., 525, 3, 10.1016/j.tcs.2013.10.007 Fici, 2017, Abelian-square-rich words, Theoret. Comput. Sci., 684, 29, 10.1016/j.tcs.2017.02.012 Entringer, 1974, On nonrepetitive sequences, J. Combin. Theory Ser. A, 16, 159, 10.1016/0097-3165(74)90041-7 Fici, 2014, On the minimum number of abelian squares in a word, Comb. Algorithmics Strings Dagstuhl Rep., 4, 34 Henshall, 2012, Shuffling and unshuffling, Bull. EATCS, 107, 131 Fici, 2018, Anti-powers in infinite words, J. Combin. Theory Ser. A, 157, 109, 10.1016/j.jcta.2018.02.009 Fici, 2019, Abelian antipowers in infinite words, Adv. Appl. Math., 108, 67, 10.1016/j.aam.2019.04.001 Ochem, 2018, Avoiding or limiting regularities in words, 177 Rampersad, 2016, Repetitions in words Erdős, 1961, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl., 6, 221 Dekking, 1979, Strongly non-repetitive sequences and progression-free sets, J. Combin. Theory Ser. A, 27, 181, 10.1016/0097-3165(79)90044-X Keränen, 1992, Abelian squares are avoidable on 4 letters, vol. 623, 41 Pleasants, 1970, Non-repetitive sequences, Proc. Cambridge Philos. Soc., 68, 267, 10.1017/S0305004100046077 Evdokimov, 1968, Strongly asymmetric sequences generated by a finite number of symbols. (Russian), Dokl. Akad. Nauk SSSR, 179, 1268 Keränen, 2009, A powerful abelian square-free substitution over 4 letters, Theoret. Comput. Sci., 410, 3893, 10.1016/j.tcs.2009.05.027 Carpi, 1993, On abelian power-free morphisms, Internat. J. Algebra Comput., 3, 151, 10.1142/S0218196793000123 Carpi, 1998, On the number of abelian square-free words on four letters, Discrete Appl. Math., 81, 155, 10.1016/S0166-218X(97)88002-X Aberkane, 2004, The number of ternary words avoiding abelian cubes grows exponentially, J. Integer Seq., 7, 04.2.7 Currie, 2004, The number of binary words avoiding abelian fourth powers grows exponentially, Theoret. Comput. Sci., 319, 441, 10.1016/j.tcs.2004.02.005 Rao, 2018, Avoiding two consecutive blocks of same size and same sum over z2, SIAM J. Discrete Math., 32, 2381, 10.1137/17M1149377 Keränen, 2003, New abelian square-free DT0L-languages over 4 letters, Manuscript Rao, 2016, Avoidability of long k-abelian repetitions, Math. Comp., 85, 3051, 10.1090/mcom/3085 Peltomäki, 2020, Avoiding abelian powers cyclically, Adv. Appl. Math., 121, 10.1016/j.aam.2020.102095 Dejean, 1972, Sur un théorème de thue, J. Comb. Theory Ser. A, 13, 90, 10.1016/0097-3165(72)90011-8 Currie, 2011, A proof of Dejean’s conjecture, Math. Comp., 80, 1063, 10.1090/S0025-5718-2010-02407-X Rao, 2011, Last cases of Dejean’s conjecture, Theoret. Comput. Sci., 412, 3010, 10.1016/j.tcs.2010.06.020 Cassaigne, 1999, Words strongly avoiding fractional powers, European J. Combin., 20, 725, 10.1006/eujc.1999.0329 Samsonov, 2012, On abelian repetition threshold, RAIRO Theor. Inform. Appl., 46, 147, 10.1051/ita/2011127 Avgustinovich, 2002, Words avoiding abelian inclusions, J. Autom. Lang. Comb., 7, 3 Dwight Richard Bean, 1979, Avoidable patterns in strings of symbols, Pacific J. Math., 85, 261, 10.2140/pjm.1979.85.261 Zimin, 1984, Blocking sets of terms, Sbornik: Math., 47, 353, 10.1070/SM1984v047n02ABEH002647 Currie, 2008, Long binary patterns are Abelian 2-avoidable, Theoret. Comput. Sci., 409, 432, 10.1016/j.tcs.2008.08.039 Rosenfeld, 2016, Every binary pattern of length greater than 14 is abelian-2-avoidable, vol. 58, 81:1 Currie, 2001, Avoiding patterns in the abelian sense, Canad. J. Math., 53, 10.4153/CJM-2001-028-4 Mignosi, 1993, If a D0L language is k-power free then it is circular, vol. 700, 507 Currie, 2012, Fixed points avoiding Abelian k-powers, J. Combin. Theory Ser. A, 119, 942, 10.1016/j.jcta.2012.01.006 Constantinescu, 2006, Fine and wilf’s theorem for abelian periods, Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS, 89, 167 Fine, 1965, Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc., 16, 109, 10.1090/S0002-9939-1965-0174934-9 Simpson, 2016, An abelian periodicity lemma, Theoret. Comput. Sci., 656, 249, 10.1016/j.tcs.2015.12.014 Césari, 1978, Une caractérisation des mots périodiques, C. R. Math. Acad. Sci. Paris, 286, 1175 Mignosi, 1998, Periodicity and the golden ratio, Theoret. Comput. Sci., 204, 153, 10.1016/S0304-3975(98)00037-1 Avgustinovich, 2012, On abelian versions of critical factorization theorem, RAIRO Theor. Inform. Appl., 46, 3, 10.1051/ita/2011121 Charlier, 2016, Abelian bordered factors and periodicity, European J. Combin., 51, 407, 10.1016/j.ejc.2015.07.003 Domaratzki, 2012, Abelian primitive words, Internat. J. Found. Comput. Sci., 23, 1021, 10.1142/S0129054112400436 Dömösi, 2014 Goč, 2014, On the number of abelian bordered words (with an example of automatic theorem-proving), Internat. J. Found. Comput. Sci., 25, 1097, 10.1142/S0129054114400267 Shallit, 2022 Christodoulakis, 2014, Abelian borders in binary words, Discrete Appl. Math., 171, 141, 10.1016/j.dam.2014.02.012 Blanchet-Sadri, 2022, Dyck words, lattice paths, and abelian borders, Internat. J. Found. Comput. Sci., 33, 203, 10.1142/S0129054122410027 Ehrenfeucht, 1979, Periodicity and unbordered segments of words, Discrete Math., 26, 101, 10.1016/0012-365X(79)90116-X Charlier, 2014, Infinite self-shuffling words, J. Combin. Theory Ser. A, 128, 1, 10.1016/j.jcta.2014.07.008 Holub, 2009, On highly palindromic words, Discrete Appl. Math., 157, 953, 10.1016/j.dam.2008.03.039 Ago, 2021, On highly palindromic words: The n-ary case, Discrete Appl. Math., 304, 98, 10.1016/j.dam.2021.07.020 Mignosi, 1989, Infinite words with linear subword complexity, Theoret. Comput. Sci., 65, 221, 10.1016/0304-3975(89)90046-7 Durand, 2003, Corrigendum and addendum to ‘Linearly recurrent subshifts have a finite number of non-periodic factors’, Ergodic Theory Dynam. Systems, 23, 663, 10.1017/S0143385702001293 Carpi, 2000, Special factors, periodicity, and an application to Sturmian words, Acta Inf., 36, 983, 10.1007/PL00013299 Vandeth, 2000, Sturmian words and words with a critical exponent, Theoret. Comput. Sci., 242, 283, 10.1016/S0304-3975(98)00227-8 Damanik, 2002, The index of Sturmian sequences, European J. Combin., 23, 23, 10.1006/eujc.2000.0496 Currie, 2009, Least periods of factors of infinite words, RAIRO Theor. Inform. Appl., 43, 165, 10.1051/ita:2008006 Peltomäki, 2020, Abelian periods of factors of Sturmian words, J. Number Theory, 214, 251, 10.1016/j.jnt.2020.04.007 Vuillon, 2001, A characterization of Sturmian words by return words, European J. Combin., 22, 263, 10.1006/eujc.2000.0444 Rigo, 2013, Some properties of abelian return words, J. Integer Seq., 16, 13.2.5 Masáková, 2013, Enumerating abelian returns to prefixes of Sturmian words, vol. 8079, 193 Rampersad, 2014, A note on abelian returns in rotation words, Theoret. Comput. Sci., 528, 101, 10.1016/j.tcs.2014.01.033 Saari, 2010, Everywhere α-repetitive sequences and Sturmian words, European J. Combin., 31, 177, 10.1016/j.ejc.2009.01.004 Peltomäki, 2017, A square root map on Sturmian words, Electron. J. Combin., 24, P1.54, 10.37236/6074 Peltomäki, 2016 Huova, 2012, Problems in between words and abelian words: k-abelian avoidability, Theoret. Comput. Sci., 454, 172, 10.1016/j.tcs.2012.03.010 Rao, 2015, On some generalizations of abelian power avoidability, Theoret. Comput. Sci., 601, 39, 10.1016/j.tcs.2015.07.026 Karhumäki, 2013, On a generalization of abelian equivalence and complexity of infinite words, J. Combin. Theory Ser. A, 120, 2189, 10.1016/j.jcta.2013.08.008 Karhumäki, 2017, Variations of the Morse–Hedlund theorem for k-abelian equivalence, Acta Cybern., 23, 175, 10.14232/actacyb.23.1.2017.11 Parreau, 2015, A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences, Electron. J. Combin., 22, 1, 10.37236/4478 Karhumäki, 2017, On cardinalities of k-abelian equivalence classes, Theoret. Comput. Sci., 658, 190, 10.1016/j.tcs.2016.06.010 Cassaigne, 2017, k-Abelian equivalence and rationality, Fund. Inform., 154, 65 Berstel, 1988, vol. 12 Whiteland, 2019 Cassaigne, 2018, On k-abelian palindromes, Inform. and Comput., 260, 89, 10.1016/j.ic.2018.04.001 Karhumäki, 2013, Fine and Wilf’s theorem for k-abelian periods, Internat. J. Found. Comput. Sci., 24, 1135, 10.1142/S0129054113400352 Peltomäki, 2020, On k-abelian equivalence and generalized Lagrange spectra, Acta Arith., 194, 135, 10.4064/aa180927-10-9 Gerver, 1979, On certain sequences of lattice points, Pacific J. Math., 83, 357, 10.2140/pjm.1979.83.357 Avgustinovich, 2016, Weak abelian periodicity of infinite words, Theory Comput. Syst., 59, 161, 10.1007/s00224-015-9629-1 Rigo, 2015, Another generalization of abelian equivalence: Binomial complexity of infinite words, Theoret. Comput. Sci., 601, 47, 10.1016/j.tcs.2015.07.025 Chrisnata, 2022, On the number of distinct k-decks: Enumeration and bounds, Adv. Math. Commun. Lejeune, 2020, The binomial equivalence classes of finite words, Int. J. Algebra Comput., 30, 1375, 10.1142/S0218196720500459 Lejeune, 2020, Templates for the k-binomial complexity of the tribonacci word, Adv. Appl. Math., 112, 10.1016/j.aam.2019.101947 Rigo, 2022, Binomial complexities and parikh-collinear morphisms, vol. 13257, 251 Rao, 2015, Avoiding 2-binomial squares and cubes, Theoret. Comput. Sci., 572, 83, 10.1016/j.tcs.2015.01.029 Halbeisen, 2000, An application of Van der Waerden’s theorem in additive number theory, INTEGERS: Electron. J. Comb. Number Theory Cassaigne, 2014, Avoiding three consecutive blocks of the same size and same sum, J. ACM, 61, 10:1, 10.1145/2590775 Lietard, 2020, Avoidability of additive cubes over alphabets of four numbers, vol. 12086, 192 Lietard, 2020 Puzynina, 2022, Abelian closures of infinite binary words, J. Combin. Theory Ser. A, 185, 10.1016/j.jcta.2021.105524 Karhumäki, 2020 Karhumäki, 2018, On abelian subshifts, vol. 11088, 453 Ferenczi, 1997, Transcendence of numbers with a low complexity expansion, J. Number Theory, 67, 146, 10.1006/jnth.1997.2175 Didier, 1999, Caractérisation des N-écritures et application à l’étude des suites de complexité ultimement n+cste, Theoret. Comput. Sci., 215, 31, 10.1016/S0304-3975(97)00122-9 Kaboré, 2007, Combinatoire de mots récurrents de complexité n+2, RAIRO Theor. Inform. Appl., 41, 425, 10.1051/ita:2007027 Graham, 1973, Covering the positive integers by disjoint sets of the form {[nα+β]:n=1,2,...}, J. Combin. Theory Ser. A, 15, 354, 10.1016/0097-3165(73)90084-8 Hubert, 2000, Suites équilibrées, Theoret. Comput. Sci., 242, 91, 10.1016/S0304-3975(98)00202-3 Hejda, 2015, What is the abelianization of the Tribonacci shift? Zamboni, 2018 Glen, 2009, Palindromic richness, European J. Combin., 30, 510, 10.1016/j.ejc.2008.04.006 Puzynina, 2019, Aperiodic two-dimensional words of small abelian complexity, Electron. J. Combin., 26, P4.15, 10.37236/8580