TU Dresden
Institut für Theoretische Informatik
Lehrstuhl für Automatentheorie

Hauptseminar "Undecidable Problems from Real Applications" im WS 2003/04

More Information for participants is now available.

Initial Meeting
Attending the initial meeting is mandatory for participation in the seminar. People who want to participate in the seminar, but have serious reasons to not attend the initial meeting, please send an email until April 8.

Schedule for Presentations
All presentations take place on February, 6th. Participants of the seminar are expected to attend all talks. The length of talks is 40 minutes.
The presentations will take place in ROOM 151

09:00Joszef BenkeSimulation of TMs by a Rewrite Rule
10:00Szilvia HalazsUndecidability of SO Unification
11:00Matthias FruthUndecidability of Aliasing
12:00Lunch Break
13:00Hongkai LiuEquivalence of Datalog Queries
14:00Eldar KarabaevSide Effects in Prolog
15:00Markus KrötzschCompass Logic
16:00Mathias KissigRecursive Queries under Keys

Position in Curriculum
Informatik (both diploma and bachelors degree), starting from 5. semester, Wahlpflichtveranstaltung (-/-/2)
Computaional Logic: Module TCSL, 3 credit points

for computer scientists: Pflichtvorlesung Grundlagen der Theoretischen Informatik

The language of the initial meeting is English unless attended by native German speakers, only. Concerning the final presentations, students may choose to present their work in German or in English.

Topic of the Hauptseminar
Many undecidable problems that are presented in computer science lectures are of a rather theoretical nature. The reason for this is not that undecidability does not arise in practice: in this seminar, we will meet several undecidable problems that occur naturally in applications. The considered applications are from the areas of operation systems security, artificial intelligence, logic, specification, and program analysis.

Participants are also invited to present their own (favorite) undecidable problems.

Goal of the Hauptseminar
Participants should learn about the relevance that theoretical computer science has for practical applications. Moreover, 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 talk.

Hints on how to prepare a paper and how to give a talk are available (in German).

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. Finally, each student presents his/her work in a talk to the other participants.

The seminar is coordinated by Dr. Carsten Lutz