Finite automata and arithmetic. (English) Zbl 0903.11009

From the introduction: The notion of sequences 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 A. Cobham in 1972 [see Math. Syst. Theory 6, 164-192 (1972; Zbl 0253.02029)]. In 1980, G. Christol, T. Kamae, M. Mendès-France and G. Rauzy [Bull. Soc. Math. Fr. 108, 401-419 (1980; Zbl 0472.10035)] 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.
The aim of this paper is to survey some results in this area, especially transcendence results, and to provide the reader with examples of automatic sequences. The author also gives a bibliography where more detailed studies can be found. See in particular the survey of M. Dekking, M. Mendès-France and A. J. van der Poorten [Math. Intell. 4, 130-138 (1982; Zbl 0493.10001); ibid., 173-181 (1982; Zbl 0439.10002), and ibid., 190-195 (1982; Zbl 0439.10003)] or the author’s, [J.-P. Allouche, Expo. Math. 5, 239-266 (1987; Zbl 0641.10041)], 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 [J.-P. Allouche, in Number theory and physics, Springer Proc. Phys. 47, 177-184 (1990; Zbl 0713.11019)].
In the first part of this paper the author recalls the basic definitions and gives the theorem of Christol, Kamae, Mendès-France and Rauzy. He also gives five typical examples of sequences generated by finite automata.
In the second part he discusses transcendence results related to automata theory, giving in particular some results concerning the Carlitz zeta function.
He indicates in the third part of this paper the possible generalizations of these automatic sequences. Finally in an appendix he gives an elementary “automatic” proof of the transcendence of the Carlitz formal power series \(\Pi\).


11B85 Automata sequences
68Q45 Formal languages and automata
11-02 Research exposition (monographs, survey articles) pertaining to number theory
11J81 Transcendence (general theory)
11G09 Drinfel’d modules; higher-dimensional motives, etc.
Full Text: EuDML