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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-1-2 [2011/07/12 14:22] (current)
baptiste created
Line 1: Line 1:
 +
 +====== Automates avancés et applications ======
 +~~NOTOC~~
 +
 +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 ==== 
 +<html>
 +<table border="2">
 +<tr><td>E. Asarin</td>
 +<td>PU</td>
 +<td>Université Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>O. Carton</td>
 +<td>PU</td>
 +<td>Université Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>Ch. Choffrut</td>
 +<td>PU</td>
 +<td>Université Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>I. Klimann</td>
 +<td>MC</td>
 +<td>Université Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +<tr><td>Ch. Prieur</td>
 +<td>MC</td>
 +<td>Université Paris 7</td>
 +<td>LIAFA</td>
 +</tr>
 +</table>
 +</html>
 +
 +==== Les années précédentes ====
 +
 +  * [[2009-2010-C-1-2|Année 2009-2010]]
 +  * [[Année 2008-2009-C-1-2|2008-2009]]
  
 
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