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 -automatique est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières : par automate fini déterministe, par morphisme uniforme, par noyau ou par série formelle. Par exemple, pour un automate fini, on définit une suite automatique de la façon suivante : le -ième terme est fonction de l'état atteint par lecture de la représentation de l'entier en base [1]. L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse.

Un ensemble -reconnaissable de nombres est un ensemble S d'entiers positifs ou nuls dont la suite caractéristique est k-automatique ; en d'autres termes, S est k-reconnaissable si la suite , définie par si et sinon, est une suite k-automatique.

Un nombre réel automatique (plus précisément un nombre réel -automatique) est un nombre réel dont le développement en base est une suite automatique, pour un entier [2]. Tout nombre réel automatique est soit rationnel, soit transcendant[3]. Ceci fournit une large classe de nombres transcendants. Par exemple, la constante de Prouhet-Thue-Morse 0,412 454 033 640..., dont le développement binaire est donné par la suite 0,0110100110010110..., est un nombre transcendant.

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

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

Les automates finis utilisés dans la définition des suites automatiques diffèrent légèrement des automates finis déterministes complets ; ils sont tous déterministes et complets, mais au lieu d'avoir un ensemble d'état séparé en deux parties, les états terminaux et les autres, les états de ces automates sont partitionnés en plusieurs classes et chaque classe se voit attribué un symbole dans un alphabet donné. Lorsqu'un mot est lu, le résultat du calcul est le symbole de la classe de l'état d'arrivé. Un tel automate est appelé DFAO pour « déterministic finite automaton with output ».

Automate déterministe avec sortie

Soit un entier. Un automate déterministe avec sortie (en anglais DFAO)[4] est un automate fini déterministe complet où :

  • L'alphabet est égal à ;
  • est l'ensemble des états ;
  • est l'état initial ;
  • est une application de dans appelée fonction de transition ;
  • est une application qui étiquette les états de l'automate par des symboles de .

L'automate n'a pas d'états terminaux, ils sont remplacés par l'application . Ne pas confondre avec l'automate de Mealy, ou l'automate de Moore.

On étend en une application à l'ensemble des mots de en posant :

  • est le mot vide ;
  • pour et .

Définition d'une suite -automatique par automate

Pour tout entier , on note l'écriture en base de l'entier [5]. L'automate lit l'entier sous la forme de son écriture en base et, partant de l'état initial , calcule, en « consommant » les chiffres de , l'état d'arrivée . Le résultat du calcul est le symbole .

Définition — La suite -automatique définie par est la suite , obtenue par concaténation des termes de la suite , où .

Exemple

Automate de Prouhet-Thue-Morse. Notation: est l'état avec . C'est un exemple de DFAO.

La suite de Prouhet-Thue-Morse. Elle peut être définie par l'automate où : , avec état initial . La fonction de transition est donnée par et . Enfin, .

L'écriture binaire des entiers naturels montre qu'après lecture du mot on est dans ou selon que comporte un nombre pair ou impair de chiffres 1.

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

Préliminaire sur les morphismes

Soit et soit un alphabet.

  • Un morphisme est -uniforme si image de toute lettre de est un mot de longueur .
  • Un morphisme est prolongeable en la lettre ou -prolongeable pour la lettre si commence par .
  • Une application se prolonge en une fonction sur les mots finis ou infinis, encore notée , en appliquant la fonction à chacune des lettres qui composent le mot.

Définition

Soit , soient un alphabet et une lettre. Soit un morphisme -uniforme et -prolongeable, c'est-à-dire que commence par . Alors, tout itéré est préfixe de tous les pour . La suite converge vers un mot infini unique noté défini par la propriété que tous les en sont préfixes. Ce mot est par définition purement morphique.

Soit maintenant un alphabet et soit une application. Elle est étendu en un morphisme lettre à lettre sur les mots infinis. La suite

est une suite morphique. C'est la deuxième définition des suites -automatiques[6] :

Une suite -automatique est un mot morphique, image par un morphisme lettre à lettre, du point fixe d'un morphisme -uniforme prolongeable : .

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

.

Exemples

  • La suite caractéristique des puissances de 2 est produite par le morphisme 2-uniforme sur l'alphabet défini par
qui engendre le mot infini
,
suivi du morphisme qui envoie sur et laisse et inchangés, ce qui donne .
qui engendre, à partir de 0, le mot infini . Ce mot est purement morphique, et le morphisme de la définition est l’identité.

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

Construction du -noyau de la suite de Prouhet-Thue-Morse avec le triplet En rouge et vert, les deux suites du -noyau.

Soit une suite infinie. Le -noyau de est l'ensemble des sous-suites

.

Cette définition un peu compliquée s'explique bien pour  : le -noyau est formé de la suite , puis des 2 suites obtenues en prenant un terme sur deux dans , 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 -automatique si et seulement si son -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[modifier | modifier le code]

Les suites -automatiques, lorsque est un nombre premier, ont une caractérisation par séries formelles. On note le corps de fractions rationnelles, et l'anneau des séries formelles en une variable et à coefficients dans . Une série est algébrique sur s'il existe des polynômes tels que

.

Nous prenons pour corps le corps à éléments.

Théorème (Christol (de))[7] —  Soit une suite à éléments dans un alphabet . On suppose que est un sous-ensemble de pour un entier positif . Alors est -automatique si et seulement si la série

est algébrique sur .

Exemples:

.

On a

.

Sur , on a , ce qui donne l'équation :

.

Ceci montre que est algébrique sur . Donc la suite des puissances de 2 est -automatique.

avec [8]. On a :

sur . Ceci montre que la suite de Prouhet-Thue-Morse est une suite -automatique [8]

Exemples de suites automatiques[modifier | modifier le code]

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[9], et qui est lié à l'ensemble triadique de Cantor. C'est le mot purement morphique qui est le point fixe du morphisme 3-uniforme On obtient successivement Les 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[modifier | modifier le code]

Un ensemble d'entiers positifs ou nuls S est k-reconnaissable si sa suite caractéristique suite caractéristique est k-automatique ; en d'autres termes, S est k-reconnaissable si la suite définie par si , et sinon, est une suite k-automatique[10].

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 en des ensembles tous k-reconnaissables, la suite définie par si et seulement si est k-automatique.

Propriétés sur les suites automatiques[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 -automatique dépend fortement de l'entier . Deux entiers et sont dits multiplicativement dépendants s'il existe des entiers et tels que . Par exemple et sont multiplicativement dépendants parce que .

Théorème (Cobham) — Soient et deux entiers multiplicativement indépendants. Une suite est à la fois -automatique et -automatique seulement si elle est -automatique[11].

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

Proposition — Si et sont deux entiers multiplicativement dépendants, alors les suites -automatique sont les mêmes que les suites -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 -automatique, alors l'autre est également -automatique.
  • Si est une suite -automatique sur un alphabet , et si est un morphisme uniforme, alors la suite obtenue par concaténations des mots est -automatique.
  • Si est une suite -automatique, alors la sous-suite est -automatique pour tous entiers .

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

  • union, intersection, complémentation
  • addition c'est-à-dire l'opération .
  • multiplication par une constante positive, c'est-à-dire l'opération .
  • l'opération d'extraction affine , où et sont des entiers naturels.

Complexité en facteurs[modifier | modifier le code]

Le nombre de facteurs de longueur d'une suite automatique 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 est une suite -automatique[2]. Un nombre réel automatique est soit rationnel, soit transcendant[3]. Ainsi, le nombre (binaire) de Thue-Morse, appelé la constante de Prouhet-Thue-Morse :

est un nombre transcendant.

Historique[modifier | modifier le code]

Le concept de suite automatique a été introduit par Büchi en 1960[12] 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[13]; il fait aussi la correspondance avec les uniform tag sequences (ou « système de tague uniforme ») en 1972[14].

Le terme « suite automatique » apparaît déjà dans un article de Jean-Marc Deshouillers en 1979-1980[15]. Samuel Eilenberg, dans son traité de 1974[16], 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[modifier | modifier le code]

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

  1. Allouche et Shallit 2003, p. 152.
  2. a et b Hejhal 1999, p. 556.
  3. 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.
  4. Allouche et Shallit 2003.
  5. L'écriture en base de est le mot vide.
  6. Allouche et Shallit 2003, p. 175.
  7. Allouche et Shallit 2003, p. 356.
  8. a et b (en) « What is an automatic sequence? ».
  9. (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).
  10. Allouche et Shallit 2003, p. 168.
  11. Allouche et Shallit 2003, p. 345-350.
  12. (en) Julius Richard Büchi, « Weak second-order arithmetic and finite automata », Z. Math. Logik Grundlagen Math., vol. 6,‎ , p. 66–92 (DOI 10.1007/978-1-4613-8928-6_22).
  13. Cobham 1969.
  14. Cobham 1972.
  15. (en) Jean-Marc Deshouillers, « La répartition modulo 1 des puissances de rationnels dans l’anneau des séries formelles sur un corps fini », Séminaire de Théorie des Nombres de Bordeaux,‎ 1979–1980, p. 5.01–5.22.
  16. Eilenberg 1974, Chapitre XV.

(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) 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
  • Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, no 1-2,‎ , p. 164–192 (DOI 10.1007/BF01706087, Math Reviews 0457011).
  • (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, coll. « Pure and Applied Mathematics » (no 58), , xvi+451 p. (ISBN 978-0-12234001-7)

Articles connexes[modifier | modifier le code]