Teaching

Méthodes formelles pour XML: algorithmes & complexité, cours de Master Recherche 2ème année Mathématiques - Informatique (M2RSL), Module "MW", à l'UJF Grenoble (2006-2007)

L'objectif de ce cours est d'introduire le pont théorique entre les méthodes formelles traditionnellement employées dans la vérification de systèmes, et l'étude des fondements de la manipulation de documents structurés, un domaine actuellement en plein essor. Le cours introduit ainsi quelques formalismes communs aux deux domaines (via la connexion logique-automates d'arbre), et leur donne de l'ampleur sous l'angle de leurs applications dans le monde des documents structurés, du Web et de XML.

Spécifiquement, le cours est divisé en deux parties. La première introduit les standards technologiques pour le traitement des documents structurés (XML, XPath, XSLT, etc.). Ensuite, une seconde partie est consacrée aux méthodes formelles proprement dites (formalismes, algorithmes et complexité) qui sont présentées dans le cadre de XML et motivées par les applications concrètes sur le Web d'aujourd'hui (typage des langages de requêtes, contrôle statique de type pour les langages de transformation, etc.). Les supports du cours sont disponibles ci-dessous, ainsi que d'autres références utiles.

1. Standards technologiques pour XML
   1. Traitement des données et documents XML [slides]
   2. Le langage de requêtes XPath [slides]
   3. Le langage de transformations XSLT [slides]

2. Méthodes formelles pour XML: algorithmes et complexité
   1. Introduction [slides]
      • analyse statique
      • complexité
      • langages d'arbre
      • sortes de grammaires d'arbres
      • automates d'arbre
   2. Requêtes et formalismes logiques [slides]
      • requêtes
      • l'approche logique
        • FO
        • MSO
   3. Résolution efficace de problèmes d'analyse statique [slides]
      • le μ-calcul
      • procédure de décision d'un μ-calcul d'arbres finis

 

Back to the list of courses