Cours
Logiques, automates et aspects formels de la théorie
des langages
Master Informatique Fondamentale, année 2017-2018
Intervenants
Luigi
Santocanale
et Pierre-Alain
Reynier.
Infos
-
Début du cours : le lundi 4 septembre 2017, à 10h00 (après
la réunion de rentrée).
- Lien vers
la partie
automates du cours.
Emploi du temps
- Lundi 4/09. Logique du premier ordre, syntaxe et
sémantique. Le calcul des séquents.
- Lundi 11/09. Théorèmes de correction et complétude du
calcul des séquents. Théorème d'élimination des
coupures. Indécidabilté de la logique du premier ordre
(I partie).
- Lundi 18/09. Indécidabilté de la logique du premier ordre
(II partie). Logique monadique du II ordre.
- Lundi
24/09. Logique monadique du II ordre (suite). Théories et
fragments décidables de la logique du I ordre : arithmétique
de Pressburger.
- Lundi 02/10. Logique modale. Théories et fragments
décidables de la logique du I ordre : le fragment avec deux
variables.
- Lundi 09/10. Logiques computationnelles. Plus petit
point fixe des fonctions monotones. Théorème de
Knaster-Tarski et théorème de Kleene. Points fixes dans
MSOL et LTL. mu-calcul modal.
- Lundi 16/10. Exemples de formules du mu-calcul modal.
Propriétés de sûreté et vivacité. Jeux de parité.
Le théorème fondamental du mu-calcul.
Docs
La documentation est accessible par ici.
Calcul de la note finale
Note finale = 0.4*CC + 0.6*ET
où
- Contrôle Continu (CC) : deux devoirs maison,
- Examen Terminal (ET) : examen écrit de 3h, début novembre.