Automata Theory

News

• 26.04.2013 Revised version of Website is online. The information on the website is updated according to our decisions in the kick-off meeting.
  

Time, Date and Location

The talks of Automata Theory and all other seminars of our chair will be held in July from Mon 22nd to Wed 24th in room 02-017 of building 52. You received a detailed schedule via email. Participation in all Automata Theory talks is mandatory.

Process of the seminar

• Contact Matthias to obtain a topic. You may suggest a topic by yourself, pick one of the suggested topics below, or find a topic suitable for you in a discussion with Matthias.
• Have a meeting with Matthias 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 Matthias. (Deadline: 23.06.2013)
  
• Your proposal is reviewed by two other participants.
• You write two reviews about other participants proposals and send them via email to Matthias (Deadline: 05.07.2013)
  
• You receive reviews of your proposal. (06.07.2013)
  
• You submit your slides via email to Matthias. (Deadline 14.07.2013)
• You have a short meeting with Matthias in which you get feedback for your slides (15.07.2013 - 19.07.2013)
  
• You give a ca. 30 min talk. (22.07.2013 - 24.07.2013)
  
• You attend the talks of all other participants. (22.07.2013 - 24.07.2013)
  

Proposals of 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.:

• structure of your talk
• aspects of the automaton are you going to present
• 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 you going to present, which of them will be proven (why?) which proofs will be omitted (why?), will you use motivating examples in the proof?

Abstract of 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 (masters students, familiar with basic automata theory, 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 don't have to show how well you understood the topic for yourself. How well you understood the topic has no direct influence on your grade. How well you presented to topic to the audience will determine your grade.
  
• You may use and copy any source of information (but don't 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 don't let yourself 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 won't have any affect on you grade whether we may publish your slides or not.
  

Review of 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?
Are all propositions made by the author correct?
Is the schedule of the autor sensible? Do you think the talk will fit into the 30-45min 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

Asynchronous Automata (Julian Jarecki)

Literature: The Book of Traces: Chapter 7

Büchi Automata (Alperen Bektaş)

Omega-Automata (Deniz Biçer)

Star Height (Sabine Rogg)

Literature: Wikipedia On the star height of rational languages. A new proof for two old results.

LTL and Büchi Automata (Jeremi Dzienian)

Literature: Wikipedia

Alternating Finite Automata (Pascal Raiola, Matthias Hengel)

Literature: Wikipedia Implementing Reversed Alternating Finite Automaton (r-AFA) Operations Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata.

(I am able to send you a pdf of these papers)

This can be a topic for two students or two relatively independent topics for two students. One presents Alternating Finite Automata and the result that the reverse language of an AFA is accepted by an DFA with 2^n states. The other presents how AFAs can be efficiently implemented using a bit-wise representation.

Slides: Alternating Finite Automata - Part 1, Alternating Finite Automata - Part 2

Antichains in Automata Theory (Simon Bartels)

Literature: Wikipedia Antichains: A New Algorithm for Checking Universality of Finite Automata Antichain Algorithms for Finite Automata   When Simulation meets Antichains

This can be a topic for two students or two relatively independent topics for two students.

Reducing size of Büchi Automata (Eteri Sokhoyan, Javed Sarwer)

Literature: Wikipedia Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata Advanced automata minimization

This can be a topic for two students or a topic for one student.

(For viewing some of the papers you may need to log in to the Uni-network (f.i. via vpn) as they are not free.)