State complexity of the multiples of the Thue-Morse set
classification
💻 cs.FL
cs.DM
keywords
integersthue-morsecomplexityexpansionsmathcalstateableautomaton
read the original abstract
The Thue-Morse set is the set of those nonnegative integers whose binary expansions have an even number of $1$. We obtain an exact formula for the state complexity of the multiplication by a constant of the Thue-Morse set $\mathcal{T}$ with respect with 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}$ for any positive integers $m$ and $p$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.