# 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.

Course type | Seminar |
---|---|

Instructors | Matthias Heizmann, Alexander Nutz |

Kick-off meeting |
Wed 25.4.2012, 13:00-14:00, building 052, room 00-016 |

Presentations | Weekly, starting in June |

Presentation language |
English |

Credits | 4 |

Course Catalog | Automata Theory |

## News

- Please let us know your preferred topics until Monday morning 9:00 (30th April 2012).
- Please use the our Doodle calendar [link removed] to let us know when you are available. If all participants agree on a common day and time the seminar will be rescheduled from Mon 10:00-12:00 to this day and time.

## Time, Date and Location

Talks will be given weekly on Monday at 10h ct. The first talk will be on Monday 4th June. According to the preferences of the person that gives the talk, the talks will be either in our meeting room (building 52 room 00-016) or in a seminar room. If not announced otherwise the talk is in our meeting room.

## Process of the seminar

- You choose one kind of automaton.
- You get literature about this automaton from the organizers.
- You write a proposal in which you explain what you are going to present in your talk.
- You submit your proposal three weeks before your presentation.
- Your proposal is reviewed by two other participants.
- Two weeks before the presentation you receive the review of your proposal.
- One week before your presentation you submit an abstract of your talk.
- One week before your presentation you submit your slides.
- You give a ca. 30-45 min talk.
- You write two reviews about other participants proposals and attend all talks of the other participants.
- You attend the talks of all other participants.

## 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.
- For each talk we sent an invitation to all members of our chair. This invitation will contain your abstract.

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

## Schedule

4.6.2012 **Nested Word Automata **(Christian Schilling)

Literature: Nested Words, Adding nesting structure to words

Reviewers: Fabian, Jan

Slides: Nested Word Automata

11.6.2012 **Tree Automata** (Betim Musa)

Literature: Wikipedia, TATA, Applied Automata Theory: Chapter 3

Reviewers: Jonas, Rebecca

Slides: Tree Automata

18.6.2012 **Petri Nets** (Rebecca Albrecht)

Literature: Applied Automata Theory: Chapter 6, Trace Theory

Reviewers: Betim, Julian

Slides: Petri Net

25.6.2012** Asynchronous Automata** (Julian Jarecki)

Literature: The Book of Traces: Chapter 7

Reviewers: Jonas, Rebecca

Slides: Asynchronous Automata

2.7.2012 **Graph Automata** (Jan Leike)

Literature: The tree width of auxiliary storage

Reviewers: Christian, Julian

Slides: Graph Automata

9.7.2012 **Büchi Automata** (Yang Zhang)

Literature: Automata on Infinte Objects, Linear-Time Temporal Logic and Büchi Automata, ω-Automata, The complementation problem for Büchi automata with applications to temporal logic

Reviewers: Christian, Fabian

16.7.2012 **Büchi Automata Part2 / Alternating Automata** (Fabian Reiter)

Literature: Weak Alternating Automata Are Not that Weak, Complementation of Büchi Automata Using Alternation

Reviewers: Jan, Yang, Betim

Slides: without overlays, with overlays, printable without overlays, printable with overlays, handout selection, handout full

(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.)