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 ne 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'ensemble 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 F_{p^m} à p^m éléments.

Théorème (Christol)[7] —  Soit u=(u_n)_{n\ge0} une suite à éléments dans un alphabet A. On suppose que A est un sous-ensemble de 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 F_{p^m}(X).

Par exemple, la série formelle sur F_2 qui est la série 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 F_2, on a f(X^2)=f(X)^2, ce qui donne, sur F_2, l'équation : f(X)^2+f(X)+X=0. Ceci montre que f(X) est algébrique.

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 & Shallit (2003) p.152
  2. Allouche & Shallit (2003) p.168
  3. a et b Hejhal (1999) p.556
  4. a et b Boris Adamczewski and Yann Bugeaud (007), « On the complexity of algebraic numbers. I. Expansions in integer bases », Ann. of Math, vol. 165, no 2,‎ 2007, p. 547-565.
  5. Allouche & Shallit (2003)
  6. Allouche & Shallit (2003) p.175
  7. Allouche & Shallit (2003), page 356.
  8. (en) Anna E. Frid, « Arithmetical complexity of the symmetric D0L words », Theoretical Computer Science, vol. 306,‎ 2003, p. 535-542 (lien DOI?).
  9. Allouche & Shallit (2003) pp.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]

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