pith. sign in

arxiv: 1903.06114 · v1 · pith:AVWYTOCCnew · submitted 2019-03-10 · 💻 cs.FL · cs.DM

State complexity of the multiples of the Thue-Morse set

classification 💻 cs.FL cs.DM
keywords integersthue-morsecomplexityexpansionsmathcalstateableautomaton
0
0 comments X
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.