Master-Praktikum in SS 2011

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

Some topics still available!

a short description of all topics offered can be found here [PDF]

if you are interested in one of them, please contact Rafael Peņaloza ASAP (projects are assigned in a first-come, first-serve basis)

Initial meeting

takes place on April 15 at 14:50 in Room INF-005. Attending the initial meeting is mandatory for participation in the praktikum/project.
People who want to participate in the praktikum/project, but have serious reasons to not attend the initial meeting, please contact Rafael Peņaloza until April 14.

Position in curriculum

- Masterstudiengang Informatik; Wahlpflichtveranstaltung (-/-/8)

Prerequisites

for computer scientists: Pflichtvorlesung "Grundlagen der Theoretischen Informatik"

Organisation

-There will be an initial meeting (see above) where different topics will be proposed to the students. Students can chose from the offered topics, one to work on.
- Students interested in doing their project, but unable to assist to the initial meeting should contact Rafael Peņaloza (:penaloza at inf.tu-dresden.de:) to discuss possible solutions.
- Each student is assigned a tutor, depending on the topic chosen. During the semester, there will be regular meetings of the student and his tutor.
- The results of the praktikum/project will be presented at the end of the semester in a talk given by the student.

Language

Concerning the final presentations, students may choose to present their work in German or in English.

Participants Duties

The participants are expected to read the relevant literature, and to discuss it with their tutor in order to become acquainted with the topic chosen. The required implementation work should be carried out in a structured way, and has to be documented appropriately. If a topic is shared by two or more participants, acquiring team-working skills is another goal of the project. The results of the project have to be described in a project paper (~15 pages) and presented in a 30 minutes talk at the end of the semester.

It is also the duty of the participants to reserve enough time for performing the project. The sharp deadline for finishing the project is the beginning of the following semester, i.e. the allowed time for the project is one semester plus the following semester break. Failure to finish the project in time will result in no credits to be given. It is the obligation of the participant to start the project in time, and to make appointments with the supervisor for regular meetings during the semester.

Topics

When choosing a topic, please take into account the knowledge you have already acquired. For example, if you'd like to do a project concerning knowledge representation, you are expected to have successfully attended the lecture "Logic-based knowledge representation" before starting the project.

(1) Unification in the Description Logic EL-trans

This project concerns the (theoretical) study of unification techniques for the lightweight Description Logic EL-trans.
A basic knowledge of Description Logics and Term Rewriting is desirable.

Tutor: Barbara Morawska

(2) Efficient Reasoning with Weighted Automata

Deciding emptiness of automata on trees requires, in general, polynomial time on the number of states of the automaton. However, there exist subclasses of automata for which this decision can be made with non-deterministic logarithmic space. The aim of this project is to generalize these classes to weighted automata, defining a subclass of these automata whose behaviour computation is also in non-deterministic logarithmic space.
This is a theoretical topic; some knowledge of automata theory is desirable.

Tutor: Rafael Peņaloza

(3) Implementation of a Monitor for ALC-LTL formulae

This project is about implementing a monitoring algorithm for ALC-LTL formulae, preferably in the JAVA programming language. Having done the implementation, the program should be evaluated by the student. Since the naīve automata-based algorithm has already a high complexity, it is needed to optimise it with the use of some on-the-fly technique.
Doing this project requires basic knowledge about automata and logic, as well as good programming skills.

Tutor: Marcel Lippmann

More topics t.b.a.