Fall 2019 Instructor: Alexandra Kolla

Course description:

Introduces the foundations of automata theory, computability theory, and complexity theory. Shows relationship between automata and formal languages. Addresses the issue of which problems can be solved by computational means (decidability vs undecidability), and Introduces concepts related to computational complexity of problems.

Requisites:

Discrete Structures/ Discrete Mathematics
Undergraduate Algorithms

Relevant Textbooks

Required Text: Introduction to the Theory of Computation, Michael Sipser, 2002. (2nd or 3rd edition).
Other supplemental materials:
Automata and Computability, Dexter C. Kozen.
Automata Theory, Languages, and Computation , Hopcroft, Motwani, and Ullman (3rd edition).
Elements of the theory of computation, Lewis and Papadimitriou (2nd edition).
Online notes and readings distributed by the instructor.

Course Objectives

The objective of this course is provide an introduction to the theory of computation covering the following three branches of theoretical computer science:

Automata Theory

  • Formalization of the notion of problems via formal languages
  • Formalization of the notion of computation using "abstract computing devices" called automata
  • Understanding a hierarchy of classes of problems or formal languages (regular, context-free, context-sensitive, decidable, and undecidable)
  • Understanding a hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)

Computability Theory

  • Understanding Church-Turing thesis (Turing machines as a notion of "general-purpose computers")
  • Understanding the concept of undecidability , i.e., when a problem can not be solved using computers
  • How to show undecidability using the concept of problem reduction

Complexity Theory

  • Complexity classes : how to classify decidable problems based on their time and space requirements
  • Complexity classes P and NP, and Intractability (NP-completeness)
  • How to prove NP-completeness?
  • Space Complexity: NL-completeness and PSAPCE-completeness

Topics Covered

Regular Languages (3 weeks)

  • Deterministic finite-state machines
  • Nondeterministic finite-state machines
  • Regular expressions
  • Properties of regular languages
  • Languages that aren't regular: pumping lemma

Context-Free Languages (2 weeks)

  • Context-free grammars
  • Pushdown automata
  • Properties of Context-free languages
  • Languages that aren't context-free: pumping lemma for CFLs

Computability Theory (4 weeks)

  • Turing machines and their variants
  • Church-Turing thesis
  • Decidable languages
  • Undecidability
  • Proving Undecidability of a given problem using problem reductions
  • Rice's theorem
  • Famous undecidable problems such as Post Correspondence Problem (PCP), Tiling problem, halting problems for multistack and two-counter machines.

Complexity Theory (3-4 weeks)

  • Time and space complexity
  • Complexity classes P and NP, and NP-Completeness
  • Famous NP-complete problems
  • Complexity class PSPACE and Pspace-Completeness
  • Complexity classes L and NL, and NL-completeness

Special Topics (guest lectures and class projects: presentations in Week 16)

  • Monadic Second-Order Logic and Automata (Elements of Finite Model Theory by Leonid Libkin)
  • Regular transformations on words and trees (TBA)
  • Descriptive complexity (Descriptive Complexity by Neil Immerman)
  • Randomized Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Quantum Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Interactive proofs and complexity class IP (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • PCP Theorem and hardness of Approximation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Timed and hybrid Automata (TBA)
  • Probabilistic Automata (TBA)

Grading

The overall grade will be based on a cumulative score computed by adding together the grades from:

  • Weekly assignments (with least two scores omitted)
  • In-class quizzes (three)
  • The final project and presentations
  • Class participation: you are expected to attend the class and to regularly interact with the instructor in the class.