Suite automatique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématique, en combinatoire des mots et en théorie des automates, une suite automatique (ou suite k-automatiquek est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières, et notamment par un automate fini. Le n-ième terme de la suite est fonction de l'état atteint, dans un automate fixe associé à la suite, par le mot qui est le développement, en base k, de l'entier n[1]. L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse.

Un ensemble d'entiers naturels est un ensemble k-automatique si la suite des valeurs de sa fonction caractéristique est une suite automatique[2]. L'exemple par excellence d'un ensemble 2-automatique est l'ensemble des puissances de 2.

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 automatique, pour un entier k[3]. Tout nombre réel automatique est soit rationnel, soit transcendant[4]. Ceci fournit une large classe de nombres transcendants. Par exemple, la constante de Prouhet-Thue-Morse 0,412 454 033 640. . . qui le nombre dont le développement binaire est donné par la suite 0,0110100110010110. . . est un nombre transcendant.

Définitions équivalentes[modifier | modifier le code]

Il existe quatre méthodes équivalentes pour définir les suites automatiques.

Définition par automate[modifier | modifier le code]

Automate de Prouhet-Thue-Morse. C'est un exemple de DFAO : \pi(a0)=0, \pi(b1)=1

Soit k\ge1 un entier. Soit \mathcal{A}=(Q,i,T) un automate fini déterministe complet sur l'alphabet \{0,\ldots,k-1\}, où :

  • Q est l'ensemble des états
  • i est l'état initial
  • T est l’ensemble des états terminaux.

La fonction de transition est notée par un point : q\cdot a est l'état cible de la transition partant de q et portant l'étiquette a. Soit A un ensemble fini, et soit \pi: \{0,\ldots,k-1\}\to A une application qui étiquette les états de l'automate par des symboles de A.

La suite k-automatique définie par \mathcal{A} est la suite

a_0a_1a_2\dots a_n\dots,

avec

a_n=\pi(i\cdot n^\prime)

n^\prime est l'écriture en base k de l'entier n. En d'autres termes, le mot n^\prime est lu dans l'automate à partir de l'état initial. Soit q=i\cdot n^\prime l'état atteint; alors la valeur a_n est l'étiquette \pi(q) de cet état. Le couple formé par l'automate \mathcal{A} et la fonction \pi(q) est appelé automate déterministe avec sortie (en anglais DFAO)[5]. Ne pas confondre avec l'automate de Mealy, ou l'automate de Moore.

Définition par morphisme uniforme[modifier | modifier le code]

Soit k\ge2. Soit B un alphabet. Un morphisme f:B^*\to B^* est k-uniforme si l'image f(b) est un mot de longueur k pour toute lettre b de B. Supposons que f est k-uniforme et qu'il est prolongeable en une lettre b de B, c'est-à-dire que f(b) commence par b. Alors la suite des itérés (f^n(b))_{n\ge0} tend vers le mot infini noté

y=f^\omega(b)

dont tous les f^n(b) sont des préfixes. Ce mot y est purement morphique. Soit A un alphabet et soit \pi:B\to A une application. Elle est étendu 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[6]. Par exemple, la suite caractéristique des puissances de 2 est produite par le morphisme 2-uniforme

\begin{array}{lcl}a&\mapsto a1\\1&\mapsto 10\\0&\mapsto 00\end{array}

qui engendre le mot infini

a11010001\cdots,

suivi du morphisme qui envoie a sur 0 et laisse 0 et 1 inchangés.

Suites 1-automatiques[modifier | modifier le code]

Lorsque k=1, l'écriture en base k d'une entier n est composée de n symboles identiques. Dans ce cas, l'automate considéré opère sur un alphabet à une seule lettre. La définition par morphisme ne s'étend en revanche pas. On peut vérifier qu'un ensemble 1-automatique est exactement l'union d'un ensemble fini, et d'une union finie de progressions arithmétiques infinies.

Définition par noyau[modifier | modifier le code]

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

N_k(u)=\{(u_{k^in+j})_{n\ge0}\mid i\ge0, 0\le j<k^n\}.

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, est la suivante : une suite est k-automatique si et seulement si son k-noyau est fini. Par exemple, la suite de Prouhet-Thue-Morse est

0110100110010110. . .

en prenant les termes de 2 en 2, on a 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 la suite de Prouhet-Thue-Morse est automatique.

Définition par série formelle algébrique[modifier | modifier le code]

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_1Y+P_2Y^2+\cdots +P_dY^d=0.

Nous prenons pour corps K le corps {\rm F}_{p^m} à p^m éléments.

Théorème (Christol (de))[7] —  Soit u=(u_n)_{n\ge0} 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_nX^n

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

Par exemple, 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\ge0}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, sur {\rm F}_2, l'équation : f(X)^2+f(X)+X=0. Ceci montre que f(X) est algébrique sur {\rm F}_2.

Exemples[modifier | modifier le code]

Les suites suivantes sont automatiques :

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

Propriétés[modifier | modifier le code]

Influence de la base[modifier | modifier le code]

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[9].

En complément de ce théorème, 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[modifier | modifier le code]

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\ge0} 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\ge0} est une suite k-automatique, alors la sous-suite (u_{an+b})_{n\ge0} est k-automatique pour tous entiers a,b\ge0.

Les ensembles k-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[modifier | modifier le code]

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[modifier | modifier le code]

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

0,0110\ 1001\ 1001\ 0110\cdots

est un nombre transcendant.

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Allouche et Shallit 2003, p. 152.
  2. Allouche et Shallit 2003, p. 168.
  3. a et b Hejhal 1999, p. 556.
  4. a et b (en) Boris Adamczewski et Yann Bugeaud, « On the complexity of algebraic numbers. I. Expansions in integer bases », Ann. of Math, vol. 165, no 2,‎ , p. 547-565.
  5. Allouche et Shallit 2003.
  6. Allouche et Shallit 2003, p. 175.
  7. Allouche et Shallit 2003, p. 356.
  8. (en) Anna E. Frid, « Arithmetical complexity of the symmetric D0L words », Theoretical Computer Science, vol. 306,‎ , p. 535-542 (DOI 10.1016/S0304-3975(03)00345-1).
  9. Allouche et Shallit 2003, p. 345-350.

(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[modifier | modifier le code]

  • (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences, Cambridge University Press,‎ (ISBN 0-521-82332-3) Document utilisé pour la rédaction de l’article
  • (en) Dennis A. Hejhal (en), Emerging applications of number theory, Springer, coll. « The IMA volumes in mathematics and its applications » (no 109),‎ (ISBN 0387988246)
  • (en) Alan Cobham, « Uniform tag sequences », Math. Systems Theory, vol. 6,‎ , p. 164-192
  • (en) 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 » (no 135),‎ (ISBN 978-0-521-51597-9, lire en ligne), p. 410- 451

Article connexe[modifier | modifier le code]

Théorème d'Eisenstein