Finite automata and arithmetic.
Jean‐Paul Allouche · 1993
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 (see [19]; see also [24]). In 1980, Christol, Kamae, Mendes France and Rauzy, ([18]), 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. See in particular the survey of Dekking, Mendes France and van der Poorten, [22], or the author’s, [2], where many relations between finite automata and number theory (and between finite automata and other mathematical fields) are described. For applications of finite automata to physics see [6]. In the first part of this paper we will recall the basic definitions and give the theorem of Christol, Kamae, Mendes France and Rauzy. We will also give five typical examples of sequences generated by finite automata. In the second part we will discuss transcendence results related to automata theory, giving in particular some results concerning the Carlitz zeta function. We will indicate in the third part of this paper the possible generalizations of these automatic sequences. Finally in an appendix we will give an elementary “automatic” proof of the transcendence of the Carlitz formal power series Π. ∗C. N. R. S., Mathematiques, 351 cours de la Liberation, F-33405 Talence Cedex, (France).