Seminar

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

Hauptseminar Theoretische Informatik: "Selected Topics in Automata Theory"

Position in Curriculum

Informatik (diploma), Wahlpflichtveranstaltung (-/-/2)
Informatik (bachelor), 3 credit points


Computational Logic: Modules TCSL and IT, 3 credit points

Prerequisites

Basic knowledge in logic and automata theory.
For computer scientist students: “Grundlagen der Theoretischen Informatik” or “Formale Systeme”

Language

The language of the seminar is English — unless attended by native German speakers only.

Preliminary schedule

The seminar starts on Friday, October 14, at 2:50pm in room 3027 of the computer science building with an introductory meeting. In this meeting all students will be assigned a research paper and a tutor.
Presentations will take place during the last weeks of the teaching period (i.e. from January 13 to February 3) .

Number	Student	Paper	Tutor	Partner Paper	Presentation Date	Report Due
1	Christian Fraß	R. Gerth et al., Simple On-the-fly Automatic Verification of LTL	Felix Distel	6	January 30th	December 16th
4	Wu Xichuan	J.-M. Couvreur et al., On-the-fly Emptiness Checks for Generalized Büchi Automata	Barbara Morawska	1	January 30th	December 22nd
5	Martin Aleksandrov	Efficient Büchi Automata from LTL Formulae	Marcel Lippmann	4	January 30th	December 22nd
6	Shqiponja Ahmetaj	O.H. Ibarra, On two-way Multihead Automata	Felix Distel	9	January 20th	December 9th
9	Oliver Fernandez Gil	J. Engelfriet et al., Nested pebbles and transitive closure	Felix Distel	5	January 20th	December 16th

Topic of the Hauptseminar

Participants will get to know a variety of different types of automata, that are usually outside the scope of introductory lectures on automata theory. One focus will be the relationship between these types of automata and first order logic.

Goal of the Hauptseminar

Apart from learning about the main topic, students should learn how to get acquainted with a relevant body of literature, how to produce a well-structured paper, and how to give an understandable scientific talk.

Duties of Participants

In the initial meeting, students choose a topic to work on and are assigned a tutor. During the seminar, the student has to understand the relevant literature and writes a paper about the chosen topic (~12 pages). Finally, each student presents his/her work in a talk to the other participants. In doing this, he/she receives individual support by the tutor. The students should present

• a full version of their paper at least 5 weeks before their talk, and
• a first version of all the slides for their talk at least 2 weeks before the talk, and
• a 20-25 minute presentation followed by 5-10 minutes of discussion.

Additionally, students must meet the following requirements.

• Refrain from any form of plagiarism in the preparation of your report. If you are unsure what is considered plagiarism in academia please consult this helpful guide by the University of Oxford.
• Reserve enough time for the seminar.
• Make appointments with your tutor. It is customary to have a first consultation within one or two weeks after the initial session. Remember that your tutor may not always be available because of travelling obligations. If possible, try to arrange meetings well ahead of time.
• Make sure the produced paper conforms to the usual standards of scientific writing. Advice (in German) for writing scientific papers can be found here.
• If possible use LaTeX for typesetting your report. If you absolutely have to use a different software you must make sure that all formulas are typeset using a formula editor.
• If you choose to use LaTeX use either the document class article or scrartcl. Do not change fonts, font sizes, margins, headers or footers.
• Prepare a question for the discussion of your partner paper. This will be explained in more detail during the introductory meeting.

Contact

The seminar is coordinated by Felix Distel.