A New Approach to the 2-Regularity of the $\ell$-Abelian Complexity of 2-Automatic Sequences

Aline Parreau, Michel Rigo, Eric Rowland, Élise Vandomme


We prove that a sequence satisfying a certain symmetry property is $2$-regular in the sense of Allouche and Shallit, i.e., the $\mathbb{Z}$-module generated by its $2$-kernel is finitely generated. We apply this theorem to develop a general approach for studying the $\ell$-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.


Automatic sequences; Abelian complexity; regular sequences; Thue-Morse; Period-doubling word

Full Text: PDF