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

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

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:00	Joszef Benke	Simulation of TMs by a Rewrite Rule
10:00	Szilvia Halazs	Undecidability of SO Unification
11:00	Matthias Fruth	Undecidability of Aliasing
12:00	Lunch Break
13:00	Hongkai Liu	Equivalence of Datalog Queries
14:00	Eldar Karabaev	Side Effects in Prolog
15:00	Markus Krötzsch	Compass Logic
16:00	Mathias Kissig	Recursive 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

Prerequisites

for computer scientists: Pflichtvorlesung Grundlagen der Theoretischen Informatik

Language

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.

Contact

The seminar is coordinated by Dr. Carsten Lutz