Automata Theory (Seminar)
In the lecture about theoretical computer science you have seen finite automata, pushdown automata and Turing machines. All three of them operate on finite words. However there are other automata models and automata that do not operate on finite words, but e.g. on infinite words, on nested words, on trees, etc. In this seminar we will have a look at automata models that you have not seen in the lecture on theoretical computer science as well as on related topics.
Course type  Seminar 

Instructors  Prof. Dr. Andreas Podelski, Tanja Schindler (contact person for organisational matters) members of the software engineering group 
Kickoff meeting 
Friday, 23rd of April 2021, 14:00 BigBlueButton in the Ilias system 
Regular meetings (talks) 
Friday 14:00  16:00 (see schedule below) 
Presentation language 
English 
Credits 
3 or 4 ECTS (depending on the PO) 
Course Catalog  Advanced Topics in Automata Theory (Seminar) 
Ilias Course 
Advanced Topics in Automata Theory 
News
 June 10: Topic assignment/schedule updated. The students involved have been notified.
 May 21: Reviews assigned.
 May 04: Topic assignment and schedule published.
 April 23: Deadline for sending an email with your three (or more) favorite topics: Wednesday, April 28, 2012, 12:00 noon.
 April 23: Available topics added.
 April 16: Kickoff meeting announced, Ilias course added.
 April 13, 2021: Webpage online. Please make sure to check for updates before April 18.
Process of the seminar
 You participate in the kickoff meeting, where we present the
available topics.
 You contact the instructors to obtain a topic. You may suggest three of the available topics and provide a priorization for each topic.
 You have a meeting with your supervisor in which we discuss relevant literature and develop a very coarse sketch of your talk (deadline: four weeks before your talk).
 You write a proposal in which you explain what you are going to present in your talk. You submit your proposal via email to your supervisor (deadline: three weeks before your talk).
 You have a meeting with your supervisor in which you get feedback for your proposal (deadline: two weeks before your talk).
 Your proposal is reviewed by two other participants.
 You
write two reviews about other participants' proposals and send them via
email to the supervisor (deadline: one week after you received the
proposal).
 You receive reviews for your proposal (deadline: two weeks before your talk).
 You submit your slides together with an abstract of your talk via email to your supervisor (deadline: one week before your talk).
 You have a meeting with your supervisor in which you get feedback for your slides.
 You give a talk of 30 minutes.
 You attend the talks of all other participants.
Proposals of the talk
The proposal should consist of around five pages in which you explain what you are going to present in your talk. The proposal should contain at least:
 short overview for the reviewers (the reviewers will probably not know your topic)
 structure of your talk
 aspects of the topic that you present (why?) and ignore (why?)
 examples occurring in the talk (why these examples? Is there a running example that can be used for demonstration?)
 which definitions are presented formally? (why?), which definitions are just mentioned informally? (why?)
 which notation is used? (why?)
 which theorems are presented, which of them will be proven (why?), which proofs will be omitted (why?), will you use motivating examples in the proof?
Abstract of the talk
 The abstract consists of one paragraph that summarizes what you present in the talk.
 We will send an invitation for the seminar to all students and members of our chair. This invitation contains the abstracts of all talks.
The talk
 The goal of your talk is that the audience (bachelor and master students, familiar with computer science in general, probably no experts in the topic) has the possibility to learn something new about an interesting topic. How well you achieved this goal will determine the grade of your talk.
 In a seminar you have to show that you are able to present some topic to other people. You do not have to show how well you understood the topic for yourself. How well you understood the topic has no direct influence on your grade, but only how well you presented the topic to the audience.
 You may use and copy any source of information (but do not forget to cite it). If you think your talk is just a "remix" of existing talks tailored to your audience, you might have done a great job. But do not let yourself be fooled by wellstructured and fancy talks found in the web, each talk was prepared to a specific audience.
Review of the proposal
 Give a short summary of the talk based on the proposal (to detect misunderstandings right at the start).
 Be generous with your criticism. It is very unlikely that a student will get a bad grade because you revealed some problems in his/her proposal. However, it is very likely that a student will get a better grade if he/she was able to resolve a problem in his/her talk, thanks to your review.
 Give reasons for your criticism (e.g., "It is not possible to understand Lemma 2 because term foo was not explained."). You are also allowed to give your personal opinions, if you do so mark them as such (e.g., "Theorem 1 is very difficult to understand, in my opinion you should give an example first.").
 The following questions might be helpful to write your review
Is the proposal sufficiently well written to be readable?
Is the appearance and structure of the proposal appropriate?
Is the comprehensibility of the talk supported by relevant examples and figures?
Is the proposed structure of the talk sensible and balanced?
Are all propositions made by the author correct?
Is the line of reasoning concerning the presentation complete and accurate?
Has the author argued his/her case effectively?
Does the author use the common notation and terminology? Where would you suggest something different?
Is the schedule of the author sensible? Do you think the talk will fit into the time slot?
Grade
Your overall grade will be composed according to the following proportion.
 10% grade of your proposal
 20% grade of your reviews
 70% grade of your talk
Topics & literature
Pattern Matching
 Talk: Verena
 Supervisor: Jochen Hoenicke
 Reviewers: Alexander, Leonardo
 Time Slot: A
 Starting Literature: Automata Theory  An algorithmic Approach by Javier Esparza, Chapter 5
Transducers
 Talk: Katharina
 Supervisor: Dominik Klumpp
 Reviewers: Melissa, Anand
 Time Slot: A
 Starting Literature: Automata Theory  An algorithmic Approach by Javier Esparza, Chapter 6
Finite Universes
 Talk: Alexander
 Supervisor: Tanja Schindler
 Reviewers: Melissa, Leonardo
 Time Slot: B
 Starting Literature: Automata Theory  An algorithmic Approach by Javier Esparza, Chapter 7
Automata and Logic
 Talk: Melissa
 Supervisor: Jochen Hoenicke
 Reviewers: Alexander, Prasad
 Time Slot: B
 Starting Literature: Automata Theory  An algorithmic Approach by Javier Esparza, Chapter 9
Emptiness Check [for Büchi automata]
 Talk: Leonardo
 Supervisor: Andreas Podelski
 Reviewers: Anand, Faisal
 Time Slot: C
 Starting Literature: Automata Theory  An algorithmic Approach by Javier Esparza, Chapter 13
Pushdown Automata
 Talk: Anand
 Supervisor: Andreas Podelski
 Reviewers: Prasad, Carl Marvin
 Time Slot: C
 Starting Literature: Applied Automata Theory by Wolfgang Thomas, Chapter 4
Petri Nets
 Talk: Prasad
 Supervisor: Matthias Heizmann
 Reviewers: Katharina, Faisal
 Time Slot: D
 Starting Literature: Applied Automata Theory by Wolfgang Thomas, Chapter 6
Visibly Pushdown Automata
 Talk: Faisal
 Supervisor: Matthias Heizmann
 Reviewers: Verena, Carl Marvin
 Time Slot: E
 Starting Literature: Wikipedia, Visibly pushdown languages, Adding nesting structure to words
Learning Finite Automata
 Talk: Carl Marvin
 Supervisor: Jochen Hoenicke
 Reviewers: Verena, Katharina
 Time Slot: E
 Starting Literature: Learning regular sets from queries and counterexamples
Schedule
Each topic/talk has a group letter assigned. We have five groups in total.
The following table contains the deadlines for the groups. Please note that "Review" stands for the review deadline for the specific group's proposals. Each seminar student has to write reviews for two other students.
Date  Outline  Proposal  Review  Slides  Talk 

21. 05. 2021 
A 

28. 05. 2021 
Pentecost Break  
04. 06. 2021 
B 
A 

11. 06. 2021 
C 
B 
A 

18. 06. 2021 
D 
C 
B 
A 

25. 06. 2021 
E 
D 
C 
B 
A 
02. 07. 2021 
E 
D 
C 
B 

09. 07. 2021 
E  D  C  
16. 07. 2021 
E  D  
23. 07. 2021 
E 