Seminar

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

Prerequisites

Basic knowledge in logic.
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 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

• 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.

Contact

The seminar is coordinated by Felix Distel.