Course: Advanced Automata Theory (Summer Term 2018)

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

• learning of automata
• the connection of automata to second-order logic and Linear Temporal Logic
• automata on infinite words
• automata on trees
• synthesis of reactive systems

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

• Instructor: Dr. Daniel Neider (Room 316, Building 26, MPI-SWS)

• Teaching Assistant: Mahmoud Salamati, Msc (Room 305, Building 26, MPI-SWS)

• Lectures: Tuesdays 08:15-09:45 in 48-210 and Wednesdays 13:45-15:15 in 46-280

• Tutorials: Tuesdays 10:00-11:30 in 86-104

• Office hours: By appointment

• Mailing List: TBA

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.