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  Alexander Nutz, Christian Schilling 
Kickoff meeting 
Fri, October 21, 2016, 14:00  16:00 c.t., building 101, room SR 01 009/13 
Presentations  Thu, February 16, 2017, 9:00  13:00 & Fri, February 17, 2017, 9:00  16:00 building 101, room SR 00 010/14 
Presentation language 
English (Seminar) / German (Proseminar) 
Credits 
4 (Seminar) / 3 (Proseminar) 
Course Catalog  Advanced Topics in Automata Theory (Seminar) Automatentheorie / Introduction to Automata Theory (Proseminar) 
News
 Jan. 11: We added a provisional
schedule for the talks (was updated later the same day!). Please let us know if your time slot is not wellsuited.
 Nov. 8: We fixed the date and time for the seminar to February 16&17 (see the box above).
 Nov. 4: We assigned the topics and reviewers and added a schedule for the deadlines (not for the talks, that date is still to be found). If you prefer a different deadline slot, please contact your supervisor soon.
 Nov. 3: We added the proseminar talk evaluation form.
 Nov. 2: On popular demand we will have a block seminar (both Proseminar and Seminar). We have created a Doodle for the first two weeks after the end of the lecture period. The link was sent in an email.
 Oct. 22: Please send us a mail until Fri, October 28 that contains the following information.
 a list of 5 topics that you want to present (with priorities); we may add some more topics at the beginning of the week
 whether you are a seminar or a proseminar student
 (optional) whether or not you prefer to work in a group of two students
 (optional) whether or not you prefer a block seminar or a weekly seminar and what time constraints you have (early/late in the semester, the Friday slot, during or after the lecture period, etc.)
 (optional) whether or not you are an ESE student

Oct. 19: The first meeting takes place on October 21 (the room was also changed).
Process of the seminar
 You participate in the kickoff meeting, where we present the available topics. Feel free to hand in your favorite topics 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 the instructors.
 You have a meeting with your supervisor in which we discuss relevant literature and develop a very coarse sketch of your talk.
 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 your supervisor (deadline: see schedule).
 Your proposal is reviewed by two other participants.
 You write two reviews about other participants' proposals and send them via email to the supervisor who sent you the proposals (deadline: one week after your received the proposals).
 You receive reviews of your proposal (deadline: two weeks before your talk).
 You submit your slides via email to your supervisor (deadline: see schedule).
 You have a meeting with your supervisor in which you get feedback for your slides.
 You give a ca. 30 min (Seminar) / 20 min (Proseminar) talk.
 You attend the talks of all other participants.
Proseminar addition:
 You evaluate the talk of two other participants using a checklist.
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 wellstructured 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?
Evaluation of the talk
To provide feedback, we want to discuss some aspects of the Proseminar talks in public. Two other students fill out an evaluation sheet during the talk and we shortly discuss the strengths and weaknesses afterward.
For Seminar students this mode is optional.
Students can additionally receive private feedback upon request.
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 onetoone 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.
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.
Topics are marked with a letter in parentheses to indicate which seminar mode they are suited for.
 (S) = Seminar
 (P) = Proseminar
Learning finite automata
 (P, 1) Learning regular sets from queries and counterexamples, Talk (min. 1530), Talk (min. 2034)
 Talk: Aleksandar
 Reviewers: Berna, Karsten
 Supervisor: Christian Schilling
Minimization of Mealy automata
 (P, 1) MeMin: SATbased exact minimization of incompletely specified Mealy machines
 Talk: Robin
 Reviewers: Felix J., Frank
 Supervisor: Christian Schilling
Minimization of finite automata
 (P, 2) A splitbased incremental deterministic automata minimization algorithm
 Talk: Felix J.
 Reviewers: Robin, Tutku
 Supervisor: Christian Schilling
Petri Nets
 (P, 2) Applied Automata Theory (Chapter 6), Recent and simple algorithms for Petri nets
 Talk: Chandran, Tim M.
 Reviewers: Aleksandar, Chandran, Tim M., Tutku
 Slides: Petri Nets 1, Petri Nets 2
 Supervisor: Alexander Nutz
Büchi automata
 (P, 3) Automata theory  An algorithmic approach (Chapter 11 Section 12), Automata on infinite objects (Chapter I Section 12; not publicly available anymore)
 Talk: Berna & Tutku
 Reviewers: Benjamin, Maximilian, Simon, Tim A.
 Supervisor: Christian Schilling
Tree automata
 (P, 3) Tree automata  Techniques and applications
 Talk: Sebastian
 Reviewers: Berna, Frank
 Supervisor: Alexander Nutz
Don't care words
 (P, 4) Learning minimal separating DFA's for compositional verification
 Talk: Karsten
 Reviewers: Aleksandar, Sebastian
 Slides: Learning minimal separating DFA for Compositional Verification
 Supervisor: Christian Schilling
Flanked finite automata
 (P, 4) On the complexity of flanked finite state automata
 Talk: Benjamin
 Reviewers: Maximilian, Tim M.
 Supervisor: Alexander Nutz
Visibly pushdown automata
 (P, 4) Wikipedia, Visibly pushdown languages, Adding nesting structure to words
 Talk: Frank
 Reviewers: Benjamin, Sebastian
 Slides: Visibly Pushdown Automata
 Supervisor: Christian Schilling
Contextsensitive languages
 (P, 5) Wikipedia, Formal languages (Chapter 5), Nondeterministic space is closed under complementation
 Talk: Simon
 Reviewers: Karsten, Robin
 Supervisor: Alexander Nutz
Reachability in pushdown systems
 (P, 5) Applied Automata Theory (Chapter 4.2)
 Talk: Maximilian
 Reviewers: Chandran, Samuel
 Supervisor: Christian Schilling
Simulation
 (P, 5) Fair simulation relations, parity games, and state space reduction for Büchi automata
 Talk: Tim A.
 Reviewers: Felix J., Samuel
 Supervisor: Christian Schilling
Visibly pushdown automata
 (S, 6) Symbolic visibly pushdown automata
 Talk: Dirk
 Reviewers: Omar, Theresa
 Supervisor: Christian Schilling
 (S, 6) On model checking for visibly pushdown automata, A tighter bound for the determinization of visibly pushdown automata
 Talk: Theresa
 Reviewers: Dirk, Felix F.
 Supervisor: Christian Schilling
Antichains
 (P&S, 7) Wikipedia, Antichains: A new algorithm for checking universality of finite automata, Antichain algorithms for finite automata, When simulation meets antichains
 Talk: Felix F. & Samuel
 Reviewers: Omar, Simon, Theresa, Tim A.
 Slides: Antichain Algorithms, A Fixpoint Antichain Algorithm
 Supervisor: Alexander Nutz
Simulation
 (S, 7) Advanced automata minimization
 Talk: Omar
 Reviewers: Dirk, Felix F.
 Supervisor: Christian Schilling
Not assigned
Ogden's lemma
Simulation
Visibly pushdown automata
Contextsensitive languages
Parikh's theorem
Quotient for missing specifications
Schedule
Provisional schedule for the talks
Each topic/talk has a slot number assigned. We have seven slots in total.
The following table contains the deadlines for the groups. Please note that "Review" stands for the review deadline for the specific group's proposals. Each student has to write reviews for two other students.
Date  Proposal  Review  Slides 

Fri, Nov. 25 
1  
Fri, Dec. 2  2  1  
Fri, Dec. 9  3  2  1 
Fri, Dec. 16  4 
3  2 
Fri, Dec. 23  5  4  3 
Fri, Jan. 13  6  5  4 
Fri, Jan. 20  7  6  5 
Fri, Jan. 27  7  6  
Fri, Feb. 3  7 