Présentation

Article

1 - SÉRIES FORMELLES SUR UN CORPS COMMUTATIF

  • 1.1 - Définitions, généralités
  • 1.2 - Algébricité

2 - ALPHABETS, MOTS, MORPHISMES, AUTOMATES FINIS

  • 2.1 - Alphabets, mots et morphismes
  • 2.2 - Suites sur un alphabet, topologie, points fixes de morphismes
  • 2.3 - Automates finis

3 - Q-NOYAU D’UNE SUITE, Q-OPÉRATEURS DE CARTIER, UN PREMIER THÉORÈME

4 - LE THÉORÈME DE CHRISTOL

5 - QUELQUES AUTRES PROPRIÉTÉS ET APPLICATIONS DES SUITES AUTOMATIQUES

Article de référence | Réf : AF175 v1

Quelques autres propriétés et applications des suites automatiques
Suites automatiques et séries formelles algébriques

Auteur(s) : Jean-Paul ALLOUCHE

Date de publication : 10 oct. 2005

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

Cet article présente la famille des suites automatiques, par définition les suites déterministes, périodiques ou ultimement périodiques, engendrées par des automates. Il s’attarde longuement sur les propriétés et applications des séries formelles sur un corps commutatif, ainsi que sur les alphabets et morphismes employés dans ces suites. Le théorème de Christol, qui stipule l’équivalence entre l’algébricité d’une série formelle à coefficients dans un corps fini et l’automaticité de la suite de ses coefficients, y est largement introduit.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

Auteur(s)

INTRODUCTION

Comment reconnaître si une suite (infinie) binaire est « au hasard » ? La difficulté de la question et le caractère non universel des réponses (au hasard dans quel sens ? pour quel usage ?) font qu’on peut imaginer poser la question à l’envers en quelque sorte et demander ce qu’est une suite « déterministe ».

Parmi les suites déterministes, celles engendrées par des « machines abstraites » semblent les plus faciles à étudier. C’est le cas des suites engendrées par automate fini, encore appelées « suites automatiques », dont une définition informelle pourrait être que ce sont des suites dont le ne terme dépend de la valeur donnée par un automate fini (qu’on pourrait représenter comme une sorte de graphe avec des étiquettes mais dont une définition formelle sera donnée plus loin) dans lequel on entre les uns après les autres les chiffres de l’entier n dans une base entière donnée.

Les suites ainsi construites sont bien sûr déterministes ; certaines d’entre elles peuvent être périodiques ou ultimement périodiques (périodiques à partir d’un certain rang), mais celles qui ne sont pas périodiques présentent la double particularité d’être « faciles » à engendrer mais de pouvoir être « compliquées » (comme pourraient l’être des suites « chaotiques » voire... au hasard).

Dans ce qui suit, nous allons présenter cette famille de suites, en insistant sur les propriétés des séries formelles associées sur un corps fini. Le résultat fondamental (théorème de Christol) a été historiquement un pont important entre la théorie des automates (et donc l’informatique théorique) et la théorie des nombres. Nous citerons aussi, très brièvement, des relations avec d’autres domaines des mathématiques, avec la physique (des quasi-cristaux), voire avec la composition musicale.

L’étude systématique des suites automatiques a commencé avec trois articles d’Alan Cobham entre 1968 et 1972 . Elles ont connu leur essor dans leurs liens avec la théorie des nombres avec un article de Gilles Christol en 1979 , puis un article de Gilles Christol, Teturo Kamae, Michel Mendès France et Gérard Rauzy en 1980 . Leurs développements les plus récents pourront être trouvés dans un livre collectif signé Pytheas Fogg , dans un livre de Friedrich von Haeseler , ainsi que dans un livre de Jeff Shallit et de l’auteur .

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af175


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

5. Quelques autres propriétés et applications des suites automatiques

Les suites automatiques ou leurs généralisations (suites automatiques à plusieurs dimensions, suites morphiques, suites q-régulières...) ont de nombreuses propriétés qui font qu’on les trouve dans plusieurs branches des mathématiques ou de l’informatique théorique. Nous ne ferons ici qu’une promenade fort rapide, renvoyant le lecteur à la bibliographie pour plus d’informations.

Le premier domaine dont nous allons parler est celui de la théorie des nombres. Nous avons vu que les suites q-automatiques sont exactement les coefficients des séries formelles algébriques sur le corps des fractions rationnelles à coefficients dans le corps à q éléments. On peut se demander de quelle sorte de nombres réels les suites automatiques peuvent être les « coefficients » (c’est-à-dire les chiffres dans une base de numération entière donnée). Par exemple la suite de Prouhet-Thue-Morse rencontrée plus haut peut être interprétée comme le développement en binaire (ou en base 10 par exemple) d’un nombre réel θ :

θ := 0, 110100110010...

Quelle est la nature arithmétique de ce nombre ? On sait depuis trois quarts de siècle que ce nombre est transcendant (c’est-à-dire non algébrique). On n’a que depuis cette année une preuve complète que tous les nombres réels dont le développement dans une base entière est une suite automatique sont transcendants ou rationnels (résultat dû à B. Adamczewski, Y. Bugeaud, et F. Luca). En d’autres termes les décimales d’un nombre algébrique irrationnel comme ne peuvent pas être engendrées par un automate fini.

Les suites automatiques ont d’autres propriétés de nature arithmétique ; ont été ainsi étudiées les séries de Dirichlet à coefficients automatiques, la répartition des puissances d’une série formelle de Laurent automatique, la transcendance (via les automates) de séries formelles de Carlitz qui ressemblent à la fonction zêta de Riemann et à la fonction Gamma, etc.

En géométrie discrète les suites automatiques à plusieurs dimensions ont des applications...

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Quelques autres propriétés et applications des suites automatiques
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - ALLOUCHE (J.-P.), SHALLIT (J.) -   Automatic sequences. Theory, Applications, Generalizations  -  , Cambridge University Press, 571 + xvi pages (2003).

  • (2) - CHRISTOL (G.) -   Ensembles presque périodiques k-reconnaissables  -  , Theoretical Computer Science 9, p. 141-145 (1979).

  • (3) - CHRISTOL (G.), KAMAE (T.), MENDÈS FRANCE (M.), RAUZY (G.) -   Suites algébriques, automates et substitutions  -  , Bulletin de la Société Mathématique de France 108, p. 401-419 (1980).

  • (4) - COBHAM (A.) -   On the Hartmanis-Stearns problem for a class of tag machines  -  , IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, p. 51-60 (1968).

  • (5) - COBHAM (A.) -   On the base-dependence of sets of numbers recognizable by finite automata  -  , Mathematical Systems Theory 3, p. 186-192 (1969).

  • (6) - COBHAM (A.) -   Uniform...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS