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: