Seminar: Automata Theory and Games
Winter Term 2017/18 in Braunschweig
Tentative ScheduleAll talks will take place Mondays at 17:00 in room IZ305.
|December 4||Prakash Saivasan||Verification of Asynchronous Programs with Nested Locks|
|Sebastian Muskalla||On the Upward/Downward Closures of Petri Nets|
|December 18||Peter Chini||On the Complexity of Bounded Context Switching|
|Sebastian Wolff||Effect Summaries for Thread-Modular Analysis|
|January 8||Florian Furbach||Portability Analysis for Axiomatic Memory Models|
|Elisabeth Neumann||Liveness Verification and Synthesis: New Algorithms for Recursive Programs|
|January 15||Frederik Fröling||Visibly Pushdown Automata|
|Janosch Reppnow||Summaries for Context-Free Games|
|January 29||Nora Widdecke||Playing Infinite Games in Finite Time|
|Chico Sundermann||Solving Parity Games in Quasi-Polynomial Time|
- November 27
- A tentative schedule for the talks is available now.
- September 1
- The date of the kickoff meeting has been fixed, see below.
- June 2
- All information given on this page is still tentative.
OrganisationDuring the winter term 2017/18, the Institute of Theoretical Computer Science offers a seminar on Automata Theory and Games, headed by Prof. Dr. Roland Meyer. If you are interested in participating, please apply for the seminar via the Stud.IP system.
- The kickoff meeting will take place on Wednesday, October 25, at 8:45 in room IZ 358.
- Number of participants: We give topics to at most 12 students.
- Target audience: Computer Science students. This is a joint seminar for Bachelor's and Master's students.
RequirementsYou can choose one out of several topics. You will have to
- prepare and give a talk of 30 minutes (including questions) during the lecture period, and
- write a seminar paper in English, 10 pages using the LIPIcs LaTeX style until the end of the term.
TopicsMost topics are follow-up topics on the contents of the lectures Algorithmic Automata Theory respectively Games with Perfect Information which we offered in the summer term 2017. Some of the topics require no prior knowledge and are thus suitable for students that have not taken these lectures. The possible topics include, but are not limited to:
- Visibly pushdown automata
- Graph automata, bounded tree-width and Courcelle's theorem
- Higher-order pushdown automata
- Efficient techniques for language inclusion and equivalence
- Saturation for context-free games
- Summarization for context-free games
- Efficient algorithms for solving parity games
- Active context-free games
- Visibly pushdown games
- Regularity of winning regions in context-free games with omega-regular winning conditions
- Encoding Muller games