Course: Advanced Automata Theory
Summer 2017
Instructor:
Dr. Rupak Majumdar ( rupak@mpisws.org ) Room 414, Building 26 (MPISWS)
Dr. Daniel Neider ( neider@mpisws.org ) Room 315, Building 26 (MPISWS)
Tutorials:
Lectures:
 Tuesdays 08:1509:45 48210 and Wednesdays 13:4515:15 46280
Tutorial: Tuesday 10:0011:30
Office hours: By appointment
Class website: https://wiki.mpisws.org/wiki/Courses/AdvancedAutomataTheory
Mailing list: TBD
Introduction
Syllabus and contents.
We shall study automata on finite/infinite words and trees and their relationship to logic and computeraided verification of systems.
Intended Audience.
Computer science or math students with background in logic and theory of computation. (Familiarity with basic algorithms, logic, and theory of computation will be assumed). Talk to the instructor if you are not sure if you have the background. We shall try to keep the class selfcontained, please attend the initial lecture for background material.
Further, I expect you (1) have "mathematical maturity" (e.g., you should be comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.
Grading
Grading will be based on a written, opennotes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam.
In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class.
Text book
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 shall provide lecture notes, surveys, or research papers for topics not covered in these books.
Homework:
Homework exercises will be handed out approximately every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture.
Teamwork and Academic Honesty:
Students may collaborate on homework assignments, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.
Announcements
 The first lecture is on April 18, 2017.
The written final exam will be held on July 28, 2017 in Room 48208 between 8:30 and 10:30am. You can bring any books or lecture notes you want to the exam. However, you are not allowed to connect to the internet on any device.
Here is a practice exam.
The room 48438 is reserved for exam preparation from Monday, July 24, to Thursday, July 28.
A list of all topics covered in the course is available.
Safra's construction: you should have a broad understanding of Safra's construction, including the underlying ideas, its main steps, and it's complexity. However, we will not ask to construct Safra trees in the exam.
Lecture Notes
We hope to collaboratively create Wikilike lecture notes at https://sandstorm.init.mpg.de/shared/fE1Q2Y28_shnnE9vet1m_xlHI2hUKjdbzlSrYEpX9c
You can find a LaTeX tutorial online, which explains basics and first steps of writing LaTeX documents. Please also consult l2tabu, which is a list of do's and don't for writing LaTeX documents. The comprehensive LaTeX symbol list and the detexify website are useful, too (please contact me prior to importing or changing fonts to make particular symbol work).
Schedule
This schedule is preliminary and subject to change.
# 
Date 
Course topic / lecture 
Homework 
Additional Materials (lecture notes/papers) 

L1 
April 18 
Introduction to the course. Review of finite automata. Basic constructions. 



L2 
April 19 
Further constructions on finite automata. Regular expressions. 
Reading: Sipser 


L3 
April 25 
Review of complexity classes, decision problems on automata 



L4 
April 26 
(Weak) monadic second order logics on words (WS1S). BuchiElgot theorem. 

Reading: MukundNotes Advanced Reading: GraedelThomasWilke Ch 12 







L5 
May 02 
Automata minimization: Homomorphisms. 


L6 
May 03 
MyhillNerode theorem. 



L7 
May 09 
Minimization of DFAs. 



L8 
May 10 
Bisimulation. Reduction of NFAs. 



L9 
May 16 
Learning from examples. Passive learning. 


L10 
May 17 
Angluin's Algorithm (L*). libalf. 









L11 
May 23 
Omega automata: Buchi, coBuchi, Rabin, Streett. 

Reading: BuchiAutomata 

L12 