cs.FL
State Complexity of the Multiples of the Thue Morse Set. The Thue Morse set T is the set of those non negative integers whose binary expansions have an even number of 1. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue Morse word abbabaabbaababba..., which is the fixed point starting with a of the word morphism sending a to ab and b to ba. The numbers in T are sometimes called the evil numbers. We obtain an exact formula for the state complexity (i.e. the number of states of its minimal automaton) of the multiplication by a constant of the Thue Morse set with respect to any integer 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 mT for any positive integers m and p. The used method is general for any b recognizable set of integers. As an application, we obtain a decision procedure running in quadratic time for the problem of deciding whether a given 2 p recognizable set is equal to some multiple of the Thue Morse set.