You are here: Home Teaching Winter Term 2022/23 Automatentheorie (Proseminar)

Automatentheorie (Proseminar)

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 proseminar 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 Proseminar
Instructors

Prof. Dr. Andreas Podelski
Elisabeth Henkel (contact person for organizational matters)
Dominik Klumpp
Frank Schüssele

Kickoff session Thursday, 20. October 2022, 10:00 c.t. (online)
BigBlueButton
Talk Sessions

Monday, 13.02.22, 10:00 - 17:00 s.t. (in-person)
Tuesday, 14.02.22, 10:00 - 17:00 s.t. (in-person)
(room tba.)

Language of instruction German
Credits 3
Course Catalog Proseminar Softwaretechnik
Ilias Course Students registered on HisInOne will be added to the course automatically.
 

News

  • Oct 17: Add BBB link for kickoff meeting.
  • Oct 10: Website online.

Proseminar

This proseminar gives a first introduction to scientific working in the discipline of computer science. The emphasis in this proseminar is on the presentations (in the roles of speaker as well as a participant).
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 (or after you log in with your RZ-login). If you have problems accessing the literature, please contact us.

Registration

  • The kickoff meeting for this pro-seminar takes place online (BigBlueButton) at the time given above.
  • In the kickoff meeting, we will elaborate on the goals, the construction, and the rules of the pro-seminar.
  • By Monday, 24th of October 2022, 09:00 (local time), you tell us
    • a list of your favourite topics (first favourite first, as many as you like)
    • and that you certainly want to participate in this proseminar
  • If the proseminar is fully booked, we will prefer admitting students who attended the kickoff meeting and submitted their favourite topics on time. The organisors will try to match favourite topics to people as well as possible.

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.

DateMeetings
SubmissionsEvents
20.10.22
Kickoff (online)
30.10.22
Topic Assignment
22.12.22 Sketch
13.01.23 Proposal
20.01.22
Proposal
23.01.23 Handout of Proposals
03.02.23 Slides

 


10.02.2023

Slides

Review

Summaries & Questions

12.01.23 / 13.02.23 Talk session (in-person)