Descriptif

Ce cours s'intéresse à des notions avancées de théorie des automates et langages réguliers, et présente un tour d'horizon de leurs connexions avec d'autres disciplines comme l'algorithmique et la logique, ainsi que leurs extensions aux arbres et aux classes structurées de graphe.

Dans un premier temps, le cours se concentre sur les automates de mots, avec notamment des variantes des formalismes d'automates classiques, des notions d'algèbre des semigroupes, et des applications à l'algorithmique du texte.

Dans un second temps, le cours présente le formalisme des automates d'arbres et son lien avec la logique monadique du second ordre, puis étend à la notion de largeur d'arbre et la programmation dynamique sur des décompositions arborescentes de graphes.