# 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 | Christian Schilling (contact person for organizational matters), Prof. Dr. Andreas Podelski, Dr. Matthias Heizmann, Dr. Jochen Hoenicke, Marius Greitschus, Vincent Langenfeld, Alexander Nutz |

Kick-off meeting |
Thu, October 19, 13:00 s.t., building 052, room 00-016 |

Presentation language |
English (Seminar) / German (Proseminar) |

Credits |
4 (Seminar) / 3 (Proseminar) |

Course Catalog | Advanced Topics in Automata Theory (Seminar) Introduction to Automata Theory (Proseminar) |

## News

- We had to reorder the reviewers for most topics.
- We have added a tentative schedule (see at the bottom) and assigned the reviewers.
- We have assigned a topic and a supervisor to each student (see at the bottom). Please contact your supervisor for further clarification of the literature and a meeting.

The tentative dates for the talks are (updated) two Saturdays, January 27 and February 3, 2018, 9:00-14:30 s.t. with a lunch break. We have reduced the talk time to 25-30 min (seminar) resp. 18-22 min (proseminar) in the interest of time.

Please contact Christian if you cannot attend the seminar at that time.

## Process of the seminar

- You participate in the kick-off meeting, where we present the
available topics. Feel free to hand in your favorite topic in advance.
- You 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.
- You have a meeting with your supervisor in which we discuss relevant literature and develop a very coarse sketch of your talk (deadline: four weeks before your talk).
- You write a proposal in which you explain what you are going to present in your talk, together with an abstract of your talk. You submit your abstract and your proposal via email to your supervisor (deadline: three weeks before your talk).
- Your proposal is reviewed by your supervisor and two other participants.
- You
write two reviews about other participants' proposals and send them via
email to the supervisor (deadline: one week after you received the
proposal).
- You receive reviews for your proposal (deadline: two weeks before your talk).
- You submit your slides via email to your supervisor (deadline: one week before your talk).
- You have a meeting with your supervisor in which you get feedback for your slides.
- You give a talk of
**25-30**minutes (Seminar) /**18-22**minutes (Proseminar). The upper bounds are hard deadlines. - 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:

- 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

- The abstract consists of 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 (bachelor and 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 prepared to a specific audience.
- If you agree, we will put your slides on this web page. Keep in mind that if you have copied images in your slides this might not be possible anymore (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 proposal. 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?

## 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 & literature

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. More literature does not mean more reading, just more options. The order of appearance is alphabetical. We have annotated each topic with "P" or "S", indicating that it is a proseminar resp. seminar talk, and with "A" or "B" indicating the group (see section "Schedule").

If requested, some topics may also be presented in groups of two.

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.

**Petri nets I [P, A]**

Literature: Applied Automata Theory (Chapter 6), FMSD '02, Software & Systems Modeling '14

Supervisor: Marius

Talk: Yannick

Reviewers: Bora, Dominik

**Petri nets II [S, A]**

Literature: Applied Automata Theory (Chapter 6), FMSD '02, Software & Systems Modeling '14

Supervisor: Alexander

Talk: Dominik

Reviewers: Johannes K., Yannick

**Number theory & automata [S, A]**

Literature: arXiv '17, arXiv '17

Supervisor: Christian

Talk: Johannes K.

Reviewers: Felix, Johannes H.

**Efficient representation of finite sets [S, A]**

Literature: Automata theory - An algorithmic approach (Chapter 7), RAMICS '12

Supervisor: Alexander

Talk: Ivo

Reviewers: Felix, Klajdi

**Context-sensitive languages [S, A]**

Literature: Wikipedia, Wikipedia, Formal languages (Chapter 5), SIAM J. Comput. '88, MFCS '01

Supervisor: Christian

Talk: Klajdi

Reviewers: Alexander, Dominik

**Super Turing machines [P, A]**

Literature: arXiv '98, CCA '05, A computable universe

Supervisor: Alexander

Talk: Felix

Reviewers: Johannes K., Michael

**Büchi automata [P, B]**

Literature: Automata theory - An algorithmic approach (Chapter 11 Section 1-2), Automata on infinite objects (Chapter I Section 1-2)

Supervisor: Vincent

Talk: Michael

Reviewers: Bora, Yannick

**Büchi automata complementation [S, B]**

Literature: LMCS '07

Supervisor: Matthias

Talk: Alexander, Constantin

Reviewers: Alexander, Constantin, Dejan

**Complexity of Büchi automata minimization [S, B]**

Literature: arXiv '10

Supervisor: Christian

Talk: Dejan

Reviewers: Ivo, Johannes H.

**Complexity of games [P, B]**

Literature: PushPush and Push-1 are NP-hard in 2D, Classic Nintendo games are (NP-)hard, Gaming Is a hard job, but someone has to do it!, Playing games with algorithms: algorithmic combinatorial game theory, The hardness of the Lemmings game, or Oh no, more NP-completeness proofs, Computational complexity of two-dimensional platform games, Lemmings is PSPACE-complete

Supervisor: Jochen

Talk: Johannes H.

Reviewers: Ivo, Michael

**Set automata [S, B]**

Literature: DLT '14 [technical report], DCFS '14, DLT '17

Supervisor: Christian

Talk: Bora

Reviewers: Constantin, Klajdi

## Schedule

Each topic/talk has a group letter assigned. We have two groups in total.

The following table contains the deadlines for the groups. The proposal/review/slides deadlines are the same for both groups.

Date | Proposal | Review | Slides | Talk |
---|---|---|---|---|

Fri, December 22 |
A & B |
|||

Fri, January 12 |
A & B |
|||

Fri, January 19 |
A & B |
|||

Sat, January 27 |
A |
|||

Sat, February 3 |
B |