Seminar

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

Hauptseminar theoretische Informatik: "Undecidable problems from applications"

Preliminary schedule

The seminar starts on Monday, April 14th, at 16:40pm (DS 6) in room 0005 3027 of the computer science building with an introductory meeting. In this meeting all participating students will pick a research paper that they will write a report and give a talk about.

Presentations will take place during the last weeks of the teaching period (i.e. in June / July)

Position in the Curriculum

Depending on your course of studies, you can use this seminar for the following modules:

• Informatik (diploma) / master: INF-AQUA
• Computational Logic: PCS (TCSL, PI); 3 credit points

Prerequisites

Basic knowledge in computational complexity is helpful.
For computer science students: “Formale Systeme” or “Grundlagen der Theoretischen Informatik”

Language

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

Preliminary schedule

The initial meeting is on Monday April 14th at 16:40 o'clock (6. DS) in room INF 0005 3027.

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

For the CL master students this seminar can be used for several modules. Depending on the CL module the seminar will be used for, the student can either carry out the seminar in the calssical way (report and talk) or as an oral exam. This choice is only available to CL students , all other students can only have this seminar in the classical way.

• Oral exam — for the PI and TCSL modules
  Choose 3 papers from the pool of papers and make appointment for the exam and attend the seminar talks.
• Classical — for the AQUA and PCS modules
  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 first full version of their paper at least 5 weeks before their talk,
  • a first version of all the slides for their talk at least 2 weeks before the talk, and
  • a 30-35 minutes 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.

Pool of papers

The seminar is about presenting and discussing papers from the following list:

• Description Logics with Aggregates and Concrete Domains
• Practical Reasoning for Expressive Description Logics
• Equivalence of Datalog Queries is undecidable
• Termination of graph rewriting is undecidable
• On termination of one rule rewrite systems
• Properties of formal Languages
• A variant of a reursively unsolvable problem
• Classes of recursively enumerable sets and their decision problems

The seminar is open to suggestions from students about other papers being presented in the seminar.

Contact