Seminar

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

Hauptseminar Theoretische Informatik: "Advanced Topics in Automatic Structures"

Position in Curriculum

• Master Informatik: Module INF-MA-PR
• Computational Logic: Modules MCL-PCS, MCL-PI, MCL-TCSL, MCL-AL, 3 credit points
• Informatik diploma: Wahlpflichtveranstaltung (-/-/2)

Prerequisites

Basic knowledge in logic and automata theory. It is not necessary to have attended the lecture Introduction to Automatic Structures, but it is helpful.
For computer science 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 started on Friday, April 13, at 2:50pm in room 3027 of the computer science building with an introductory meeting.
In case students are interested to join the seminar, they can do so by the end of April. In that case send an email to Anni-Yasmin Turhan.

The student presentations will take place during the last weeks of the teaching period.

Topic of the Hauptseminar

Participants will get to know different types of automatic structures. The seminar will investigate properties of the structures and the relationship between them and different kinds of logics.

Available Seminar Papers

• Theories of Automatic Structures and Their Complexity
  D. Kuske
• Definability and Regularity in Automatic Structures
  B. Khoussainov , S. Rubin , F. Stephan
• Finite Presentations of Infinite Structures: Automata and Interpretations
  A. Blumensath, E. Grädel
• First-order and counting theories of omega-automatic structures
  D. Kuske , M. Lohrey

Classical Mathematical Problems treated with Automatic Structures

• Is Cantor's theorem automatic?
  D. Kuske
• Automatic linear orders and trees--revised
  B. Khoussainov, S. Rubin, F. Stephan
  Automatic version of Königs Lemma

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 report, that conforms to the rules of scientific writing, 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 report 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 report 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 25-30 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 teaching or traveling obligations. If possible, try to arrange meetings well ahead of time.
• Make sure the produced report 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.

If both, the student report and the student talk, are of acceptable quality, then the grade for the seminar will (roughly) be based by 2/3 on the quality of the report and by 1/3 on the quality of the talk.

Contact

The seminar is coordinated by Anni-Yasmin Turhan.