[en] 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 l-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. The computation and arguments leading to these results fit into a quite general scheme that can be used to obtain additional regularity results. This supports the conjecture that the l-abelian complexity of a $k$-automatic sequence is a k-regular sequence.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
On a conjecture about regularity and l-abelian complexity
Publication date :
25 April 2017
Event name :
School on bridges between Automatic Sequences, Algebra and Number Theory