Automatentheorie (Proseminar)

Sessions

The regular talk sessions take place in-person as a block seminar at the location and time given above.

Process of the proseminar

• If you are admitted to the proseminar, you receive an e-mail in which you are assigned to a topic and a supervisor.
• You read the literature for your assigned topic and develop a coarse sketch of your talk.
• You have a meeting with your supervisor in which we discuss the literature and the sketch of your talk.
• You write a proposal in which you explain what you are going to present in your talk. You send your proposal via email to your supervisor.
• You have a meeting with your supervisor in which you get feedback on your proposal.
• You submit a final version of your proposal via the proseminar's Ilias course.
• You receive the proposals of the other participants.
• You write a review for the proposal of one participant.
• You write short summaries and questions for the proposals of the other participants (see below).
• You submit the review, your short summaries and questions via the proseminar's Ilias course.
• You send your slides via email to your supervisor.
• You have a meeting with your supervisor in which you get feedback for your slides.
• You submit a final version of your slides via the proseminar's Ilias course.
• You give a talk of 25 minutes and answer questions in the subsequent discussion round (5 - 10 minutes).
• You attend the talks of all other participants and participate in the discussion rounds.

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?

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. A student will not get a bad grade because you revealed some problems in his/her proposal.
• 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?

Short Summary & Questions

• You read the proposals of all other participants.
• For each proposal you write a short summary (2-3 sentences).
• For each proposal you write down two precise questions that you may ask the speaker after the talk was given.

Grade

Your overall grade will be composed according to the following proportion.

• 20% grade of your proposal
• 60% grade of your talk
• 20% grade of your review and preparation

Topics and Literature

The topics of the proseminar are based on the book Automatentheorie und Logik by Hofmann and Lange. The book is available via the university network The book is available via the university network (or after you log in with your RZ-login). If you have problems accessing the literature, please contact us.

1. Schwache Monadische Logik zweiter Stufe (Chapter 2)

2. Alternierende Endliche Automaton (Chapter 3)

3. Sternfreie Sprachen (Chapter 4)

4. Automaten auf unendlichen Wörtern (Chapter 5)

5. Linearzeit-Temporale Logik (Chapter 11)

6. Automaten auf endlichen Bäumen (Chapter 12)

Preliminary Schedule

The following table contains the preliminary schedule. The dates for the meetings with your supervisor only serve as an orientation. You are responsible to make individual appointments with your supervisor.