Université Paris Diderot - Master 1 Ingénierie Informatique, MPRI1, etc

Automates avancés (2009)

Equipe pédagogique

Chargé de cours : Eugene Asarin

Chargé de TD :  Peter Habermehl

Objectifs

L'objectif de ce cours consiste à montrer l'intérêt et l'utilité des automates en tant que modèles comportementaux et surtout en tant que structures de données/outils algorithmiques. Pour les situations ou les automates finis sur les mots finis, que vous connaissez déjà bien, ne suffisent pas nous présenterons les variantes utiles des automates ( $\omega$), étudierons leurs propriétés de base et montrerons leurs applications.

Dans ce cours nous privilégions la couverture à la profondeur. Nous souhaitons que chaque étudiant(e) acquière les bonnes intuitions concernant les applications des automates, qu'il (elle) ait un arsenal des outils basés sur les automates. Par contre, l'approfondissement vers la ``vraie'' théorie des automates se fera dans plusieurs cours de M2.

Plan de cours

Le programme change un peu chaque année. Ainsi en 2009, ni les jeux, ni la recherche de motifs, ni les automates temporisés ne sont plus au programme, par contre la méthode d' apprentissage d'Angluin a été ajoutée.

  1. Automates finis – rappels.
    1. Mots et langages
    2. Automates déterministes-nondéterministes-epsilon. Equivalence.
    3. Langages réguliers. Opérations sur les langages (en utilisant les automates).  Algorithmes de décision.
    4. Expressions régulières- Thm de Kleene
    5. Minimisation et Thm de Myhill-Nerode
    6. Langages non-réguliers
  2. Apprentissage des langages réguliers (algorithme d' Angluin)
  3. Automates finis comme structures de données
    1. BDD
    2. Décision de l’arithmétique de Presburger
  4. Caractérisations alternatives des langages réguliers  et oméga-réguliers
    1. Logique MSO(S,<) et son équivalence expressive aux automates
    2. Les langages star-free et leurs caractérisations: expressions sans-étoiles, langages apériodiques, automates non-comptants, logiques FO(S,<) et LTL.
  5. Mots infinis
    1. Omega-mots et omega-langages
    2. Automates de Buchi
    3. Langages omega-réguliers et leurs propriétés (opérations, procédures de décision)
    4. Expressions  oméga-régulières et et automates de Büchi : équivalence
    5. Exemples des langages non-oméga-réguliers et des langages non-déterminisables
    6. Logique MSO sur les mots infinis.

Méthodes importantes vues en cours, TDs et partiels:

Contrôle de connaissances (et révisions)

Documents utiles

Pages web des TDs de Peter Habermehl.

Notes manuscrites succinctes de ce cours du 2007 par Emilie Diot.

Pour réviser la théorie élémentaire:

John E. Hopcroft, Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, Pearson/Addison Wesley, 2007

Pour comprendre les BDDs:

R.Bryant Graph-Based Algorithms for Boolean Function Manipulation, 1986

Pour comprendre l' algo d'Angluin

Dana Angluin: Learning Regular Sets from Queries and Counterexamples Inf. Comput. 75(2): 87-106 (1987), ou les transparents de  Vasin Punyakanok

Un livre un peu difficile (voir chapitres 1 et 8)

Dominique Perrin, Jean-Eric Pin. Infinite words: automata, semigroups, logic and games. Academic Press, 2004

Un livre facile

Gopalakrishnan. Computation Engineering. Springer, 2006

Annales

Attention - le programme change un peu chaque année

Pré-requis

Un cours des automates et langages.