[TU Dresden]


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

Hauptseminar Theoretische Informatik: "Undecidable Problems"

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

Computational Logic: Modules TCSL and IT, 3 credit points

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

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

Preliminary schedule
The following schedule is preliminary and may be subject to change during the following weeks.

Number Student Paper Tutor Presentation Report due Partner Paper
1 Amin Timany Simulation of Turing machines by a regular rewrite rule Barbara Morawska July 1 May 27 No. 5
4 Wenqian Wang Equivalence of Datalog queries is undecidable Felix Distel July 8 June 3 No. 7
5 Cheng Ye The expressive power of side effects in prolog Felix Distel July 8 June 3 No. 6
6 Dorian Merz Answering recursive queries under keys and foreign keys is undecidable Anni-Yasmin Turhan July 8 June 3 No. 1
7 Ralitsa Ivanova Protection in operating systems Felix Distel July 1 May 27 No. 4

Topic of the Hauptseminar
Participants will meet a selection of undecidable problems. The focus will be on problems that occur naturally in applications such as logic, artificial intelligence or knowledge representation. Participants are also invited to present their own (favorite) undecidable problems.

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). In doing this, he/she receives individual support by the tutor. The produced paper is required to conform to the standards of scientific writing. Advice (in German) for writing scientific papers can be found here. Finally, each student presents his/her work in a talk to the other participants.

It is also the duty of the participants to reserve enough time for performing the seminar. It is the obligation of the participant to start working in time, and to make appointments with their tutors for regular meetings during the semester. In particular, students must present to their tutors

The seminar is coordinated by Felix Distel.

Last modified: Tue Sep 28 17:46:28 CET 2010