Course: Advanced Automata Theory (Summer Term 2018)

This course covers advanced topics of automata theory and its applications (e.g., computer-aided verification), including:

Intended Audience: The course is intended for computer science or math students with background in logic and theory of computation (familiarity with basic algorithms, logic, and the theory of computation will be assumed). Talk to the instructor if you are not sure if you have the background. Please attend the initial lecture for background material.

Further, students should (1) have "mathematical maturity" (e.g., you should be comfortable with proofs and abstract reasoning), (2) be interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.

General Information

Text Books

The following text books cover most of the material (and much more):

  1. Michael Sipser, Introduction to the theory of computation, MIT Press

  2. Javier Esparza, Automata Theory Lecture Notes

  3. Erich Graedel, Wolfgang Thomas, Thomas Wilke, Automata, Logics, and Infinite Games, Springer

  4. Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press

In addition, we will provide lecture notes, surveys, or research papers for topics not covered in these books.