Intervenants: Florent Jacquemard (cours), Stefan Ciobaca (TD).
Motivations et objectifs du cours
Il s'agit de donner quelques algorithmes de base sur les automates d'arbres (par exemple: le vide est un problème typique de la classe PTIME), mais surtout l'objectif est de montrer comment utiliser les automates d'arbres dans plusieurs domaines d'application.
Ce cours doit donc permettre d'acquérir quelques notions de base qui permettent d'utiliser l'outil automates d'arbres chaque fois que le problème posé s'y prête. C'est notamment le cas pour toute une série de questions qui se posent naturellement en logique monadique de second ordre, comme la recherche de stratégies optimales de réduction, mais aussi pour d'autres problèmes plus exotiques: contraintes ensemblistes, unification rigide, réductibilité close, vérification de protocoles, déductibilité par un attaquant, langages de requêtes, etc.
Nous verrons plusieurs variantes des automates d'arbres: automates sur les arbres finis ou infinis, d'arité fixe ou variable, dont les fils sont ordonnés ou non, automates alternants...
Description du cours
automates d'arbres finis
définition
déterminisme
lemme de pompage, propriétés de clôture
minimisation
problèmes de décision, complexité
logique monadique faible du second ordre à deux successeurs
automates d'arbres infinis
automates d'arbres variadiques ordonnés
automates de haies
logique monadique du second ordre correspondante
langages de schémas XML
automates d'arbres variadiques non-ordonnés
automates de Presburger
logique monadique du second ordre de Presburger
optionel automates alternants et bidirectionnels
optionel notions de languages de relations sur les arbres
optionel représentations d'automates d'arbres par clauses de Horn
optionel automates d'arbres à pile, à mémoire arborescente
Examens :
Partiel: mercredi 18 novembre 2009, 12h45-15h45, rue du Chateau des Rentiers (salle de cours habituelle). Tous documents autorisés.
Examen: mercredi 3 février 2010, 12h45-15h45, rue du Chateau des Rentiers (salle de cours habituelle). Tous documents autorisés.
Langues du cours :
Le cours sera a priori en français.
Cependant, s'il est suivi par des étudiants non francophones et en accord avec l'ensemble des étudiants qui le suivent, ce cours pourra aussi être en anglais.
Le sujet d'examen sera en français, ou en français et en anglais selon demande.
Les étudiants seront autorisés à rédiger leur examen en français ou en anglais.
