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

Automates avancés et applications

Resp. : E. Asarin

Objectifs

Les automates sont extrêmement utiles pour modéliser des phénomènes complexes et pour développer des algorithmes efficaces sur ces modèles. Le plus souvent, on utilise des extensions de la notion classique d'automate fini. Ces extensions peuvent porter sur l'objet à reconnaître : mot infini, arbre, fonction, relation, ...ou sur la méthode de reconnaissance : non déterminisme, alternance, condition d'acceptation, ...Ces généralisations d'automates sont utilisées avec succès pour de nombreuses applications : vérification automatique de systèmes, calcul de propriétés quantitatives, compression, algorithmique du génôme, algorithmique du texte, systèmes de numération, ...

L'objectif du cours est de présenter certaines extensions des automates et certaines de leurs applications.

Plan du cours

  • Modélisation de processus infinitaires : mots infinis, automates
    sur les mots infinis, conditions d'acceptation (Büchi, Muller, parité,
    ...), déterminisme, expressions rationnelles.
  • Minimisation des automates déterministes sur les mots finis,
    relations de simulation sur les automates non déterministes,
    application à la réduction d'automates non déterministes sur les
    mots finis ou infinis.
  • Automates alternants pour les mots finis ou infinis : équivalence
    avec les automates classiques, automates alternants faibles et application
    à la déterminisation des automates de Büchi.
  • Logiques du premier ordre, logiques monadiques du second ordre
    ou logiques temporelles pour spécifier les propriétés des systèmes,
    lien avec les automates sur les mots finis ou infinis, application à
    la vérification automatique.

Pour compléter, on traitera certains des points suivants :

  • Modélisation de propriétés quantitatives : semi-anneaux, séries
    formelles, automates à multiplicité, théorème de Schützenberger, applications.
  • Fonctions et relations rationnelles : caractérisation des
    relations reconnaissables (Théorème de Elgot et Mezei), problèmes de
    décidabilité des relations rationnelles, décidabilité de l'égalité de
    deux fonctions rationnelles et de la fonctionnalité d'une relation rationnelle.
  • Arbres : automates d'arbres (ascendants et descendants),
    Langages d'arbres reconnaissables, propriétés de clôture,
    expressions régulières, caractérisations logiques, applications
  • Systèmes de numération : arithmétique dans des bases non classiques
    (Avizienis, Fibonacci, ...), problème d'ambiguïté et de recherche de
    représentants canoniques, complexité des opérations arithmétiques dans
    ces bases.

Pré-requis

Automates finis.

Bibliographie

  • G. Rozenberg and A. Salomaa Eds.,
    Handbook of Formal Languages
    (volumes 1, 2, 3)
    Springer, 1997.
  • D. Perrin et J.-E. Pin,
    Infinite Words,
    Pure and Applied Mathematics vol. 141,
    Academic Press, 2003.
  • M. Crochemore, C. Hancart and T. Lecroq,
    Algorithmique du texte,
    Vuibert, 2001

Équipe pédagogique

E. Asarin PU Université Paris 7 LIAFA
O. Carton PU Université Paris 7 LIAFA
Ch. Choffrut PU Université Paris 7 LIAFA
I. Klimann MC Université Paris 7 LIAFA
Ch. Prieur MC Université Paris 7 LIAFA

Les années précédentes

 
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