\documentstyle[11pt]{article} \newcommand{\GN}{\mbox{\rm I$\!$N}} \newcommand{\GF}{\mbox{\rm I$\!$F}} \newcommand{\GZ}{\mbox{\rm Z$\!\!$Z}} \author{J.-P. Allouche \thanks{C. N. R. S., Math\'ematiques, 351 cours de la Lib\'eration, F-33405 Talence Cedex, (France).}} \title{Finite automata and arithmetic} \date{} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{definition}{Definition} \begin{document} \maketitle \section{Introduction} 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 \cite{Cobham1}; see also \cite{Eilenberg}). In 1980, Christol, Kamae, Mend\`es France and Rauzy, (\cite{CKMFR}), 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, Mend\`es France and van der Poorten, \cite{Dekking}, or the author's, \cite{Alloucheexpo}, 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 \cite{Allouchephys}. In the first part of this paper we will recall the basic definitions and give the theorem of Christol, Kamae, Mend\`es 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 $\Pi$. \section{Generalities, examples, the main theorem} \subsection{Sequences generated by finite automata} \begin{definition} Let $q$ be an integer ($q \geq 2$). A $q$-automaton consists of - a finite set $S = \{a_1 = i, a_2, \cdots, a_d \}$, which is called the set of states. One of the states is denoted by $i$ and called the initial state, - $q$ maps from $S$ to itself, labelled $0, 1, \cdots, q-1$. The image of the state $s$ by the map $j$ is denoted by $j.s$, - a map (the output function), say $\varphi$, from $S$ to a set $Y$. \noindent This ``machine" generates a sequence with values in $Y$, say $(u_n)_{n \geq 0}$, as follows: to compute the term $u_n$, one expands $n$ in base $q$, say $n = \sum_{j=0}^{\ell} n_j q^j$, with $0 \leq n_j \leq q-1$. Then each $n_j$ is interpreted as one of the maps from $S$ to itself, and these maps are applied to $i$ to obtain: $$u_n = \varphi \left [n_{\ell}(n_{\ell -1}(\cdots(n_1(n_0.i))\cdots)) \right ].$$ \noindent Such a sequence is called a {\bf $q$-automatic sequence}. \end{definition} \bigskip \subsection{Examples} 1) The Prouhet-Thue-Morse sequence \medskip This sequence has been studied by Thue at the beginning of the century, to give an example of a binary sequence without cubes (i. e. without three consecutive identical blocks, see \cite{Thue1} and \cite{Thue2}), by Morse in the 20's, (see \cite{Morse}), but also by Prouhet in 1851 (\cite{Prouhet}). It can be defined by the following $2$-automaton : \medskip - the set of states is $S = \{i, a \}$, - the maps $0$ and $1$ from $S$ to $S$ are defined by, $$0.i = i, \, 0.a = a,$$ $$1.i = a, \, 1.a = i,$$ - the output function is defined by, $$\varphi(i) = 0, \, \varphi(a) = 1.$$ Hence this sequence begins by: $$0 \, 1 \, 1 \, 0 \, 1 \, 0 \, 0 \, 1 \, 1 \, 0 \, 0 \, 1 \, \cdots$$ \newpage \begin{figure}[h] \setlength{\unitlength}{0.02in}% \begin{picture}(187,64)(220,530) \thicklines \put(300,600){\circle{20}} \put(400,600){\circle{20}} \put(320,610){\oval(40,40)[tl]} \put(380,610){\oval(40,40)[tr]} \put(320,630){\vector(1,0){34}} \put(350,630){\line(1,0){30}} \put(320,590){\oval(40,40)[bl]} \put(380,590){\oval(40,40)[rb]} \put(318,570){\line(1,0){40}} \put(380,570){\vector(-1,0){32}} \put(291,600){\oval(30,15)[l]} \put(409,600){\oval(30,15)[r]} \put(350,634){$1$} \put(350,560){$1$} \put(298,598){i} \put(398,598){a} \put(269,598){0} \put(428,598){0} \put(324,540){$\varphi(i) = 0, \, \varphi(a)=1$} \end{picture} \caption{An automaton which generates the Prouhet-Thue-Morse sequence} \end{figure} \bigskip \noindent 2) The Rudin-Shapiro sequence \medskip Let $a = (a_n)_{n \geq 0}$ be any sequence of $\pm 1$. What can be said of the asymptotic size of the supremum of its Fourier transform $$F_N(a) = \sup_{x \in [0, 1]}\mid \sum_{n=0}^{N-1} a_n e^{2i\pi n x} \mid?$$ The following bounds are trivial: $$\sqrt{N} = \parallel \sum_{n=0}^{N-1} a_n e^{2i\pi n x} \parallel_{L^2} \leq \parallel \sum_{n=0}^{N-1} a_n e^{2i\pi n x} \parallel_{L^{\infty}} = F_N(a) \leq N.$$ On the other hand, for almost all (in the sense of the Haar measure on $\{-1, +1\}^{\scriptsize \GN}$) sequences of $\pm 1$, one has $$F_N(a) \leq \sqrt{N \log N}.$$ In other words, for a ``random" sequence $a$, $F_N(a)$ behaves roughly like $\sqrt{N}$. Shapiro in 1951 (\cite{Shapiro}) and Rudin in 1959 (\cite{Rudin}) constructed a sequence $a$ for which $F_N(a) \leq C \sqrt{N}$ and which is {\em deterministic} for any reasonable definition of this notion. Moreover this sequence is $2$-automatic, and can be generated by the following $2$-automaton: \medskip - set of states $S = \{i, a, b, c \}$, - maps from $S$ to $S$, $$0.i = i, \, 0.a = i, \, 0.b = c, \, 0.c = c,$$ $$1.i = a, \, 1.a = b, \, 1.b = a, \, 1.c = b,$$ - output function, $$\varphi(i) = \varphi(a) = +1,$$ $$\varphi(b) = \varphi(c) = -1.$$ \medskip \noindent Hence this sequence begins by: $$+1 \, +1 \, +1 \, -1 \, +1 \, +1 \, -1 \, +1 \, +1 \, \cdots$$ \bigskip \begin{figure}[h] \setlength{\unitlength}{0.012in}% \begin{picture}(187,104)(240,530) \thicklines \multiput(300,600)(100,0){4}{\circle{20}} \multiput(320,610)(100,0){3}{\oval(40,40)[tl]} \multiput(380,610)(100,0){3}{\oval(40,40)[tr]} \multiput(320,630)(100,0){3}{\vector(1,0){30}} \multiput(350,630)(100,0){3}{\line(1,0){30}} \multiput(320,590)(100,0){3}{\oval(40,40)[bl]} \multiput(380,590)(100,0){3}{\oval(40,40)[rb]} \multiput(320,570)(100,0){3}{\line(1,0){30}} \multiput(380,570)(100,0){3}{\vector(-1,0){30}} \put(291,600){\oval(30,15)[l]} \put(609,600){\oval(30,15)[r]} \put(350,634){$1$} \put(350,556){$0$} \put(450,634){$1$} \put(450,556){$1$} \put(550,634){$0$} \put(550,556){$1$} \put(298,597){i} \put(397,597){a} \put(497,596){b} \put(597,597){c} \put(266,596){$0$} \put(628,596){$0$} \put(352,530){$\varphi(i) = \varphi(a) = +1, \, \varphi(b) = \varphi(c) = -1$} \end{picture} \caption{An automaton which generates the Rudin-Shapiro sequence} \end{figure} \bigskip \noindent 3) The paperfolding sequence \medskip Folding repeatedly a sheet of paper yields a sequence of ``peaks" $\Lambda$ and ``valleys" V which has been studied by many authors since the paper of Davis and Knuth (\cite{Davis}). This sequence can indeed be generated by the following $2$-automaton: \medskip - set of states $S = \{i, a, b, c \}$, - maps from $S$ to $S$, $$0.i = a, \, 0.a = b, \, 0.b = b, \, 0.c = c,$$ $$1.i = i, \, 1.a = c, \, 1.b = b, \, 1.c = c,$$ - output function, $$\varphi(i) = \varphi(a) = \varphi(b) = \mbox{\rm V}, \, \varphi(c) = \Lambda.$$ \medskip \noindent Hence this sequence begins by: $$\mbox{\rm V} \, \mbox{\rm V} \, \Lambda \, \mbox{\rm V} \, \mbox{\rm V} \, \Lambda \, \Lambda \, \mbox{\rm V} \, \cdots$$ \newpage \begin{figure}[h] \setlength{\unitlength}{0.016in}% \begin{picture}(187,64)(240,540) \thicklines \put(300,600){\circle{20}} \put(400,600){\circle{20}} \put(311,600){\line(1,0){79}} \put(311,600){\vector(1,0){44}} \put(500,650){\circle{20}} \put(500,550){\circle{20}} \put(508,650){\oval(34,15)[r]} \put(509,650){\oval(20,8)[r]} \put(520,648){$\scriptstyle 0$} \put(526,648){$\scriptstyle 1$} \put(508,550){\oval(34,15)[r]} \put(509,550){\oval(20,8)[r]} \put(520,548){$\scriptstyle 0$} \put(526,548){$\scriptstyle 1$} \put(291,600){\oval(30,15)[l]} \put(272,598){$\scriptstyle 1$} \put(408.92,604.46){\line(2,1){82}} \put(408.92,604.46){\vector(2,1){47}} \put(408.92,595.54){\line(2,-1){82}} \put(408.92,595.54){\vector(2,-1){47}} \put(350,603){$\scriptstyle 0$} \put(450,629){$\scriptstyle 0$} \put(450,579){$\scriptstyle 1$} \put(298,598){i} \put(398,598){a} \put(498,648){b} \put(498,548){c} \put(300,540){$\varphi(i) = \varphi(a) = \varphi(b) = \mbox{\rm V}, \, \varphi(c) = \Lambda$} \end{picture} \caption{An automaton which generates the paperfolding sequence} \end{figure} \bigskip \noindent 4) The Baum-Sweet sequence \medskip It is well known that, if a real number is quadratic over the rationals, then its continued fraction expansion is periodic or ultimately periodic. But nothing is known for algebraic numbers of degree $\geq 3$: no example is known with bounded partial quotients, nor with unbounded quotients. If one replaces the real numbers by the field of Laurent series $\GF_q((X^{-1}))$ over the finite field $\GF_q$, the field of rational numbers by $\GF_q(X)$, and the ring of integers $\GZ$ by the ring of polynomials $\GF_q[X]$, more is known. There is indeed a theory of continued fractions, and the property of bounded partial quotients has to be replaced by the property of quotients of bounded degree (or equivalently quotients taking a finite number of values). A first result has been given by Baum and Sweet in 1976 (\cite{BaumSweet}): {\em there exists a Laurent series in} $\GF_2((X^{-1}))$, {\em of degree $3$ over } $\GF_2(X)$, {\em such that its continued fraction has only finitely many partial quotients}. By the Christol, Kamae, Mend\`es France and Rauzy theorem, (where the variable $X$ is replaced by $X^{-1}$), the sequence of coefficients of the Baum-Sweet series is $2$-automatic. Here is a $2$-automaton which generates this sequence: \medskip - set of states $S = \{i, a, b \}$, - maps from $S$ to $S$, $$0.i = a, \, 0.a = i, \, 0.b = b,$$ $$1.i = i, \, 1.a = b, \, 1.b = b,$$ - output function, $$\varphi(i) = 1, \, \varphi(a) = \varphi(b) = 0.$$ \medskip \noindent Hence this sequence begins by: $$1 \, 1 \, 0 \, 1 \, 1 \, 0 \, 0 \, 1 \, 0 \, \cdots$$ \newpage \begin{figure}[h] \setlength{\unitlength}{0.015in}% \begin{picture}(187,94)(220,532) \thicklines \put(300,600){\circle{20}} \put(400,600){\circle{20}} \put(500,600){\circle{20}} \put(320,610){\oval(40,40)[tl]} \put(380,610){\oval(40,40)[tr]} \put(320,630){\vector(1,0){34}} \put(350,630){\line(1,0){30}} \put(320,590){\oval(40,40)[bl]} \put(380,590){\oval(40,40)[rb]} \put(318,570){\line(1,0){40}} \put(380,570){\vector(-1,0){32}} \put(293,600){\oval(35,15)[l]} \put(506,600){\oval(35,15)[r]} \put(509,600){\oval(15,8)[r]} \put(410,600){\vector(1,0){45}} \put(450,600){\line(1,0){40}} \put(350,634){$\scriptstyle 0$} \put(350,560){$\scriptstyle 0$} \put(450,604){$\scriptstyle 1$} \put(299,597){i} \put(398,598){a} \put(497.5,597){b} \put(270,598){$\scriptstyle 1$} \put(525,598){$\scriptstyle 1$} \put(518,598){$\scriptstyle 0$} \put(300,540){$\varphi(i) = 1, \, \varphi(a) = \varphi(b) = 0$} \end{picture} \caption{An automaton which generates the Baum-Sweet sequence} \end{figure} \bigskip It can be shown that the term $u_n$ of the Baum-Sweet sequence $u$ is equal to $1$ if and only if there is no string of $0$'s of odd length in the binary expansion of $n$. Other examples have been given by Mills and Robbins for all characteristics (\cite{MillsRobbins}). A natural question due to Mend\`es France arises: given an algebraic Laurent series whose partial quotients take only a finite number of values, is the sequence of these partial quotients automatic? (remember that the sequence of coefficients of the series is itself automatic from the Christol, Kamae, Mend\`es France and Rauzy theorem). The answer is yes for the example of Mills and Robbins in characteristic 3, (see \cite{AlloucheBetremaShallit}), and for their examples in characteristic $p \geq 3$, (see \cite{Allouchefc}). The sequence of partial quotients of the Baum-Sweet series has recently been shown non-automatic by Mkaouar, \cite{Mkaouar}, but this sequence can be generated by a non-uniform morphism, see below. \bigskip \noindent 5) The Hanoi sequence \medskip The well known towers of Hanoi game is the following: $N$ disks of diameter, say $1$, $2$, $\cdots$, $N$, are stacked on the first of three vertical pegs. At each step one is allowed to pick the topmost disk on a peg and to put it on another one, provided it is not stacked on a smaller disk. The game is over when all the disks are on a (new) peg. A classical recursive algorithm gives a (finite) sequence of moves of length $2^N -1$, which is optimal, to transfer $N$ disks from the first peg to another one. If one chooses to transfer the disks to the second peg if $N$ is odd, and to the third one if $N$ is even, all the sequences of moves of length $2^N-1$ given by the algorithm are prefixes of a unique infinite sequence of moves on the six-letter alphabet of all possible moves. It has been proved in \cite{AlloucheDress} that this infinite sequence is indeed $2$-automatic, and that it can be generated by the $2$-automaton given below. Note that in the cyclic towers of Hanoi, (where the pegs are on a circle and where only clockwise moves are allowed), the infinite sequence of moves resulting from the classical cyclic algorithm is NOT automatic, but can be generated by a non-uniform morphism, (see \cite{AlloucheHanoicyclique}). \begin{figure}[h] \setlength{\unitlength}{0.0066in}% \begin{picture}(500,693)(140,360) \thicklines %******************************************** \put(210,700){\circle{30}} \put(405,765){\circle{30}} %******************************************** \put(600,830){\circle{30}} \put(596,826){\scriptsize $\overline{\rm c}$} \put(650,916){\circle{30}} \put(646,912){\scriptsize $\overline{\rm c}$} \put(750,916){\circle{30}} \put(746,912){\scriptsize $\overline{\rm a}$} \put(800,830){\circle{30}} \put(796,826){\scriptsize $\overline{\rm a}$} \put(750,744){\circle{30}} \put(746,739){\scriptsize $\overline{\rm b}$} \put(650,744){\circle{30}} \put(646,739){\scriptsize $\overline{\rm b}$} %******************************************** \put(600,570){\circle{30}} \put(596,567){\scriptsize a} \put(650,484){\circle{30}} \put(646,481){\scriptsize a} \put(750,484){\circle{30}} \put(746,481){\scriptsize c} \put(800,570){\circle{30}} \put(796,567){\scriptsize c} \put(750,656){\circle{30}} \put(746,652){\scriptsize b} \put(650,656){\circle{30}} \put(646,652){\scriptsize b} %******************************************** \put(220,708){\vector(3,1){90}} \put(220,708){\line(3,1){171}} \put(296,742){\scriptsize $0$} \put(394,757){\vector(-3,-1){90}} \put(394,757){\line(-3,-1){170}} \put(308,712){\scriptsize $0$} \put(419,765){\vector(3,1){90}} \put(419,765){\line(3,1){170}} \put(497,799){\scriptsize $1$} %******************************** %******************************** \put(612,835){\line(3,5){40}} \put(626,860){\vector(-1,-1){0}} \put(600,844){\line(3,5){38}} \put(624,880){\vector(1,1){0}} \put(638,860){\scriptsize $0$} \put(610,880){\scriptsize $0$} %******************************** \put(662,909){\line(1,0){75}} \put(693,909){\vector(-1,0){0}} \put(662,923){\line(1,0){75}} \put(706.8,923){\vector(1,0){0}} \put(697,892){\scriptsize $1$} \put(697,929){\scriptsize $1$} %******************************** \put(762,911){\line(3,-5){40}} \put(787,871){\vector(1,-1){0}} \put(750,902){\line(3,-5){37}} \put(765,877){\vector(-1,1){0}} \put(788,880){\scriptsize $0$} \put(760,856){\scriptsize $0$} %******************************** \put(762,749){\line(3,5){40}} \put(776,774){\vector(-1,-1){0}} \put(750,758){\line(3,5){38}} \put(774,794){\vector(1,1){0}} \put(788,774){\scriptsize $1$} \put(760,794){\scriptsize $1$} %******************************** \put(662,737){\line(1,0){75}} \put(693,737){\vector(-1,0){0}} \put(662,751){\line(1,0){75}} \put(706.8,751){\vector(1,0){0}} \put(697,720){\scriptsize $0$} \put(697,757){\scriptsize $0$} %******************************** \put(612,825){\line(3,-5){40}} \put(637,785){\vector(1,-1){0}} \put(600,816){\line(3,-5){37}} \put(615,791){\vector(-1,1){0}} \put(638,794){\scriptsize $1$} \put(610,770){\scriptsize $1$} %******************************** %******************************** \put(612,575){\line(3,5){40}} \put(626,600){\vector(-1,-1){0}} \put(600,584){\line(3,5){38}} \put(624,620){\vector(1,1){0}} \put(638,600){\scriptsize $1$} \put(610,620){\scriptsize $1$} %******************************** \put(662,649){\line(1,0){75}} \put(693,649){\vector(-1,0){0}} \put(662,663){\line(1,0){75}} \put(706.8,663){\vector(1,0){0}} \put(697,632){\scriptsize $0$} \put(697,669){\scriptsize $0$} %******************************** \put(762,651){\line(3,-5){40}} \put(787,611){\vector(1,-1){0}} \put(750,642){\line(3,-5){37}} \put(765,617){\vector(-1,1){0}} \put(788,620){\scriptsize $1$} \put(760,596){\scriptsize $1$} %******************************** \put(762,489){\line(3,5){40}} \put(776,514){\vector(-1,-1){0}} \put(750,498){\line(3,5){38}} \put(774,534){\vector(1,1){0}} \put(788,514){\scriptsize $0$} \put(760,534){\scriptsize $0$} %******************************** \put(662,477){\line(1,0){75}} \put(693,477){\vector(-1,0){0}} \put(662,491){\line(1,0){75}} \put(706.8,491){\vector(1,0){0}} \put(697,460){\scriptsize $1$} \put(697,497){\scriptsize $1$} %******************************** \put(612,565){\line(3,-5){40}} \put(637,525){\vector(1,-1){0}} \put(600,556){\line(3,-5){37}} \put(615,531){\vector(-1,1){0}} \put(638,534){\scriptsize $0$} \put(610,510){\scriptsize $0$} %******************************** %******************************** \put(224,700){\line(3,-1){365}} \put(224,700){\vector(3,-1){188}} \put(400,624){\scriptsize $1$} %******************************** \put(180,380){(The - significant - states have been replaced by their images by $\varphi$)} \end{picture} \caption{An automaton which generates the Hanoi sequence} \end{figure} \bigskip \subsection{Sequences generated by uniform morphisms} \begin{definition} A sequence $u = (u_n)_{n \geq 0}$ with values in a finite set $Y$ is said to be the image of a fixed point of a uniform morphism of length $q$, ($q$ being an integer $\geq 2$), if there exists: - a set $A$, - a uniform morphism $\sigma$ of length $q$ on $A$, i. e. a map which associates to each letter in $A$ a $q$-letter word on $A$. This map is extended by concatenation to a morphism of the free monoid $A^*$ generated by $A$, and by continuity to the infinite sequences with values in $A$, - a sequence $v = (v_n)_{n \geq 0}$ with values in $A$, which is a fixed point of $\sigma$, - a map $\psi$ from $A$ to $Y$ such that $\forall n \in \, $\mbox{\em \GN, } $\psi(v_n) = u_n$. \end{definition} \bigskip \subsection{Examples} The patient reader can check (or prove) that the five examples given previously are images of fixed points of uniform morphisms of length $2$, indeed: \bigskip \noindent 1) The Prouhet-Thue-Morse sequence \medskip This sequence is the fixed point of the $2$-morphism on $\{0, 1\}$ given by: $$\begin{array}{lll} \sigma(0) & = & 01, \\ \sigma(1) & = & 10. \end{array} $$ \bigskip \noindent 2) The Rudin-Shapiro sequence \medskip Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by: $$ \begin{array}{lll} \sigma (a) & = & ab, \\ \sigma (b) & = & ac, \\ \sigma (c) & = & db, \\ \sigma (d) & = & dc, \end{array} $$ and let $\psi$ be the map: $$\psi(a) = \psi(b) = +1, \, \psi(c) = \psi(d) = -1.$$ Then the sequence $v = (v_n)_{n \geq 0}$ defined by $v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of $\sigma$, and the Rudin-Shapiro sequence is the pointwise image of the sequence $v$ by the map $\psi$. \newpage \noindent 3) The paperfolding sequence \medskip Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by: $$\begin{array}{lll} \sigma (a) & = & ab, \\ \sigma (b) & = & cb, \\ \sigma (c) & = & ad, \\ \sigma (d) & = & cd, \end{array} $$ and let $\psi$ be the map: $$\psi(a) = \psi(b) = \mbox{\rm V}, \, \psi(c) = \psi(d) = \Lambda.$$ Then the sequence $v = (v_n)_{n \geq 0}$ defined by $v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of $\sigma$, and the paperfolding sequence is the pointwise image of the sequence $v$ by the map $\psi$. \bigskip \noindent 4) The Baum-Sweet sequence \medskip Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by: $$\begin{array}{lll} \sigma (a) & = & ab, \\ \sigma (b) & = & cb, \\ \sigma (c) & = & bd, \\ \sigma (d) & = & dd, \end{array} $$ and let $\psi$ be the map: $$\psi(a) = \psi(b) = 1, \, \psi(c) = \psi(d) = 0.$$ Then the sequence $v = (v_n)_{n \geq 0}$ defined by $v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of $\sigma$, and the Baum-Sweet sequence is the pointwise image of the sequence $v$ by the map $\psi$. \bigskip \noindent 5) The Hanoi sequence \medskip This sequence is the fixed point of the $2$-morphism $\sigma$ defined on the alphabet $A = \{a, b, c, \overline{a}, \overline{b}, \overline{c}\}$ by: $$\begin{array}{lll} \sigma(a) & = & a \overline{c}, \\ \sigma(b) & = & c \overline{b}, \\ \sigma(c) & = & b \overline{a}, \\ \sigma(\overline{a}) & = & a c, \\ \sigma(\overline{b}) & = & c b, \\ \sigma(\overline{c}) & = & b a. \end{array} $$ \bigskip \subsection{The main theorem} It is not by chance that our five examples are simultaneously $2$-automatic and images of fixed points of uniform morphisms of length $2$. Indeed a theorem due to Cobham, \cite{Cobham1}, asserts that this is general: \begin{theorem} {\em (\cite{Cobham1})}. A sequence is $q$-automatic if and only if it is the image of a fixed point of a $q$-substitution. \end{theorem} \bigskip The proof of this theorem uses a combinatorial property of these sequences: both properties above are equivalent to saying that the set of subsequences $N_q(u)$ defined by: $$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \, 0 \leq a \leq q^k-1J\right \},$$ (also called the $q$-kernel of the sequence $u$, see \cite{Salon2}), is finite. \bigskip Christol, Kamae, Mend\`es France and Rauzy, gave in 1980, \cite{CKMFR}, an arithmetical condition which is equivalent to the theo\-re\-tical-com\-pu\-ter-science condition and to the combinatorial condition given above: \begin{theorem} {\em (\cite{CKMFR})}. Let $u$ be a sequence with values in the finite field {\em \GF}$_q$, ($q$ is a power of a prime number $p$). Then the sequence $u$ is $q$-automatic if and only if the formal power series $\sum_{n = 0}^{+ \infty} u_n X^n$ is algebraic over the field {\em \GF}$_q(X)$ of rational functions with coefficients in {\em \GF}$_q$. \end{theorem} \bigskip \noindent {\bf Remarks} \medskip - this theorem has, of course, nothing to do with the Chomsky-Sch\"utzen\-berger theorem, (\cite{Chomsky}); \medskip - to give the flavour of this theorem, let us consider again the Prouhet-Thue-Morse sequence quoted above. Remember that this sequence is the fixed point of the $2$-morphism $\sigma$ defined by: $$\begin{array}{lll} \sigma(0) & = & 01, \\ \sigma(1) & = & 10. \end{array} $$ We consider from now on $0$ and $1$ as the two elements of \GF$_2$ and we make all computations modulo $2$. The definition of our sequence $u$ by the morphism $\sigma$ shows that: $$\forall n \in \GN, \, u_{2n} = u_n, \, u_{2n+1} = 1+u_n.$$ Hence: \begin{eqnarray*} F(X) & := & \sum_{n = 0}^{+ \infty}u_nX^n = \sum_{n = 0}^{+ \infty} u_{2n}X^{2n} + \sum_{n = 0}^{+ \infty} u_{2n+1}X^{2n+1} \\ &\, = & \sum_{n = 0}^{+ \infty} u_nX^{2n} + \sum_{n = 0}^{+ \infty} (1+u_{n})X^{2n+1} \\ &\, = & (\sum_{n = 0}^{+ \infty} u_nX^n)^2 + X(\sum_{n = 0}^{+ \infty} u_{n}X^n)^2 + \frac{X} {(1+X)^2} \\ &\, = & F^2(X) + XF^2(X) + \frac{X}{(1+X)^2}. \end{eqnarray*} One sees that $F$ satisfies the equation: $$(1+X)^3F^2 + (1+X)^2F + X = 0,$$ which shows that $F$ is algebraic (quadratic) on $\GF_2(X)$. \bigskip Another condition can be given for the automaticity of a sequence with values in a finite field. This is a theorem of Furstenberg's, which he proved in 1967, \cite{Furstenberg}: \begin{theorem} {\em \cite{Furstenberg}.} Let $u = (u_n)_{n \geq 0}$ be a sequence with values in the finite field {\em \GF}$_q$. Then the series $\sum u_n X^n$ is algebraic over the field {\em \GF}$_q(X)$ if and only if there exists a double formal power series $\sum_{m, n \geq 0} a_{m, n} X^m Y^n$ such that - this series is a rational function, i. e. belongs to the field {\em \GF}$_q(X, Y)$, - the sequence $u$ is the diagonal of the sequence $a$, i. e. : $\forall n \in \,$ {\em \GN}, $u_n = a_{n,n}$. \end{theorem} Putting all these conditions together one obtains the following fundamental theorem: \bigskip \noindent {\bf Fundamental Theorem} {\em Let $u = (u_n)_{n \geq 0}$ be a sequence with values in the finite field {\em \GF}$_q$. Then the following conditions are equivalent: i) the $q$-kernel of the sequence $u$, i. e. the set of subsequences $$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \, 0 \leq a \leq q^k-1J\right \},$$ is finite, ii) the sequence $u$ is $q$-automatic, iii) the sequence $u$ is the image of a fixed point of a uniform morphism of length $q$, iv) the formal power series $\sum_{n=0}^{+ \infty} u_n X^n$ is algebraic over the field {\em \GF}$_q(X)$, v) there exists a double sequence $a = (a_{m, n})_{m,n}$ with values in {\em \GF}$_q$ such that the formal power series $\sum_{m, n \geq 0} a_{m, n} X^m Y^n$ is a rational function, (i. e. an element of {\em \GF}$_q(X,Y)$), and such that $u$ is the diagonal of $a$, (i. e. $\forall n \in \,${\em \GN}, $u_n = a_{n, n}$)}. \bigskip \section{Transcendence results and finite automata} In this chapter we will see two kinds of transcendence results: - transcendence over $\GF_q(X)$ of formal power series with coefficients in $\GF_q$, using the Christol, Kamae, Mend\`es France and Rauzy theorem. In particular we will devote a paragraph to the Carlitz zeta function. - transcendence of real numbers over the rational numbers. \subsection{Miscellaneous transcendental formal power series} - An old question of Mahler's asks whether a binary sequence $(a_n)_n$ such that both numbers $\sum_{n=0}^{+ \infty} a_n 2^{-n}$ and $\sum_{n=0}^{+ \infty} a_n 3^{-n}$ are algebraic over the rational numbers is necessary an ultimately periodic sequence, (i. e. whether both numbers are ``trivial", indeed whether they are both rational). Actually, although this question is still open, the result is true if one replaces the usual operations by operations without carries: \begin{theorem} Let $(a_n)_n$ be a binary sequence such that the formal power series $\sum_{n=0}^{+ \infty} a_n X^n$ is algebraic over {\em \GF}$_2(X)$ when considered as an element of {\em \GF}$_2[[X]]$, and algebraic over {\em \GF}$_3(X)$ when considered as an element of {\em \GF}$_3[[X]]$. Then this sequence is ultimately periodic, i. e. both formal power series are indeed rational functions. \end{theorem} The proof of this result is an easy consequence of the theorem of Christol, Kamae, Mend\`es France and Rauzy and of a (non-easy!) result of Cobham which asserts that a sequence which is both $q$-automatic and $q'$-automatic, with $q$ and $q'$ multiplicatively independent, is necessary ultimately periodic, (\cite{Cobham2}). \bigskip \noindent - Let $s_q(n)$ be the residue modulo $q$ of the sum of the digits of the integer $n$ in its $q$-ary expansion. It is not hard to see that the sequence $(s_q(an+b))_n$ is $q$-automatic; in particular for $q = 2$, $a=1$, $b=0$, one gets the Prouhet-Thue-Morse sequence. But what can be said of $(s_q(n^2))$? A result of the author (\cite{Allouchesomme}), states that this sequence is NOT $q$-automatic. \begin{theorem} {\em \cite{Allouchesomme}.} Let $P$ be a polynomial of degree $\geq 2$, such that $P(${\em \GN}$) \subset \,${\em \GN}. Then the sequence $(s_q(P(n))_n$ is not $q$-automatic. Hence, if $q$ is a prime number, the formal power series $\sum s_q(P(n)) X^n$ is transcendental over {\em \GF}$_q(X)$. \end{theorem} \noindent - As seen previously, the paperfolding sequence is $2$-automatic, hence the paperfolding series is algebraic over $\GF_2(X)$. Now suppose that at each step you choose to fold either up or down arbitrarily; you thus obtain an uncountable number of paperfolding sequences. Of course they cannot be all automatic, as the set of automatic sequences is countable. It can be shown that such a sequence is $2$-automatic if and only if the sequence of its ``folding instructions" (i. e. the sequence of choices to fold one way or the other way) is ultimately periodic: in other words any non-ultimately periodic sequence of folding instructions yields a formal power series which is transcendental over $\GF_2(X)$. \subsection{The Carlitz zeta function} In 1935 Carlitz introduced a function now known as the Carlitz zeta function which ressembles the Riemann zeta function (see for instance \cite{Carlitz}). This function from $\GN^*$ to $\GF_q[[X^{-1}]]$ is defined by: $$\forall n \in \GN^*, \, \zeta(n) = \sum_{P \mbox{ \rm\scriptsize monic }\in \, \mbox{\scriptsize \GF}_q[X]} \frac{1}{P^n}.$$ Moreover there exists a formal Laurent series denoted by $\Pi$ such that: $$\forall n \equiv 0 \bmod{(q-1)}, \, n \neq 0, \, \exists r_n \in \GF_q(X), \, \zeta(n) = \Pi^n r_n.$$ The expression for $\Pi$ is: $$\Pi = \prod_{j=1}^{+ \infty} \left ( 1 - \frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right ).$$ Note that this property can be compared to the classical result on the values of the Riemann zeta function at the even integers. \medskip One can ask whether this formal Laurent series $\Pi$, the values of this zeta function, and the values $\frac{\zeta(n)}{\Pi^n}$ are transcendental over $\GF_q(X)$. Remember that the real number $\pi$ is transcendental over the field of rational numbers, hence the values of the Riemann zeta function at the even integers are also transcendental, as the numbers $\zeta(2n)/\pi^{2n}$ are rational. For the other values of the Riemann zeta function, (divided by a suitable power of $\pi$ or not), the only thing which is known is the irrationality of $\zeta(3)$ proved by Ap\'ery in 1978. Four methods are available for the Carlitz zeta function and the related series: - the original method due to Wade in the 40's, (he proved many transcendence results, in particular {\em the transcendence of the formal power series $\Pi$}), ressembles transcendence methods for the case of real numbers. This method has been extended recently by Dammame and Hellegouarch, who proved the {\em transcendence of all the values $\zeta(n)$, $\forall n \in$ {\em \GN}$^*$}; - the method of diophantine approximation is worked out by de Mathan and Ch\'erif and gives {\em irrationality measures for the values of the Carlitz zeta function}; - the method of Yu uses Drinfeld modules and gives the most complete results, indeed {\em $\zeta(n)$ is transcendental $\forall n \in $ {\em \GN}$^*$ and $\frac{\zeta(n)}{\Pi^n}$ is transcendental for every $n \not\equiv 0 \bmod{(q-1)}$}; - the ``automatic method". This method has been proposed by the author to give {\em an ``elementary" proof of the transcendence of the formal series $\Pi$}, (see \cite{AllouchePi}). The reader will find in the appendix a different (but even simpler) proof of the transcendence of this series $\Pi$. This ``automatic" method has been recently extended by Berth\'e: she gave an elementary automatic proof of {\em the transcendence of $\zeta(n)$, $\forall n \leq q-2$}, (see \cite{Berthe1}), as well as {\em linear independence results for these series}, (\cite{Berthe2}), and {\em transcendence results for the Carlitz logarithm}, (see \cite{Berthe3}). \subsection{Transcendence of real numbers and finite automata} The consequence of Cobham's theorem quoted above (Theorem 4) can be described, roughly speaking, by saying: {\em ``changing bases kills algebraicity"}. Hence a natural question posed in \cite{CKMFR} asks whether every real number $\sum a_n 2^{-n}$ such that the sequence of coefficients in its base-2 expansion is $2$-automatic and not ultimately periodic is indeed a transcendental number. The answer is yes, it is due to Loxton and van der Poorten, (see also the work of Nishioka): \begin{theorem} {\em \cite{LoxtonvdP}}. If the coefficients of the base-$q$ expansion of a real number form an automatic sequence, then this number is either rational or transcendental. \end{theorem} In other words a number like $\sqrt 2$ cannot have an automatic expansion in any base. Note that this theorem gives the transcendence of a countable set of ``ad hoc" real numbers, and that one should not hope to get that way the transcendence of classical numbers like the Euler constant (!), even for numbers which are known to be transcendental: a reasonable but out of reach conjecture is that the real numbers $\pi$ and $e$ are not automatic. Note also that Mend\`es France and van der Poorten proved that a real number whose base-2 expansion is any paperfolding sequence is transcendental, (see \cite{MendesvdP}), this gives an uncountable (but ``thin") set of numbers, (which of course are not all automatic numbers), for which the transcendence can be proved using this kind of methods. \section{Generalizations} In this chapter we will survey quickly some possible generalizations of the automatic sequences. The interested reader can find a survey with more details in \cite{AlloucheLNCS}, in particular what is kept and what is lost in each of these generalizations. \subsection{The multidimensional case} Instead of considering one-dimensional morphisms which consist of replacing a letter by a word, one can imagine of a multidimensional morphism. Thus a two-dimensional morphism associates to each letter a ``square", for instance: $$ 0 \rightarrow \begin{array}{ll} 0 & 1 \\ 1 & 0 \end{array}, \quad 1 \rightarrow \begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}. $$ This can be extended as previously, iterating this map gives: $$0 \rightarrow \begin{array}{ll} 0 & 1 \\ 1 & 0 \end{array} \rightarrow \begin{array}{llll} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array} \rightarrow \cdots $$ The reader can find in \cite{Salon1} and \cite{Salon2} more details, in particular a theorem analogous to the Christol, Kamae, Mend\`es France and Rauzy theorem holds true. \subsection{Non-uniform morphisms} A non-uniform morphism maps each letter of a finite alphabet on a word with letters in this alphabet, but all these words do not have necessarily the same length. A classical example is the Fibonacci morphism defined on $\{0, 1\}$ by: $$0 \rightarrow 01, \, \, 1 \rightarrow 0.$$ Iterating this morphism gives: $$0 \rightarrow 01 \rightarrow 010 \rightarrow 01001 \rightarrow 01001010 \rightarrow \cdots$$ The arithmetic properties of the infinite sequences which are (images of) fixed points of these morphisms are not very simple as the numeration base associated to them is not the base $q$ for some integer $q \geq 2$. For instance, in the above example, the numeration base is the Fibonacci base: $F_0 = 1$, $F_1=2$, $F_2=3$, $F_3=5$, $\cdots$ On this subject one can read the paper of Shallit (\cite{Shallit}), and also the work of Fabre. \subsection{From finite fields to fields of positive characteristic} Remember that the theorem of Christol, Kamae, Mend\`es France and Rauzy can be stated in the following way, (see theorem 2): \medskip {\em Let $q$ be an integer $\geq 2$. For a sequence $u=(u_n)_n$ define its $q$-kernel as the set of subsequences $$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \, 0 \leq a \leq q^k-1 \right \}.$$ Suppose that $u$ takes its values in the finite field {\em \GF}$_q$. Then the series $\sum u_n X^n$ is algebraic over {\em \GF}$_q(X)$ if and only if its $q$-kernel $N_q(u)$ is finite}. \medskip \noindent The main result obtained by Sharif and Woodcock in \cite{SharifWoodcock} and Harase in \cite{Harase} (see also the survey of the author \cite{AlloucheSW}), can be stated as follows: \begin{theorem} {\em \cite{SharifWoodcock}, \cite{Harase}}. Let $u$ be a sequence with values in a field $K$ of positive characteristic $p$. Let $s$ be any integer $\geq 1$, $q=p^s$, and let $\overline{K}$ be a perfect field containing $K$, (for instance its algebraic closure). Then the series $\sum u_n X^n$ is algebraic over $K(X)$ if and only if the vector space spanned over $\overline{K}$ by the ``modified" $q$-kernel of $u$ $$N_q'(u) = \left \{ n \rightarrow u_{q^k n + a}^{1/q^k}, \, k \geq 0, \, 0 \leq a \leq q^k-1J\right \}.$$ has finite dimension. \end{theorem} Note that this theorem contains the Christol, Kamae, Mend\`es France and Rauzy theorem, and that it can be easily extended to the multidimensional case. Note also that two interesting corollaries can been proved, using the work of Salon for a finite field, or more generally the above theorem for a field of positive characteristic, (these results have been first given by Deligne by a non-elementary method in \cite{Deligne}): \medskip - {\em the Hadamard product of two algebraic formal power series with coefficients in a field of positive characteristic, $\sum u_n X^n$ and $\sum v_n X^n$, i. e. the ``naive" product $\sum u_n v_n X^n$, is itself an algebraic formal power series}. \medskip - {\em let $\sum u_{m,n}X^m Y^n$ be a double formal power series in $K[[X,Y]]$, algebraic over $K(X,Y)$, (where $K$ is a field of positive characteristic). Then its diagonal $\sum u_{n,n}X^n$ is algebraic over the field $K(X)$}. \subsection{$q$-regular sequences} Let $s(n)$ be the sum of the digits of $n$ in the binary expansion, then the sequence $(s(n))_n \bmod 2$ is the Prouhet-Thue-Morse sequence, hence is a $2$-automatic sequence. What can be said of the sequence $(s(n))_n$ not reduced modulo $2$? The notion of $q$-regular sequence has been introduced by Shallit and the author in \cite{AlloucheShallit} to answer this question {\em inter alia}. \medskip {\em Let $q$ be an integer $\geq 2$. Let $u=(u_n)_n$ be a sequence with values in a N{\oe}therian ring $R$. This sequence is said to be $q$-regular if its kernel $N_q(u)$ generates a module of finite type}. \noindent (Remember that the $q$-kernel of the sequence $u$ is defined as: $N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \, 0 \leq a \leq q^k-1J\right \}$). \medskip The reader is referred to \cite{AlloucheShallit} for the properties of these sequences and for numerous examples of such sequences, together with ``their Sloane numbers" for the sequences which are quoted in Sloane's book \cite{Sloane}. \section{Appendix: an easy ``automatic" proof of the transcendence of the formal power series $\Pi$} As said in chapter 3.2 the Carlitz formal power series $\Pi$, given by $$\Pi = \prod_{j=1}^{+ \infty} \left ( 1 - \frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right ).$$ has been proved transcendental by Wade in the 40's. We gave an ``automatic" proof of this result in \cite{AllouchePi}. We want to present now another - still simpler - ``automatic" proof. \medskip The first step consists of a remark due to Laurent Denis concerning an expression for $\frac{\Pi'}{\Pi}$. Indeed taking the derivative of the expression of $\Pi \in \GF_q((X^{-1}))$, one has: $$\frac{\Pi'}{\Pi} = \sum_{j=1}^{+ \infty} \frac{ \left ( 1 - \frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right )'}{ \left ( 1 - \frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right )} = \sum_{j=1}^{+ \infty} \frac{1}{X^{q^{j+1}}-X}.$$ A traditional notation is $[j] = X^{q^j}-X$, hence the above equality can be written $$\frac{\Pi'}{\Pi} = \sum_{j=1}^{+ \infty} \frac{1}{[j+1]}.$$ If $\Pi$ were algebraic, that would be the case also for $\Pi'$, (the proof is left to the reader who might use - for instance - the Christol, Kamae, Mend\`es France an Rauzy theorem, where the variable $X$ is replaced by $X^{-1}$), hence for $\frac{\Pi'}{\Pi}$. Finally to prove the transcendence of $\Pi$ it suffices to prove the transcendence of the series $\sum_{j=1}^{+ \infty} \frac{1}{[j]}$. This series is known as the ``bracket" series and has been proved transcendental by Wade, but we gave in \cite{AllouchePi} an ``automatic" proof for the transcendence of slightly more general series. We rewrite here this - easy - proof in the case of the bracket series. One has: $$\sum_{j=1}^{+ \infty} \frac{1}{[j]} = \sum_{j=1}^{+ \infty} \frac{1}{X^{q^{j}}-X} = \sum_{j=1}^{+ \infty} \frac{1}{X^{q^j}} \left ( 1 - \left ( \frac{1}{X} \right )^{q^j -1} \right )^{-1}$$ $$ = \sum_{\stackrel{{\scriptstyle j \geq 1}}{m \geq 0}} \left ( \frac{1}{X} \right )^{q^j+m(q^j-1)} = \frac{1}{X} \sum_{\stackrel{{\scriptstyle j \geq 1}} {m \geq 1}} \left ( \frac{1}{X} \right )^{m(q^j-1)} = \frac{1}{X} \sum_{n \geq 1} \left ( \sum_{\stackrel{{\scriptstyle j, m}} {m(q^j-1) = n}} 1 \right ) \frac{1}{X^n}.$$ This last expression can also be written $$\frac{1}{X} \sum_{n \geq 1} \left ( \sum_{\stackrel{{\scriptstyle j}} {(q^j-1) \mid n}} 1 \right ) \frac{1}{X^n}.$$ Using the theorem of Christol, Kamae, Mend\`es France and Rauzy one sees that the series above is algebraic over $\GF_q(X)$ if and only if the sequence $$ n \rightarrow \sum_{\stackrel{{\scriptstyle j}} {(q^j-1) \mid n}} 1 $$ is $q$-automatic. So we have to prove that it is not. But if a sequence $v$ is $q$-automatic, then the subsequence $n \rightarrow v_{q^n-1}$ is ultimately periodic, (hint: the base-$q$ expansion of $q^n - 1$ consists of $n$ digits all equal to $q-1$). It thus suffices to show that the sequence: $$n \rightarrow \sum_{\stackrel{{\scriptstyle j}} {(q^j-1) \mid (q^n-1)}} 1 $$ is not ultimately periodic. But it is well known that $(q^j-1) \mid (q^n-1)$ if and only if $j \mid n$. Hence, using the classical notation $\tau(n)$ to denote the number of divisors of the integer $n$, it suffices to show that the sequence $$n \rightarrow \tau(n)$$ is not ultimately periodic. OF COURSE THIS SEQUENCE HAS TO BE TAKEN modulo $p$, where $p$ is the characteristic of $\GF_q$. \medskip Now, suppose that $(\tau(n))_n \bmod p$ is ultimately periodic. Then there exist two integers $T \geq 1$ and $n_0 \geq 1$ such that: $$\forall n \geq n_0, \, \forall k \in \GN, \, \tau(n+kT) \equiv \tau(n) \bmod p.$$ This implies $$\forall n \geq n_0, \, \forall k \in \GN, \, \tau(n(1+kT)) = \tau(n+knT) \equiv \tau(n) \bmod p.$$ Now choose $k$ large enough such that $(1+kT) \geq n_0$ and $(1+kT)$ is a prime number, say $\overline{\omega}$: this is possible from the arithmetic progression theorem for prime numbers, (note that this case, i. e. the existence of arbitrarily large prime numbers in the progression $1+kT$, can be proved in a very elementary way, using cyclotomic polynomials). Taking $n = (1+kT) = \overline{\omega}$, one gets: $$\tau(\overline{\omega}^2) \equiv \tau(\overline{\omega}) \bmod p,$$ i. e. $$3 \equiv 2 \bmod p,$$ which yields the desired contradiction. \bigskip \begin{thebibliography}{99} \bibitem{Allouchesomme} J.-P. Allouche, {\em Somme des chiffres et transcendance}, Bull. Soc. math. France, {\bf 110} (1982), 279--285. \bibitem{Alloucheexpo} J.-P. Allouche, {\em Automates finis en th\'eorie des nombres}, Expo. Math., {\bf 5} (1987), 239--266. \bibitem{Allouchefc} J.-P. Allouche, {\em Sur le d\'eveloppement en fraction continue de certaines s\'eries formelles}, C. R. Acad. Sci. Paris, S\'erie I, {\bf 307} (1988), 631--633. \bibitem{AlloucheSW} J.-P. Allouche, {\em Note sur un article de Sharif et Woodcock}, S\'eminaire de Th\'eorie des Nombres de Bordeaux, S\'erie II, {\bf 1} (1989), 163--187. \bibitem{AllouchePi} J.-P. Allouche, {\em Sur la transcendance de la s\'erie formelle $\Pi$}, S\'eminaire de Th\'eorie des Nombres de Bordeaux, S\'erie II, {\bf 2} (1990), 103--117. \bibitem{Allouchephys} J.-P. Allouche, {\em Finite automata in $1$-dimensional and $2$-dimensional physics}, Number theory and physics, J.-M. Luck, P. Moussa, M. Waldschmidt (Eds.), Proceedings in Physics, Springer, {\bf 47} (1990), 177--184. \bibitem{AlloucheLNCS} J.-P. Allouche, {\em $q$-regular sequences and other generalizations of $q$-automatic sequences}, Lecture Notes in Computer Science, {\bf 583} (1992), 15--23. \bibitem{AlloucheHanoicyclique} J.-P. Allouche, {\em Note on the cyclic towers of Hanoi}, Theoret. Comput. Sci., (to appear). \bibitem{AlloucheBetremaShallit} J.-P. Allouche, J. B\'etr\'ema and J. Shallit, {\em Sur des points fixes de morphismes d'un mono\"{\i}de libre}, Inform. Th\'eor. Appl., {\bf 23} (1989), 235--249. \bibitem{AlloucheDress} J.-P. Allouche and F. Dress, {\em Tours de Hano\"{\i} et automates}, Inform. Th\'eor. Appl., {\bf 24} (1990), 1--15. \bibitem{AlloucheShallit} J.-P. Allouche and J. Shallit, {\em The ring of $k$-regular sequences}, Theoret. Comput. Sci., {\bf 98} (1992), 163--197. \bibitem{BaumSweet} L. E. Baum and M. M. Sweet, {\em Continued fractions of algebraic power series in characteristic $2$}, Ann. of Math., {\bf 103} (1976), 539--610. \bibitem{Berthe1} V. Berth\'e, {\em De nouvelles preuves ``automatiques" de transcendance pour la fonction z\'eta de Carlitz}, Journ\'ees arithm\'etiques de Gen\`eve, Ast\'erisque, {\bf 209} (1992), 159--168. \bibitem{Berthe2} V. Berth\'e, {\em Combinaisons lin\'eaires de $\frac{\zeta(s)}{\Pi^s}$ sur {\em \GF}$_q(x)$, pour $1 \leq s \leq (q-2)$}, submitted. \bibitem{Berthe3} V. Berth\'e, {\em Automates et valeurs de transcendance du logarithme de Carlitz}, Acta Arithmetica, (to appear). \bibitem{Carlitz} L. Carlitz, {\em On certain functions connected with polynomials in a Galois field}, Duke Math. J., {\bf 1} (1935), 137--168. \bibitem{Chomsky} N. Chomsky and M. P. Sch\"utzenberger, {\em The algebraic theory of context-free languages}, in Computer programming and formal languages, 118--161, North Holland, Amsterdam, 1963. \bibitem{CKMFR} G. Christol, T. Kamae, M. Mend\`es France, G. Rauzy, {\em Suites alg\'e\-bri\-ques, automates et substitutions}, Bull. Soc. math. France, {\bf 108} (1980), 401--419. \bibitem{Cobham1} A. Cobham, {\em Uniform tag sequences}, Math. Systems Theory, {\bf 6} (1972), 164--192. \bibitem{Cobham2} A. Cobham, {\em On the base-dependence of sets of numbers recognizable by finite automata}, Math. Systems Theory, {\bf 3} (1969), 186--192. \bibitem{Davis} C. Davis and D. E. Knuth, {\em Number representations and dragon curves, I, II}, J. Recr. Math. {\bf 3} (1970), 161--181 and 133--149. \bibitem{Dekking} M. Dekking, M. Mend\`es France and A. van der Poorten, {\em FOLDS!}, Math. Intell. {\bf 4} (1982), 130--138, 173--181 and 190--195. \bibitem{Deligne} P. Deligne, {\em Int\'egration sur un cycle \'evanescent}, Invent. Math., {\bf 76} (1984), 129--143. \bibitem{Eilenberg} S. Eilenberg, {\em Automata, Languages and Machines}, vol. A, Acad. Press, New York, 1974. \bibitem{Furstenberg} H. Furstenberg, {\em Algebraic functions over finite fields}, J. Algebra, {\bf 7} (1967), 271--277. \bibitem{Harase} T. Harase, {\em Algebraic elements in formal power series rings}, Israel J. Math., {\bf 63} (1988), 281--288. \bibitem{LoxtonvdP} J. H. Loxton and A. J. van der Poorten, {\em Arithmetic properties of automata: regular sequences}, J. Reine Angew. Math., {\bf 392} (1988), 57--69. \bibitem{MendesvdP} M. Mend\`es France and A. van der Poorten, {\em Arithmetic and analytic properties of paperfolding sequences}, dedicated to K. Mahler, Bull. Austral. Math. Soc., {\bf 24} (1981), 123--131. \bibitem{MillsRobbins} W. H. Mills and D. P. Robbins, {\em Continued fractions for certain algebraic power series}, J. Number Theory, {\bf 23} (1986), 388--404. \bibitem{Mkaouar} M. Mkaouar, Th\`ese, Lyon, 1993. \bibitem{Morse} M. Morse, {\em Recurrent geodesics on a surface of negative curvature}, Trans. Amer. Math. Soc., {\bf 22} (1921), 84--100. \bibitem{Prouhet} E. Prouhet, Comptes-Rendus de l'Acad\'emie des Sciences, Paris, {\bf 33} (1851), 225. \bibitem{Rudin} W. Rudin, {\em Some theorems on Fourier coefficients}, Proc. Amer. Math. Soc., {\bf 10} (1959), 855--859. \bibitem{Salon1} O. Salon, {\em Suites automatiques \`a multi-indices et alg\'ebricit\'e}, C. R. Acad. Sci. Paris, S\'erie I, {\bf 305} (1987), 501--504. \bibitem{Salon2} O. Salon, {\em Suites automatiques \`a multi-indices}, S\'eminaire de Th\'eorie des Nombres de Bordeaux, Expos\'e 4, 1986--1987. \bibitem{Shallit} J. Shallit, {\em A generalization of automatic sequences}, Theoret. Comput. Sci., {\bf 61} (1988), 1--16. \bibitem{Shapiro} H. S. Shapiro, {\em Extremal problems for polynomial and power series}, Thesis, M.I.T., 1951. \bibitem{SharifWoodcock} H. Sharif and C. F. Woodcock, {\em Algebraic functions over a field of positive characteristic and Hadamard products}, J. Lond. Math. Soc., {\bf 37} (1988), 395--403. \bibitem{Sloane} N. J. A. Sloane, {\em A Handbook of Integer Sequences}, Academic Press, New York, 1973. \bibitem{Thue1} A. Thue, {\em \"Uber unendliche Zeichenreihen}, Norske vid. Selsk. Skr. I. Mat. Kl. Christiana, {\bf 7} (1906), 1--22. \bibitem{Thue2} A. Thue, {\em Lage gleicher Teile gewisse Zeichenreihen}, Norske vid. Selsk. Skr. I. Mat. Kl. Christiana, {\bf 1} (1912), 1--67. \end{thebibliography} \end{document}