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 Conférences, 46 rue d’Ulm
Classes/TD: After each lecture from 15:15-17:00 (15 min break)
Other Dates: Final exam on 23/01/2020. Projects subjects due on 15/11/2019. Project reports due on 03/01/2020. 

 

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

 

By November 15th, 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 (26/09): Course outline. Deterministic and non-deterministic finite automaton. Equivalence of DFAs and NFAs.

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

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

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

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

·       Vacances Toussaint (31/10)

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

·       Lecture 07 (14/11): The halting problem and other undecidable problems. 

·       Lecture 08 (21/11): Rice’s theorem. Post correspondence problem. Decision properties of regular and context-free languages.

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

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

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

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

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

·       Presentations 13-17/01: Reports are due on 03/01/2020. There will be a doodle page to decide on time slots for the presentations. 

·       Final exam (23/01): Salle de Conférences (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 3x + 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