Evil numbers; State complexity; Numeration systems
Abstract :
[en] The Thue-Morse set is the set of those nonnegative integers whose binary expansions have an even number of 1. Its characteristic sequence is given by the famous Thue-Morse word, which is the fixed point starting with 1 of the morphism 0->01,1->10. We obtain an exact formula for the state complexity of the multiplication by a constant of the Thue-Morse set T with respect to any base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set of integers mT for any positive integers m and p.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Cisternino, Célia ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Massuir, Adeline ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
State complexity of the multiples of the Thue-Morse set