Logique et automates

Enseignant

Emplois du temps

6 semaines, du 28 octobre au 5 novembre.

mardi 10h15-12h15, bat. A10, SAC5

vendredi 10h15-12h15, bat. A10, SAC4

Transparents

Semaine1.ps, Semaine1.pdf

Semaine2.ps, Semaine2.pdf

Semaine3.ps, Semaine3.pdf

Semaine4.ps, Semaine4.pdf

Semaine5.ps, Semaine5.pdf

Semaine6.ps, Semaine6.pdf

Examen.ps, Examen.pdf

Objectifs

Introduction à la theorie des automates et à la calculabilitié. Presentation des connections entre les deux et la logique.

Pré-requis

Programme

• Ensembles ordonnés, induction.
• Automates finis.
• Logique du premier ordre.
• Automates sur structures infinies, logique monadique du seconde ordre.
• Calculabilité.
• Complexité.

Bibliographie et références Internet

• A. Arnold, I. Guessarian, Mathématiques pour l´informatiques (Prentice-Hall, Masson, 1996).
• Autebert, Calculabilité et décidabilité, Masson, 1992
• H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic (Springer-Verlag, 1984).
• J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979).
• D. Kozen, Automata and Computability (Springer-Verlag, 1997).
• C.H. Papadimitriou, Computational Complexity (Addison Wesley, 1994).
• I. Walukiewcz, Automata and logic, Notes from EFF Summer School'01 ps.

Contrôle des connaissances

• Examen écrit: 3h
• Contrôle continue