Computability by finite automata and pisot bases

We prove that the function of normalization in base , which maps any -representation of a real number onto its -development, obtained by a greedy algorithm, is a function computable by a finite automaton over any alphabet if and only if is a Pisot number.Christiane Frougny was supported in part by the PRC Mathématiques et Informatique of the Ministère de la Recherche et de l'Espace.     

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 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 is a Meyer set, which implies that there exists a finite set F (which depends only on β) such that . 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 as a sum belonging to .     

On the Hotz group of a context-free grammar

Summary This note gives a new and algebraic construction of the Hotz group of a context-free grammar. The main result, that the Hotz group is defined by the generated language, as well as the relationships between this group and the syntactic monoid of the language are then easy consequences of this presentation.     

Representations of numbers and finite automata

Numeration systems, the basis of which is defined by a linear recurrence with integer coefficients, are considered. We give conditions on the recurrence under which the function of normalization which transforms any representation of an integer into the normal one—obtained by the usual algorithm—can be realized by a finite automaton. Addition is a particular case of normalization. The same questions are discussed for the representation of real numbers in basis , where is a real number > 1, in connection with symbolic dynamics. In particular it is shown that if is a Pisot number, then the normalization and the addition in basis are computable by a finite automaton.This work has been supported by the PRC Mathématiques et Informatique.     

On alpha-adic expansions in Pisot bases

We study α-adic expansions of numbers, that is to say, left infinite representations of numbers in the positional numeration system with the base α, where α is an algebraic conjugate of a Pisot number β. Based on a result of Bertrand and Schmidt, we prove that a number belongs to if and only if it has an eventually periodic α-adic expansion. Then we consider α-adic expansions of elements of the ring when β satisfies the so-called Finiteness property (F). We give two algorithms for computing these expansions — one for positive and one for negative numbers. In the particular case that β is a quadratic Pisot unit satisfying (F), we inspect the unicity and/or multiplicity of α-adic expansions of elements of . We also provide algorithms to generate α-adic expansions of rational numbers in that case.