Regularity and L-abelian complexity

Since the fundamental work of Cobham, the so-called automatic sequences have been extensively studied. A natural generalization of automatic sequences over an infinite alphabet is given by the notion of k-regular sequences, introduced by Allouche and Shallit in 1992. The k-regularity of a sequence provides us with structural information about how the different terms are related to each other. We show that a sequence satisfying a certain symmetry property is 2-regular. We apply this theorem to develop a general approach for studying the ℓ-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue–Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results.