Combinatoire des automates Home Page

Table des matières

• Combinatoire des automates
• Langages reconnaissables et automates finis
• Produit de concaténation et hiérarchies
• Topologie profinie
• Théorie des codes
• Théorie des semigroupes
• Equations et variétés
• Logique et automates
• Mots infinis
• Autres applications de la théorie des automates
• Livres et articles de synthèse
• Le projet Automate
• Compression de données
• Activités chez BULL
• Responsabilités scientifiques
• Publications
• A propos de ce document ...

Présentation des travaux de recherche

de Jean-Éric Pin

LIAFA, CNRS

La plupart des aspects théoriques de l'Informatique ont pu bénéficier de l'apport de trente siècles de mathématiques : l'algorithmique a mis à profit la puissance de l'analyse mathématique pour évaluer ses performances, la programmation fait un large usage de la logique, la cryptographie utilise des techniques algébriques sophistiquées, le dessin assisté par ordinateur repose sur les principes de la géométrie, etc.. Rien de tout cela pour la théorie des automates, qui a eu rapidement besoin de forger ses propres outils mathématiques. Elle utilise en effet un concept relativement peu étudié par les mathématiciens : les semigroupes. C'est ce constat qui a amené plusieurs chercheurs, au premier rang desquels figurent Schützenberger et Eilenberg, à mener de front l'étude des semigroupes et celle des automates. On ne s'étonnera donc pas de trouver dans mes travaux une partie importante consacrée aux semigroupes. Ce détour mathématique est une étape nécessaire, même pour étudier des problèmes dont l'énoncé laisserait à penser qu'ils peuvent être abordés directement.