Documents disponibles écrits par cet auteur

Suite automatiques et séries formelles algébriques / Allouche, Jean-Paul in Techniques de l'ingénieur AFM, Vol. AFM2 (Trimestriel) 

Public ISBD [article]  in Techniques de l'ingénieur AFM > Vol. AFM2 (Trimestriel) . - 1-8 p. Titre : Suite automatiques et séries formelles algébriques Type de document : texte imprimé Auteurs : Allouche, Jean-Paul, Auteur Année de publication : 2007 Article en page(s) : 1-8 p. Note générale : Mathématiques pour l'ingénieur Langues : Français (fre) Mots-clés : Séries  formelles--Algébriques--Machines  abstraites--Systématique Résumé : 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 COBHAM (A.) - On the Hartmanis-Stearns problem for a class of tag machines COBHAM (A.) - On the base-dependence of sets of numbers recognizable by finite automata COBHAM (A.) - Uniform tag sequences. Elles ont connu leur essor dans leurs liens avec la théorie des nombres avec un article de Gilles Christol en 1979 CHRISTOL (G.) - Ensembles presque périodiques k-reconnaissables, puis un article de Gilles Christol, Teturo Kamae, Michel Mendès France et Gérard Rauzy en 1980 CHRISTOL (G.), KAMAE (T.), MENDÈS FRANCE (M.), RAUZY (G.) - Suites algébriques, automates et substitutions. Leurs développements les plus récents pourront être trouvés dans un livre collectif signé Pytheas Fogg PYTHEAS FOGG (N.) - Substitutions in dynamics, arithmetics and combinatorics, dans un livre de Friedrich von Haeseler Von HAESELER (F.) - Automatic sequences, ainsi que dans un livre de Jeff Shallit et de l’auteur ALLOUCHE (J.-P.), SHALLIT (J.) - Automatic sequences. Theory, Applications, Generalizations Note de contenu : Bibliogr. REFERENCE : AF175 ISSN : 1776-0860 Date : Octobre 2005 En ligne : http://www.techniques-ingenieur.fr/base-documentaire/sciences-fondamentales-th8/ [...] [article] Suite automatiques et séries formelles algébriques [texte imprimé] / Allouche, Jean-Paul, Auteur . - 2007 . - 1-8 p. Mathématiques pour l'ingénieur Langues : Français (fre) in Techniques de l'ingénieur AFM > Vol. AFM2 (Trimestriel) . - 1-8 p. Mots-clés : Séries  formelles--Algébriques--Machines  abstraites--Systématique Résumé : 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 COBHAM (A.) - On the Hartmanis-Stearns problem for a class of tag machines COBHAM (A.) - On the base-dependence of sets of numbers recognizable by finite automata COBHAM (A.) - Uniform tag sequences. Elles ont connu leur essor dans leurs liens avec la théorie des nombres avec un article de Gilles Christol en 1979 CHRISTOL (G.) - Ensembles presque périodiques k-reconnaissables, puis un article de Gilles Christol, Teturo Kamae, Michel Mendès France et Gérard Rauzy en 1980 CHRISTOL (G.), KAMAE (T.), MENDÈS FRANCE (M.), RAUZY (G.) - Suites algébriques, automates et substitutions. Leurs développements les plus récents pourront être trouvés dans un livre collectif signé Pytheas Fogg PYTHEAS FOGG (N.) - Substitutions in dynamics, arithmetics and combinatorics, dans un livre de Friedrich von Haeseler Von HAESELER (F.) - Automatic sequences, ainsi que dans un livre de Jeff Shallit et de l’auteur ALLOUCHE (J.-P.), SHALLIT (J.) - Automatic sequences. Theory, Applications, Generalizations Note de contenu : Bibliogr. REFERENCE : AF175 ISSN : 1776-0860 Date : Octobre 2005 En ligne : http://www.techniques-ingenieur.fr/base-documentaire/sciences-fondamentales-th8/ [...]