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.
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
The following text books cover most of the material (and much more):
Michael Sipser, Introduction to the theory of computation, MIT Press
Javier Esparza, Automata Theory Lecture Notes
Erich Graedel, Wolfgang Thomas, Thomas Wilke, Automata, Logics, and Infinite Games, Springer
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.