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

  • Aline Parreau
  • Michel Rigo
  • Eric Rowland
  • Élise Vandomme
Keywords: Automatic sequences, Abelian complexity, regular sequences, Thue-Morse, Period-doubling word


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.

Article Number