Automates avancés et Applications

Dans ce cours, nous présentons des résultats théoriques avancés sur la manipulation d'automates finis et de leurs extensions. Nous présentons également les liens entre les familles d'automates considérées et les classes de langages qu'ils reconnaissent ainsi qu'avec les formalismes logiques permettant de décrire des langages.

1. Expression rationnelles et automates finis
2. Lemme de l'étoile pour les langages réguliers
3. Langages Hors Contexte et Automates à pile
4. Minimisation et apprentissage des automates finis déterministes
5. Équivalence entre logique monadique du second ordre et automates finis
6. Logique du premier ordre et langages sans étoile
7. Automates de Büchi

1. Automates
2. Logique