Computability and Definability, 236331
Teachers:
Prof. J.A. Makowsky (Lecture), E. Ravve (Projects and exercises)
Textbooks
- [EFT]
H.D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic,
2nd ed.,
Springer 1994.
- [EF]
H.D. Ebbinghaus and J. Flum, Finite Model Theory,
Springer 1995.
- [Pa]
C. Papadimitriou, Computational Complexity,
Addison Wesley 1994.
- [Ma1]
J.A. Makowsky,
Lecture Notes of Logic for Computer Science 1, part I.
- [Ma2]
J.A. Makowsky,
Lecture Notes of Logic for Computer Science 1, part II.
- [Ma3]
J.A. Makowsky,
Draft chapter of Interpretations, Translations and
Reductions (for the Handbook of Logic in CS)
Slides of course given at ESSLLI'97
An advanced course on the same topics
(without Pebble games) was given at
the European Summer School of Logic, Language and
Information in Aix-en-Provence,
August 11-22 1997.
These slides are stored in ps-format and
are printed as three slides per page (A4)
with additional space for notes. There 286 slides.
Prelude ,
Lecture 1 ,
Lecture 2 ,
Lecture 3 ,
Lecture 4 ,
Lecture 5 ,
Lecture 6 .
Abstracts of Lectures W97/8
- Lecture 1 (2.11.97)
- Lecture 2 (9.11.97)
- Lecture 3 (16.11.97)
- Lecture 4 (23.11.97)
- Lecture 5 (30.11.97)
Projects 1997/8
- Prepare library of examples of games separting properties.
(Gaifman paper)
- Monadic NP
- Prepare survey on definability of connectivity.
- Prepare survey on definability of planarity.
- Prepare survey on definability of hamiltonicity.
- Prepare survey on definability of three colorability.
Abstracts of Lectures W96/7
Projects 1996/7
Topics for research (M.Sc or Ph.D)
- Formulate pumping lemmas for MSOL
- The definability of HEX
- SOL definable properties of matrices over finite fields
- Invariant definability and circuit complexity I (Ajtai papers)
- Invariant definability and circuit complexity II The classes
P/poly, NL/poly etc..