##
**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\).

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\).

### MSC:

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. |

### Keywords:

Prouhet-Thue-Morse sequence; Rudin-Shapiro sequence; paperfolding sequence; Baum-Sweet sequence; Hanoi sequence; survey; finite automata; transcendence; bibliography; uniform tag system; Carlitz zeta-function; automatic sequences; formed power series; substitution### Citations:

Zbl 0253.02029; Zbl 0472.10035; Zbl 0493.10001; Zbl 0439.10002; Zbl 0439.10003; Zbl 0641.10041; Zbl 0713.11019
PDFBibTeX
XMLCite

\textit{J.-P. Allouche}, Sémin. Lothar. Comb. 30, B30c, 23 p. (1993; Zbl 0903.11009)

Full Text:
EuDML

### Online Encyclopedia of Integer Sequences:

Baum-Sweet sequence: a(n) = 1 if binary representation of n contains no block of consecutive zeros of odd length; otherwise a(n) = 0.Prime analog of Baum-Sweet sequence: a(n) = 1 if binary representation of n contains no block of consecutive zeros of exactly prime length; otherwise a(n) = 0.

Numbers n such that n in binary representation has a block of exactly a semiprime number of zeros.

Numbers n such that n in binary representation has a block of exactly a nontrivial triangular number number of zeros.

Numbers n such that n in binary representation has a block of exactly a nontrivial square number of zeros.

Numbers n such that n in ternary representation (A007089) has a block of exactly a prime number of consecutive zeros.

Numbers n such that n in binary representation has a block of exactly a nontrivial pentagonal number of zeros.