Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Fondations mathématiques de la théorie des automates (24h, 3 ECTS)

Mathematical Foundations of Automata Theory (24h, 3 ECTS)

Responsable: J.-E. Pin, Directeur de recherches au CNRS

Objectifs

Ce cours s'adresse à des étudiants possédant une grande curiosité, car il fait appel simultanément à plusieurs domaines des mathématiques (combinatoire, algèbre, logique, topologie, etc.), mais sous un angle parfois très éloigné des mathématiques “classiques”.

Introduits vers 1950, les automates finis constituent le modèle le plus élémentaire de machine. Ils sont utilisés dans diverses branches de l'informatique (et plus récemment des mathématiques): compilation, traitement de texte, modélisation et vérification des systèmes, calculs distribués, traitement des langues naturelles, compression de données, codage, etc.

Ce cours se propose de donner les bases mathématiques de la théorie des automates dans les domaines suivants:

- nouveaux concepts mathématiques (parties rationnelles et reconnaissables, monoïdes syntactiques ordonnés, etc.)

- algèbre non-commutative (monoïdes, semi-anneaux, théorie des variétés)

- logique (premier ordre, second ordre monadique)

- théorie équationnelle et topologies profinies

L'objectif est de démontrer dans ce cours quelques grands résultats classiques qui permettront aux étudiants d'accéder aux développements les plus récents et aux applications dans des domaines très variés (langages formels, vérification, logique, complexité des circuits, complexité de communication, modèles finis, etc.). On insistera plus particulièrement sur les liens avec la logique. On ne traitera que le cas des automates travaillant sur des mots finis, mais les extensions aux mots infinis, aux arbres et à d'autres structures pourront être étudiées ultérieurement.

Cours 2014-2015 : intervenants

Intervenants:

- Olivier Carton, Professeur à Paris 7 (12h)

- Jean-Eric Pin, Directeur de recherches au CNRS (12h)

Autres cours complémentaires

  • 2-8 Modélisation et vérification des systèmes temporisés, hybrides ou concurrents
  • 2-9 Vérification de systèmes dynamiques et paramétrés
  • 2-16 Techniques pour la modélisation par automates
  • 2-20-1 Jeux pour la théorie des automates, la vérification et l'internet
  • 2-26-1 Logique, complexité descriptive et théorie des bases de données
  • 2-28-1 Automates d'arbres et applications

Cours 2014-2015 : Plan

Le plan détaillé du cours sera précisé ultérieurement, mais on suivra plus ou moins le plan du support de cours. Cette année deux séances supplémentaires seront organisées sous forme de travaux dirigés.

Langues du cours :

Français ou Anglais suivant l'avis des étudiants. L'anglais sera choisi si au moins un étudiant ne connait pas le français.

Le sujet d'examen sera en français et en anglais.

Les étudiants seront autorisés à rédiger leur examen en français ou en anglais.

Supports de cours :

Description du cours

Voici quelques thèmes abordés dans ce cours:

  • Reconnaissance par morphismes
  • Langages sans étoile et théorème de Schützenberger
  • Calcul séquentiel de Büchi; logiques du premier ordre et du second ordre
  • Logique du successeur, caractérisation algébrique
  • Logique temporelle
  • Langages testables par morceaux
  • Théorème des variétés d'Eilenberg
  • Topologies profinies, théorie équationnelles

Pré-requis

Théorie classique des automates finis et quelques rudiments de logique.

Il est très vivement recommandé aux étudiants peu familiers avec les automates de suivre le cours de tronc commun Automates.

Bibliographie

  • Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008
  • Dexter C. Kozen, Automata and Computability, Springer, 1997
  • Gerard Lallement, Semigroups and Combinatorial Applications, 1979, John Wiley & Sons, Inc.
  • Leonid Libkin, Elements of finite model theory, Springer-Verlag, 2004
  • Dominique Perrin et Jean-Éric Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004.
  • Jean-Éric Pin, Variétés de langages formels, Masson, Paris, 1984.
  • Jean-Éric Pin, Varieties of formal languages, North Oxford, London et Plenum, New-York, 1986.
  • Howard Straubing, Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA, 1994.

Les années précédentes

Équipe pédagogique

Les membres de l'équipe “Automates et applications” du LIAFA

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA