Séminaire Lotharingien de Combinatoire, B30c (1993), 23 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1993, 1993/034, p. 1-18.]

J.-P. Allouche

Finite automata and arithmetic

Abstract. The notion of sequence generated by a finite automaton, (or more precisely a finite automaton with output function, i.e., a "uniform tag system") has been introduced and studied by Cobham in 1972. In 1980, Christol, Kamae, Mendès France and Rauzy proved that a sequence with values in a finite field is automatic if and only if the related formal power series is algebraic over the rational functions with coefficients in this field: this was the starting point of numerous results linking automata theory, combinatorics and number theory. Our aim is to survey some results in this area, especially transcendence results, and to provide the reader with examples of automatic sequences. We will also give a bibliography where more detailed studies can be found.


The following versions are available: