Arithmetic Meyer sets and finite automata

Non-standard number representation has proved to be useful in the speed-up of some algorithms, and in the modelization of solids called quasicrystals. Using tools from automata theory we study the set Z β of β-integers, that is, the set of real numbers which have a zero fractional part when expanded in a real base β, for a given β >1. In particular, when β is a Pisot number — like the golden mean —, the set Z β is a Meyer set, which implies that there exists a finite set F (which depends only on β) such that Z β - Z β ⊂ Z β + F. Such a finite set F, even of minimal size, is not uniquely determined. In this paper we give a method to construct the sets F and an algorithm, whose complexity is exponential in time and space, to minimize their size. We also give a finite transducer that performs the decomposition of the elements of Z β - Z β as a sum belonging to Z β + F.

Authors

• Shigeki Akiyama
• Frédérique Bassino
• Christiane Frougny

Keywords

No keywords are indexed for this paper.