2015/12/14 by Christiane Frougny, Edita Pelantová, Frougny, Christiane +1
Computer Science · Mathematics · #11K16 #68Q45 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT) #cs.FL #math.NT #msc:11K16 #msc:68Q45
paper · pdf · doi:10.48550/arxiv.1512.04234
arxiv created 2018/03/18 · arxiv updated 2018/03/20
Let the base β be a complex number, |β|>1, and let A ⊂ \C be a finite alphabet of digits. The A-spectrum of β is the set SA(β) = \∑k=0n akβk | n ∈ ℕ, ak ∈ A\. We show that the spectrum SA(β) has an accumulation point if and only if 0 has a particular (β, A)-representation, said to be rigid. The first application is restricted to the case that β>1 and the alphabet is A=\-M, …, M\, M ≥ 1 integer. We show that the set Zβ,M of infinite (β, A)-representations of 0 is recognizable by a finite Büchi automaton if and only if the spectrum SA(β) has no accumulation point. Using a result of Akiyama-Komornik and Feng, this implies that Zβ, M is recognizable by a finite Büchi automaton for any positive integer M ≥ \lceil β\rceil -1 if and only if β is a Pisot number. This improves the previous bound M ≥ \lceil β\rceil . For the second application the base and the digits are complex. We consider the on-line algorithm for division of Trivedi and Ercegovac generalized to a complex numeration system. In on-line arithmetic the operands and results are processed in a digit serial manner, starting with the most significant digit. The divisor must be far from 0, which means that no prefix of the (β,A)-representation of the divisor can be small. The numeration system (β,A) is said to allow preprocessing if there exists a finite list of transformations on the divisor which achieve this task. We show that (β,A ) allows preprocessing if and only if the spectrum SA(β) has no accumulation point.