Suites automatiques et algébricité de séries formelles

Mercredi 16/02/2011 – 17h00

Le but de ce cours-conférence est de présenter certains liens entre la théorie des nombres, la théorie des langages formels et la géométrie discrète. Bien plus que de présenter des thématiques cloisonnées et indépendantes, nous souhaitons mettre à l’avant-plan les interactions fructueuses et non triviales existant entre ces différents domaines de recherche.

Ainsi, les suites automatiques étudiées en particulier par Cobham au début des années 1970 permettent-elles de caractériser les séries formelles algébriques en caractéristique positive (c’est un théorème de Christol en 1979, complété en 1980 dans un article de Christol, Kamae, Mendès France et Rauzy).

Un autre exemple est un résultat récent de H. Derksen qui stipule que l’ensemble d’annulation d’une suite linéaire récurrente sur un corps de caractéristique positive possède une structure qui s’interprète parfaitement dans le formalisme de la théorie des automates ; ceci contribuant notamment à l’obtention de preuves effectives.

Dans le même registre, les liens entre combinatoire des mots et approximations diophantiennes sont remarquables. Par exemple, la transcendance de certains nombres réels peut se déduire de propriétés combinatoires dont jouissent leurs développements dans une base entière.

De même, un théorème fondateur dû à A. Cobham montre que la reconnaissance par automate fini du langage formé des représentations en base entière des éléments d’un ensemble d’entiers dépend fortement de la base choisie. Ces ensembles reconnaissables d’entiers sont considérés comme particulièrement simples si l’on s’intéresse à la complexité des machines requises pour les décrire. Ce théorème de Cobham trouve, par exemple, des applications en vérification algorithmique de systèmes utilisant des variables non bornées.

Enfin, en géométrie discrète, la construction et l’étude de plans discrets ou plus généralement de surfaces discrétisées font intervenir des développements simultanés en fractions continues ou encore des suites engendrées par morphisme itéré.

Les leçons du Collège Belgique sont accessibles à tous, gratuitement et sans inscription préalable.


Responsables

Nom & prénom

   

Fonction

Jean Mawhin

   

Responsable académique

   

Michel Rigo

   

Coordinateur

   

Jean-Paul Allouche

   

Conférencier

   

Michel Rigo

   

Conférencier

   

Matière

Matière

Sciences et technologies

Cours-conférence

Arithmétique, automates et géométrie discrète


Programme

Heure

   

Leçon

   

Conférenciers

17h00 - 19h00

   

Suites automatiques et algébricité de séries formelles

   

Jean-Paul Allouche
Michel Rigo

     

Lieu

Site

Palais des Académies

Immeuble

 

Local

Salle à déterminer

Adresse

Rue Ducale 1, 1000 Bruxelles


Galerie


Top