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.
Combinatoire des automates
Home Page
Table des matières
Présentation des travaux de recherche
Jean-Éric PIN, 5 Octobre 1996