Automata Theory

News

• Talks should be 30 minutes for the Seminar and 25 minutes for the Proseminar. Note that these constraints are mandatory and you should not deviate more than 5 minutes from schedule.
  
• The topics have been assigned. Please contact your supervisor before you read through the literature. We want to assign a specific subtopic to each of you.
• If you want to participate in the proseminar then please choose three of the topics listed below and send your choices sorted according to your preferences to Christian Schilling by Sunday evening (26th April). If you have another favorite topic in mind, you may additionally list it and we will discuss whether it is suitable.
  
• If you want to participate in the seminar then please choose one of the topics listed below and send your choice to Christian Schilling by Sunday evening (26th April). If you have another favorite topic in mind, you may additionally list it and we will discuss whether it is suitable.
• Starting from Wednesday evening we will list possible seminar topics on this website. If you have a suggestion for a topic that should be covered by our seminar please let us know as soon as possible and we will (try to) include it in our list.
• The kick-off meeting takes place on Tuesday, 21 April, at 12-14 s.t.
  

Process of the seminar

• Participate in the kick-off 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 (schedule see below).
  
• 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.

The talk

• The goal of your talk is that the audience (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 well-structured 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.
  

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 30 min 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 for the Proseminar "Introduction to Automata Theory"

There is not a one-to-one 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.

Alternating Finite Automata I (Group A)

• Literature: tba
• Talk by: Felix
  
• Supervisor: Alexander Nutz
• Reviewers: Maximilian, Zhiwei

Alternating Finite Automata II (Group A)

• Literature: tba
• Talk by: Michael S.
  
• Supervisor: Alexander Nutz
  
• Reviewers: Maximilian, Zhiwei

Automata and Logical Specifications (Group B)

• Literature: Applied Automata Theory (Chapter 1)
• Talk by: Marc
  
• Supervisor: Christian Schilling
• Reviewers: Daniel Z., Jannis
  

Star Height (Group B)

• Literature: Wikipedia, Applied Automata Theory (Chapter 1), On the star height of rational languages. A new proof for two old results
• Talk by: Jannis
• Supervisor: Christian Schilling
• Reviewers: Daniel Z., Michael B.
  

Congruences and Minimization (Group B)

• Literature: Applied Automata Theory (Chapter 2)
• Talk by: Sven
  
• Supervisor: Christian Schilling
• Reviewers: Jannis, Michael B.

Tree Automata (Group C)

• Literature: Applied Automata Theory (Chapter 3)
• Talk by: Maximilian
  
• Supervisor: Alexander Nutz
  
• Reviewers: Marc, Matthias

Pushdown and Counter Systems (Group C)

• Literature: Applied Automata Theory (Chapter 4)
• Talk by: Zhiwei
  
• Supervisor: Christian Schilling
• Reviewers: Matthias, Sven
  

Nested Word Automata (Group D)

• Literature: Wikipedia, Nested Words, Adding nested structure to words
  
• Talk by: Michael B.
  
• Supervisor: Christian Schilling
• Reviewers: Felix, Michael S.
  

Petri Nets (Group D)

• Literature: Applied Automata Theory (Chapter 6)
• Talk by: Daniel Z.
  
• Supervisor: Christian Schilling
• Reviewers: Felix, Michael S.

Omega Automata (Group E)

• Literature: Automata on Infinite Objects, ω-Automata, The complementation problem for Büchi automata with applications to temporal logic
• Talk by: Matthias
  
• Supervisor: Matthias Heizmann
• Reviewers: Marc, Sven
  

Topics for the Seminar "Automata Theory"

There is not a one-to-one 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.

Reducing the size of Büchi Automata (Group E)

• Literature: Wikipedia, Advanced automata minimization, Fair Simulation Minimization Fair Simulation Relation,   Parity Games, and State Space Reduction for Büchi Automata
  
• Talk by: Daniel T.
  
• Supervisor: Matthias Heizmann
  
• Reviewers: Jeremias, Marcel
  

Antichains in Automata Theory (Group F)

• Literature: Wikipedia, Antichains: A New Algorithm for Checking Universality of Finite Automata, Antichain Algorithms for Finite Automata, When Simulation meets Antichains
• Talk by: Jeremias
  
• Supervisor: Matthias Heizmann
• Reviewers: Daniel T., Marcel
  

Deciding Monadic Second Order Logic Using Automata (Group F)

• Literature: The MONA tool , Nested Antichains for WS1S (especially Section 4), Decidability of S1S and S2S , The Complexity of Translating Logic to Finite Automata, 
• Talk by: Marcel
  
• Supervisor: Matthias Heizmann
• Reviewers: Daniel T., Jeremias

Schedule

We have six meetings for the talks, hence six groups.

The following table contains the deadlines for the groups. Please note that "review" stands for the review deadline for the specific group. Each student has to write reviews for two other students.