Automata Theory
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 / Proseminar 

Instructors  Matthias Heizmann, Alexander Nutz, Christian Schilling 
Kickoff meeting 
Wednesday, 20 April 2016, 16:00  18:00 c.t., building 052, room 02017 
Presentations  weekly Wednesday 16:00  18:00 c.t., building 052, room 02017 (start: 22 June 2016) 
Presentation language 
English (Seminar) / German (Proseminar) 
Credits 
4 (Seminar) / 3 (Proseminar) 
Course Catalog  Automata Theory (Seminar) Automatentheorie (Proseminar) 
News
 May 5: The reviewers have been assigned.
 April 27th: The topics have been assigned and a schedule has been added. Please contact your supervisor to clarify the relevant literature and to make an appointment.
Process of the seminar
 Participate in the kickoff meeting, where we present the available topics. Feel free to hand in your favorite topic in advance.
 Contact the instructors to obtain a topic. You may suggest a topic by yourself, pick one of the suggested topics, or find a topic suitable for you in a discussion with your supervisor.
 Have a meeting with your supervisor in which we discuss relevant literature and develop a very coarse sketch of your talk. (in the first weeks of the semester).
 You write a proposal in which you explain what you are going to present in your talk.
 You write an abstract of your talk.
 You submit your abstract and your proposal via email to the instructors (deadline: three 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 instructors (deadline: one week after you received the proposal).
 You receive reviews of your proposal (deadline: two weeks before your talk).
 You submit your slides via email to the instructors (deadline: one week before your talk).
 You have a short meeting with the instructors in which you get feedback for your slides.
 You give a ca. 30 min (Seminar) / 25 min (Proseminar) talk.
 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 may contain e.g.:
 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
 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.
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 talk. 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?
The talk
 The goal of your talk is that the audience (bachelor or 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 tailored to a specific audience.
 If you agree we put your slides on this website. Keep in mind that if you have copied images in your slides this might not be possible any more (copyright restrictions). Of course, it will not have any effect on your grade whether we may publish your slides or not.
Formalities
We have the following criteria for successfully passing the course.
 Proposal: 46 pages in 12pt (not counting figures)
 Review: 12 pages in 12pt
 meet all deadlines
 give a talk
 attend all other talks
Grade
If you need a grade, it will be composed according to the following proportion.
 10% grade of your proposal
 20% grade of your reviews
 70% grade of your talk
Topics
There is not a onetoone correspondence between seminar talks and topics. Several students may give talks on the same topic, but present different aspects. The suggested literature should give you a first impression of the topics. We assign the exact literature in cooperation with you after you stated your preferences for the topic.
Some of the papers are only available via the network of our university (e.g., via vpn). If you have some problem accessing the papers, please ask us.
Topics for the Proseminar "Introduction to Automata Theory"
(A) Büchi automata
 Literature: Automata theory  An algorithmic approach (Chapter 11 Section 12), Automata on Infinite Objects (Chapter I Section 12)
 Talk by: Jianlan
 Supervisor: Christian Schilling
 Reviewers: Chau, Ivo
(A) Minimization of Büchi automata
 Literature: Minimising deterministic Büchi automata precisely using SAT solving, Mechanizing the Minimization of Deterministic Generalized Büchi Automata (Section 3)
 Talk by: Ivo
 Supervisor: Christian Schilling
 Reviewers: Jianlan, Lukas
(B) Syntactic monoid
 Literature: Applied Automata Theory (Chapter 2.4)
 Talk by: Teresa
 Supervisor: Christian Schilling
 Reviewers: Chau, Lukas
(B) LR(1) grammars
 Literature: LR(k)Analyse für Pragmatiker
 Talk by: Lukas
 Supervisor: Alexander Nutz
 Reviewers: Ivo, Teresa
(C) Tree automata
 Literature: Tree Automata  Techniques and Applications, (Chapter 1)
 Talk by: Chau
 Supervisor: Alexander Nutz
 Reviewers: Jianlan, Teresa
Not assigned
Automata and MSO logic
 Literature: Automata theory  An algorithmic approach (Chapter 9)
Petri Nets
 Literature: Applied Automata Theory (Chapter 6), Recent and simple algorithms for Petri nets
Don't care words
Ogden's lemma
 Literature: Wikipedia, A helpful result for proving inherent ambiguity
Parikh's theorem
Contextsensitive languages
 Literature: Wikipedia, Formal languages (Chapter 5), Nondeterministic Space is Closed Under Complementation
Topics for the Seminar "Automata Theory"
(C) Tree automata

Literature: Tree Automata  Techniques and Applications, (Chapter 1)
 Talk by: Frank
 Supervisor: Alexander Nutz
 Reviewers: Moritz, Saskia
 Slides: Eigenschaften und Minimierung von Baumautomaten
(D) Automata and MSO logic
 Literature: Automata theory  An algorithmic approach (Chapter 9 and Chapter 15)
 Talk by: Teresa
 Supervisor: Matthias Heizmann
 Reviewers: Claus, Saskia
(D) Probabilistic automata
 Literature: Bounded error probabilistic finite state automata
 Talk by: Saskia
 Supervisor: Matthias Heizmann
 Reviewers: Frank, Teresa
(E) Petri Nets
 Literature: Applied Automata Theory (Chapter 6), Recent and simple algorithms for Petri nets, Unfoldings  A PartialOrder Approach to Model Checking, An improvement of McMillan's Unfolding Algorithm
 Talk by: Claus, Moritz
 Supervisor: Matthias Heizmann
 Reviewers: Claus, Frank, Moritz, Teresa
Not assigned
Minimization of Büchi automata
 Literature: Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata, Advanced automata minimization
DAG automata
 Literature: Automata on DAG Representations of Finite Trees, Closure Properties and Decision Problems of Dag Automata
Parikh's theorem
Schedule
We have five meetings for the talks, hence five groups (AE, see topics).
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 student has to write reviews for two other students.
Date  Proposal  Review  Slides  Talk 

June 1st 
A  
June 8th  B  A  
June 15th  C  B  A  
June 22nd  D 
C  B 
A 
June 29th 
E 
D 
C  B 
July 6th  E 
D 
C  
July 13th  E  D  
July 20th 
E 