The Thue-Morse set $\mathcal{T}$ is the set of those non-negative integers whose binary expansions have an even number of $1$'s. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word $${\tt 0110100110010110\cdots},$$ which is the fixed point starting with ${\tt 0}$ of the word morphism ${\tt 0\mapsto 01}$, ${\tt 1\mapsto 10}$. The numbers in $\mathcal{T}$ are commonly called the evil numbers. We obtain an exact formula for the state complexity of the set $m\mathcal{T}+r$ (i.e. the number of states of its minimal automaton) 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 $m\mathcal{T}+r$ for any positive integers $p$ and $m$ and any remainder $r\in\{0,\ldots,m{-}1\}$. The proposed method is general for any $b$-recognizable set of integers.
@article{10_37236_9068,
author = {\'Emilie Charlier and C\'elia Cisternino and Adeline Massuir},
title = {Minimal automaton for multiplying and translating the {Thue-Morse} set},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9068},
zbl = {1517.68179},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9068/}
}
TY - JOUR
AU - Émilie Charlier
AU - Célia Cisternino
AU - Adeline Massuir
TI - Minimal automaton for multiplying and translating the Thue-Morse set
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9068/
DO - 10.37236/9068
ID - 10_37236_9068
ER -
%0 Journal Article
%A Émilie Charlier
%A Célia Cisternino
%A Adeline Massuir
%T Minimal automaton for multiplying and translating the Thue-Morse set
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9068/
%R 10.37236/9068
%F 10_37236_9068
Émilie Charlier; Célia Cisternino; Adeline Massuir. Minimal automaton for multiplying and translating the Thue-Morse set. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9068
