Suite automatique

En mathématique, en combinatoire des mots et en théorie des automates, une suite automatique (ou suite $k$-automatique où $k$ est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières équivalentes : par automate fini déterministe, par morphisme uniforme, par noyau ou par série formelle. Par exemple, la caractérisation par automates est la suivante : une suite est $k$-automatique s'il existe un automate tel que le $n$-ième terme de la suite est fonction de l'état atteint par cet automate après lecture de $n$ en base $k$. L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse.

Un ensemble $k$-reconnaissable de nombres est un ensemble S d'entiers naturels dont la suite caractéristique est k-automatique ; en d'autres termes, S est k-reconnaissable si la suite $(s_{n})_{n\geq 0}$, définie par $s_{n}=1$ si $n\in S$ et $s_{n}=0$ sinon, est k-automatique.

Un nombre réel automatique (plus précisément un nombre réel $k$-automatique) est un nombre réel dont le développement en base $k$ est une suite $k$-automatique.

Tout nombre réel automatique est soit rationnel, soit transcendant. Ce théorème fournit une large classe de nombres transcendants. Par exemple, la constante de Prouhet-Thue-Morse, dont le développement binaire $0,0110100110010110\ldots _{2}$ est donné par la suite du même nom, est un nombre transcendant.

Définitions équivalentes

Définition par automate

Les automates utilisés pour définir les suites automatiques généralisent légèrement les automates finis déterministes complets : ils sont toujours finis, déterministes et complets, et leur résultat est toujours fonction de l'état d'arrivée, mais ce résultat n'est plus nécessairement une réponse binaire (accepté ou refusé). Autrement dit, au lieu de marquer chaque état comme terminal ou non terminal, on marque chaque état par un symbole de sortie choisi dans un certain ensemble.

Un tel automate est appelé en anglais « (déterministic) finite automaton with output » et abrégé (D)FAO, ce qu'on peut traduire par « automate (déterministe complet) avec sortie ». Cette notion diffère de celle d'automate transducteur (automate de Mealy ou automate de Moore), qui émet un résultat fonction de la séquence d'états et de transitions empruntés, plutôt que de l'état d'arrivée seul.

Automate déterministe complet avec sortie

Un automate déterministe complet avec sortie est un n-uplet ${\mathcal {A}}=(\Sigma ,A,Q,q_{0},\delta ,\pi )$ où :

• $\Sigma$ est un ensemble fini dit « alphabet », ses éléments sont les lettres des mots lus en entrée ;
• $A$ est un ensemble dont les éléments sont appelés les « symboles de sortie » ;
• $Q$ est un ensemble fini dont les éléments sont appelés les « états » de l'automate ;
• $q_{0}\in Q$ est un état dit l'« état initial » ;
• $\delta :Q\times \Sigma \to Q$ est une application dite « fonction de transition » (notons qu'avec ce formalisme, l'automate est toujours déterministe et complet) ;
• $\pi :Q\to A$ est une application qui étiquette chaque état de l'automate par un symbole.

L'automate n'a pas d'états terminaux ; au lieu de cela, son résultat est donné par l'application $\pi$.

On étend $\delta$ à l'ensemble des mots dans $\Sigma ^{*}$, l'application résultante étant notée $\delta ^{*}:Q\times \Sigma ^{*}\to Q$, en posant :

• $\delta ^{*}(q,\varepsilon )=q$ où $\varepsilon$ est le mot vide ;
• $\delta ^{*}(q,xm)=\delta ^{*}(\delta (q,x),m)$ pour $x\in \Sigma$ et $m\in \Sigma ^{*}$.

Définition d'une suite $k$-automatique par automate

Soit $k\geq 1$ un entier, et soit $A$ un automate déterministe complet avec sortie sur l'alphabet $\Sigma =\{0\,;\ldots \,;k-1\}$. Pour tout entier $n\in \mathbb {N}$, l'écriture en base $k$ de $n$ est un mot sur l'alphabet $\Sigma$ qu'on note ${\bar {n}}_{k}$. L'automate ${\mathcal {A}}$ calcule un résultat pour l'entier $n$ de la façon suivante : partant de l'état initial $q_{0}$, l'automate lit un par un les chiffres de l'écriture ${\bar {n}}_{k}$ et calcule ainsi l'état d'arrivée $q=\delta ^{*}(q_{0},{\bar {n}}_{k})$ ; le résultat du calcul est finalement le symbole $\pi (q)$.

Définition — La suite $k$-automatique définie par ${\mathcal {A}}$ est la suite $a_{0}a_{1}a_{2}\dots a_{n}\dots$ obtenue par concaténation des termes de la suite $(a_{n})_{n\in \mathbb {N} }$, où $a_{n}=\pi (\delta ^{*}(q_{0},{\bar {n}}_{k}))$ est le résultat calculé par $A$ pour l'entier $n$.

Exemple

Automate de Prouhet-Thue-Morse. Dans cette figure, un état $q$ dont le symbole de sortie est $a$ est représenté par la notation $q/a$.

La suite de Prouhet-Thue-Morse est définie comme suit :

• $a_{n}$ = 0 si l'écriture binaire de l'entier $n$ comporte un nombre pair de chiffres 1 ;
• $a_{n}$ = 1 sinon.

Cette suite est engendrée par l'automate ${\mathcal {A}}=(\Sigma ,A,Q,q_{0},\delta ,\pi )$ où

• $\Sigma =A=\{0,1\}$,
• $Q=\{q_{0},q_{1}\}$ ($q_{0}$ étant l'état initial),
• $\delta (q_{i},0)=q_{i}$, $\delta (q_{i},1)=q_{1-i}$
• et $\pi (q_{i})=i$.

Cet automate est représenté ci-contre. Il termine dans l'état $q_{0}$ (respectivement $q_{1}$) s'il y a un nombre pair (respectivement impair) de 1 dans ${\bar {n}}_{2}$, où $n$ est l'entier donné en entrée.

Définition par morphisme uniforme

Préliminaire sur les morphismes

Soit $k\geq 2$ et soit $B$ un alphabet.

• Un morphisme $f:B^{*}\to B^{*}$ est $k$-uniforme si image de toute lettre de $B$ est un mot de longueur $k$.
• Un morphisme $f:B^{*}\to B^{*}$ est prolongeable en la lettre $b\in B$ ou $b$-prolongeable pour la lettre $b\in B$ si $f(b)$ commence par $b$.
• Une application $\pi :B\rightarrow A$ se prolonge en une fonction sur les mots finis ou infinis, encore notée $\pi$, en appliquant la fonction à chacune des lettres qui composent le mot.

Définition

Soit $k\geq 2$, soient $B$ un alphabet et $b\in B$ une lettre. Soit $f:B^{*}\rightarrow B^{*}$ un morphisme $k$-uniforme et $b$-prolongeable, c'est-à-dire que $f(b)$ commence par $b$. Alors, tout itéré $f^{n}(b)$ est préfixe de tous les $f^{m}(b)$ pour $m>n$. La suite $(f^{n}(b))_{n\in \mathbb {N} }$ converge vers un mot infini unique $y$ noté $y=f^{\omega }(b)$ défini par la propriété que tous les $f^{n}(b)$ en sont préfixes. Ce mot $y$ est par définition purement morphique.

Soit maintenant $A$ un alphabet et soit $\pi :B\to A$ une application. Elle est étendue en un morphisme lettre à lettre sur les mots infinis. La suite

$x=\pi (y)$

est une suite morphique. C'est la deuxième définition des suites $k$-automatiques :

Définition — Une suite $k$-automatique $x$ est un mot morphique, image par un morphisme lettre à lettre, du point fixe d'un morphisme $k$-uniforme prolongeable :

$x=\pi (f^{\omega }(b))$.

Exemples

• La suite caractéristique des puissances de 2 est produite par le morphisme 2-uniforme sur l'alphabet $B=\{a,0,1\}$ défini par

$a\mapsto a1\ ,\quad 1\mapsto 10\ ,\quad 0\mapsto 00$

qui engendre le mot infini

$a11010001\cdots$,

suivi du morphisme qui envoie $a$ sur $0$ et laisse $0$ et $1$ inchangés, ce qui donne $011010001\cdots$.

• La suite de Prouhet-Thue-Morse peut être définie par le morphisme 2-uniforme :

$1\mapsto 10\ ,\quad 0\mapsto 01$

qui engendre, à partir de 0, le mot infini $0110100110010110\cdots$. Ce mot est purement morphique, et le morphisme $\pi$ de la définition est l’identité.

Définition par noyau

Construction du $2$-noyau de la suite de Prouhet-Thue-Morse avec le triplet $(k=2,i,j)$ En rouge et vert, les deux suites du $2$-noyau.

Soit $u=(u_{n})_{n\geq 0}$ une suite infinie. Le $k$-noyau de $u$ est l'ensemble des sous-suites

$N_{k}(u)=\{(u_{k^{i}n+j})_{n\geq 0}\mid i\geq 0,0\leq j<k^{i}\}$.

Cette définition un peu compliquée s'explique bien pour $k=2$ : le $2$-noyau est formé de la suite $u$, puis des 2 suites obtenues en prenant un terme sur deux dans $u$, puis des 4 suites obtenues en prenant un terme sur 4, etc.

La caractérisation, ou la troisième définition équivalente, est la suivante :

Définition — Une suite est $k$-automatique si et seulement si son $k$-noyau est fini.

Exemple :

En prenant les termes de 2 en 2 dans la suite de Prouhet-Thue-Morse 0110100110010110. . ., on obtient les deux suites :

0-1-1-0-1-0-0-1-. . .

-1-0-0-1-0-1-1-0. . .

c'est-à-dire la suite elle-même et son opposée. Le 2-noyau est donc composé de ces deux suites, et ceci montre que la suite de Prouhet-Thue-Morse est automatique.

Définition par série formelle algébrique

Les suites $p$-automatiques, lorsque $p$ est un nombre premier, ont une caractérisation par séries formelles. On note $K(X)$ le corps de fractions rationnelles, et $K[[X]]$ l'anneau des séries formelles en une variable $X$ et à coefficients dans $K$. Une série $Y$ est algébrique sur $K(X)$ s'il existe des polynômes $P_{0}(X),P_{1}(X),\ldots ,P_{d}(X)$ tels que

$P_{0}+P_{1}Y+P_{2}Y^{2}+\cdots +P_{d}Y^{d}=0$.

On prend pour corps $K$ le corps ${\rm {F}}_{p^{m}}$ à $p^{m}$ éléments.

Théorème (Christol) —  Soit $u=(u_{n})_{n\geq 0}$ une suite à éléments dans un alphabet $A$. On suppose que $A$ est un sous-ensemble de ${\rm {F}}_{p^{m}}$ pour un entier positif $m$. Alors $u$ est $p$-automatique si et seulement si la série

$u(X)=\sum _{n=0}^{\infty }u_{n}X^{n}$

est algébrique sur ${\rm {F}}_{p^{m}}(X)$.

Exemples :

• La série génératrice de la suite caractéristique des puissances de 2 est :

$f(X)=X+X^{2}+X^{4}+X^{8}+\cdots =\sum _{i\geq 0}X^{2^{i}}$.

On a

$f(X)=X+f(X^{2})$.

Sur ${\rm {F}}_{2}$, on a $f(X^{2})=f(X)^{2}$, ce qui donne l'équation :

$f(X)^{2}+f(X)+X=0$.

Ceci montre que $f(X)$ est algébrique sur ${\rm {F}}_{2}$. Donc la suite des puissances de 2 est $2$-automatique.

• La série génératrice de la suite de Prouhet-Thue-Morse est :

$f(X)=0\times 1+1\times X+1\times X^{2}+0\times X^{3}\cdots =\sum _{i\geq 0}s(i)X^{i}$

avec $(s(n))_{n\geq 0}=0,1,1,0,1,0,0,1,\ldots$. On a :

$(1+X^{3})f(X)^{2}+(1+X^{2})f(X)+f(X)=0$

sur $F_{2}$. Ceci montre que la suite de Prouhet-Thue-Morse est une suite $2$-automatique

Définition par formule logique

Les suites k-automatiques admettent des caractérisations en termes de logique du premier ordre. Pour les suites $k$-automatiques, elle est due à Büchi ; elle a été étendues aux suites de Pisot par Véronique Bruyère et Georges Hansel. Une présentation est donnée dans le livre de Michel Rigo. Une étude systématique est donnée par Hamoon Mousavi.

Exemples de suites automatiques

Les suites suivantes sont automatiques :

• La suite de Prouhet-Thue-Morse
• Le mot infini ternaire de Thue-Morse, qui est un mot sans carré
• Le mot infini d'Arshon, qui est un autre mot sans carré
• La suite de Rudin-Shapiro
• La suite de Baum et Sweet
• Les suites de pliage de papier sont automatiques si elles sont régulières.
• Un autre exemple est le mot infini, appelé mot de Sierpiński par Anna Frid, et qui est lié à l'ensemble triadique de Cantor. C'est le mot purement morphique qui est le point fixe du morphisme 3-uniforme ${\begin{array}{lcl}0&\mapsto &010\\1&\mapsto &111\end{array}}$ On obtient successivement ${\begin{array}{l}0\\010\\010111010\\010111010111111111010111010\\\cdots \end{array}}$ Les $0$ dans ce mot infini sont aux positions des entiers naturels dont l'écriture en base 3 ne comporte pas le chiffre 1.

La suite de Fibonacci, et les suites sturmiennes ne sont pas automatiques.

Ensemble reconnaissable de nombres

Un ensemble d'entiers positifs ou nuls S est k-reconnaissable si sa suite caractéristique est k-automatique ; en d'autres termes, S est k-reconnaissable si la suite $(s_{n})_{n\geq 0}$ définie par $s_{n}=1$ si $n\in S$, et $s_{n}=0$ sinon, est une suite k-automatique.

Ainsi, une suite k-automatique qui prend m valeurs distinctes définit une partition de l'ensemble des entiers naturels en m parties qui chacune constitue un ensemble k-reconnaissable. Réciproquement, étant donné une partition de $\mathbb {N}$ en des ensembles $S_{0},\ldots ,S_{m-1}$ tous k-reconnaissables, la suite $s=(s_{n})_{n\geq 0}$ définie par $s_{n}=i$ si et seulement si $n\in S_{i}$ est k-automatique.

Propriétés sur les suites automatiques

Influence de la base

La propriété principale est le théorème de Cobham qui énonce que le fait d'être $k$-automatique dépend fortement de l'entier $k$. Deux entiers $k$ et $\ell$ sont dits multiplicativement dépendants s'il existe des entiers $n$ et $m$ tels que $k^{n}=\ell ^{m}$. Par exemple $4$ et $8$ sont multiplicativement dépendants parce que $4^{3}=8^{2}$.

Théorème (Cobham) — Soient $k$ et $\ell$ deux entiers multiplicativement indépendants. Une suite est à la fois $k$-automatique et $\ell$-automatique seulement si elle est $1$-automatique.

En complément de ce théorème démontré par Alan Cobham en 1969, il y a la proposition suivante :

Proposition — Si $k$ et $\ell$ sont deux entiers multiplicativement dépendants, alors les suites $k$-automatique sont les mêmes que les suites $\ell$-automatiques.

Robustesse

Les suites automatiques sont stables pour un certain nombre de transformations.

• Si deux suites ne diffèrent que par un nombre fini de termes, et l'une est $k$-automatique, alors l'autre est également $k$-automatique.
• Si $u=(u_{n})_{n\geq 0}$ est une suite $k$-automatique sur un alphabet $A$, et si $\pi :A\to B^{*}$ est un morphisme uniforme, alors la suite $\pi (u)$ obtenue par concaténations des mots $\pi (u_{n})$ est $k$-automatique.
• Si $u=(u_{n})_{n\geq 0}$ est une suite $k$-automatique, alors la sous-suite $(u_{an+b})_{n\geq 0}$ est $k$-automatique pour tous entiers $a,b\geq 0$.

Les ensembles automatiques sont stables pour les opérations suivantes :

• union, intersection, complémentation
• addition c'est-à-dire l'opération $R+S=\{r+s\mid r\in R,s\in S\}$.
• multiplication par une constante positive, c'est-à-dire l'opération $nT=\{nt\mid t\in T\}$.
• l'opération d'extraction affine $J_{a,b}(S)=\{x\mid ax+b\in S\}$, où $a$ et $b$ sont des entiers naturels.

Complexité en facteurs

Le nombre $c_{u}(n)$ de facteurs de longueur $n$ d'une suite automatique $u$ croît au plus linéairement.

Nombres réels automatiques

Un nombre réel automatique est un nombre réel dont le développement en base $k$ est une suite $k$-automatique. Un nombre réel automatique est soit rationnel, soit transcendant. Ainsi, le nombre (binaire) de Thue-Morse, appelé la constante de Prouhet-Thue-Morse :

$0,0110\ 1001\ 1001\ 0110\cdots$

est un nombre transcendant.

Historique

Le concept de suite automatique a été introduit par Büchi en 1960 même s'il n'utilise pas la terminologie et est intéressé plutôt par une approche logique. Le terme d'ensemble reconnaissable de nombres apparaît tôt dans la théorie des automates finis, et est utilisé aussi par Cobham; il fait aussi la correspondance avec les uniform tag sequences (ou « système de tague uniforme ») en 1972.

Le terme « suite automatique » apparaît déjà dans un article de Jean-Marc Deshouillers en 1979-1980. Samuel Eilenberg, dans son traité de 1974, les appelle « suite k-reconnaissable ». La correspondance entre ensemble reconnaissable de nombres et suite automatique est détaillée dans le livre d'Eilenberg.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « automatic sequence » (voir la liste des auteurs).

Bibliographie

• (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3)
• Dennis A. Hejhal, Joel Friedman, Martin C. Gutzwiller et Andrew M. Odlyzko (éditeurs), Emerging applications of number theory, New York, Springer, coll. « The IMA volumes in mathematics and its applications » (n^o 109), 1999, xiii+689 (ISBN 0-387-98824-6, SUDOC 051980215)
• Alan Cobham, « Uniform tag sequences », Math. Systems Theory, vol. 6,‎ 1972, p. 164-192 (MR 0457011)
• Alan Cobham, « On the base-dependence of sets of numbers recognizable by finite automata », Mathematical Systems Theory, vol. 3, n^o 2,‎ 1969, p. 186–192 (DOI 10.1007/BF01746527, MR 0250789).

• Boris Adamczewski et Yann Bugeaud, « Transcendence and Diophantine approximation », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, automata and number theory, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 135), 2010 (ISBN 978-0-521-51597-9, lire en ligne), p. 410- 451
• Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, n^os 1-2,‎ 1972, p. 164–192 (DOI 10.1007/BF01706087, MR 0457011).
• (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, New York, Academic Press, coll. « Pure and Applied Mathematics » (n^o 58), 1974, xvi+451 (ISBN 978-0-12-234001-7)
• Yining Hu et Guoniu Wei-Han, « On the automaticity of the Hankel determinants of a family of automatic sequences », Theoretical Computer Science, vol. 795,‎ 2019, p. 154–164 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.06.009, arXiv 1806.05864).
• Jeffrey Shallit, The Logical Approach to Automatic Sequences : Exploring Combinatorics on Words with Walnut, Cambridge University Press, coll. « London Mathematical Society Lecture Note Series » (n^o 482), 2022, xvi + 358 (ISBN 978-1-108-74524-6, zbMATH 7565707).

Articles connexes

• Théorème d'Eisenstein
• Système de tague
• Mot de Toeplitz
• Suite de Piatetski-Shapiro