FORMAL LANGUAGES, COMPUTABILITY, AND COMPLEXITY

 

Lecturer: Michel Abdalla (michel.abdalla@ens.fr)
Teaching Assistant: Nathan Grosshans (nathan.grosshans@ens.fr)
Lectures: Thursdays 13:15-15:00 at Salle des Actes, 45 rue d’Ulm
Classes/TD: After each lecture from 15:15-17:00 (15 min break)
Other Dates: Mid-term on 15/11. Final exam on 24/01. Project reports due on 22/12. 

 

Lectures will be in English. The classes by Nathan will be in French. An outline of the course contents is given below.

 

By October 31st, you will need to decide on a project topic. A preliminary list of possible topics is given below and you are welcome to suggest topics of your own choice. The project presentation and the project report can be in English or French. 

 

References

 

Exercise Sheets: See here.  

Lecture Notes:

·       Regular and context-free languages.

·       Computability.

 

Contents

·       Lecture 01 (20/09): Course outline. Deterministic and non-deterministic finite automaton. Equivalence of DFAs and NFAs.

·       Lecture 02 (27/09): Regular expressions and equivalence with NFAs. Closure properties.

·       Lecture 03 (04/10): The pumping lemma. Minimization of DFAs.

·       Lecture 04 (11/10): Context-free grammars. Derivations and parse trees. Ambiguity. Chomsky normal form. 

·       Lecture 05 (18/10): Closure properties of CFLs. Pushdown automata and equivalence with CFGs. Pumping Lemma for CFLs.

·       Lecture 06 (25/10): Turing machines. The Church-Turing thesis. Universal TMs. 

·       Vacances Toussaint (01/11)

·       Lecture 07 (08/11): The halting problem and other undecidable problems. Rice’s theorem. 

·       Mid-term exam (15/11)

·       Lecture 08 (22/11): Post correspondence problem. Decision properties of regular and context-free languages. Undecidability of logical theories.

·       Lecture 09 (29/11): Time complexity: P, NP, and coNP. NP-completeness.

·       Lecture 10 (06/12): NP-completeness of SAT. Other complete problems.

·       Lecture 11 (13/12): Space complexity. Savitch’s theorem. PSPACE-completeness. Classes L and NL, co-NL. NL=coNL.

·       Lecture 12 (20/12): Circuit complexity. Randomized algorithms. Classes BPP, RP, coRP, and ZPP.  BPP in P/poly.

·       Lecture 13 (10/01): Cryptography. One-way functions. Pseudorandom generators. The Goldreich-Levin theorem.

·       Presentations 14-18/01: Reports are due on 22/12. There will be a doodle page to decide on time slots for the presentations. 

·       Final exam (24/01): Salle des Actes (3 Hours)

 

 

Presentation Topics

Email me if you’d like to propose your own topic(s). 

1.     Repetition-Free Sequences

2.     Moore and Mealy Machines

3.     Other Algorithms for DFA Minimization

4.     Deterministic Context-Free Languages

5.     Context-Sensitive Languages

6.     Greibach Normal Form

7.     Parikh’s Theorem

8.     The CYK Algorithm

9.     Tree Automata

10.  WSkS and Monadic Logics

11.  Infinite Automata

12.  Cellular Automaton

13.  Recursive Functions

14.  Random-Access Machines

15.  Lambda Calculus

16.  Fast-Growing Functions 

17.  Kolmogorov complexity

18.  The Arithmetic Hierarchy

19.  Presburger Arithmetic

20.  Undecidability of the Generalized 3+ 1 Problem

21.  Undecidability of Tilings of the Plane

22.  The Unexpected Examination Paradox

23.  Gödel’s Incompleteness Theorems

24.  Topics in Kolmogorov Complexity

25.  Turing Degrees

26.  Blum’s Speedup Theorem

27.  Ladner’s Theorem

28.  Complexity of Decision versus Search

29.  The Polynomial Hierarchy

30.  Barrington’s Theorem

31.  Class #P

32.  IP=PSPACE

33.  Complexity of Games

34.  Parity Is Not in AC0

35.  Relativization and Natural Proofs Barrier

36.  Communication Complexity

37.  PAC Learning

38.  Learning and Languages

39.  Evolvability

40.  Hardness Amplification

41.  Pseudorandom Functions

42.  Zero-Knowledge Protocols

43.  Quantum Computation

44.  Average-Case Complexity

45.  The (Other) PCP Theorem