2019/10/18 by Charlier, Émilie, Cisternino, Célia, Massuir, Adeline · 1 citation
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1910.08543
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 \tt abbabaabbaababba⋯, which is the fixed point starting with \tt a of the word morphism \tt a↦ ab,b↦ ba. The numbers in T are commonly called the \em evil numbers. We obtain an exact formula for the state complexity of the set mT+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 2p-expansions of the set of integers mT+r for any positive integers p and m and any remainder r∈\0,…,m-1\. The proposed 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 2p-recognizable set is equal to a set of the form mT+r.