Komplexpraktikum/Project in WS 2012/2013

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

Initial meeting

takes place on October 19th at 15:00 in Room INF-3027. 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 before October 18.

Position in curriculum

- Diplomstudiengang Informatik (Diplom- und Bakkalaureatsabschluß), ab 5. Semester; Wahlpflichtveranstaltung (-/-/4)
- Course of studies Computation Logic; project (12 credits)

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 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 (if any) 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) Finite Herbrand Models for Horn Clauses

Deciding the existence of finite Herbrand models for certain sets of first-order anti-Horn clauses is ExpTime-complete. The aim of this project is to analyze the computational complexity of the same problem for Horn clauses by finding a hardness proof and/or a decision procedure.
This project requires basic knowledge about first-order logic and complexity theory.

Tutor: Stefan Borgwardt

(2) Finite Herbrand Models for anti-Horn Clauses

The aim of this project is to implement and optimize an algorithm for deciding the existence of finite Herbrand models for certain sets of first-order anti-Horn clauses. The program should be evaluated on a representative set of input problems. The programming language can be chosen by the student.
This project requires basic knowledge about first-order logic and good programming skills.

Tutor: Stefan Borgwardt

(3) Finding the Best Explanations

When dealing with vast ammounts of knowledge, it is important to be able to explain why some consequence holds. Typically, a single consequence can have more than one explanation. The aim of this project is to study methods for computing the best explanation efficiently, when possible, and identifying the cases where this is a hard problem.
Basic knowledge of complexity theory and Description Logics is useful, but not required.

Tutor: Rafael Peñaloza

(4) Implementing Similarity Measures for ELH

A variety of similarity measures and their properties have been recently studied for the Description Logic ELH. The goal of the project is to implement a framework capable of dealing with different similarity measures, and use it to compare known measures found in the literature.
This is a practical topic that requires good programming skills

Tutor: Anni-Yasmin Turhan

(5) Combining GEL with the ELK reasoner

GEL is a tool for computing generalization inferences in extensions of the Description Logic EL. In its current state, it is coupled with, and depends on, the reasoner jCEL. In this project, the student should implement and interface between GEL and the ELK reasoner, and compare its performance with that obtained from jCEL.
This is a practical topic that requires good programming skills

Tutor: Anni-Yasmin Turhan

(6) Verification of Properties of Infinite Sequences of DL-Actions w.r.t. general TBoxes

This project is about the verifying properties of DL-action sequences generated by Büchi-automata. So far, this was considered only w.r.t. acyclic TBoxes. The goal of this project is to extend the results to general TBoxes.
Basic knowledge of Description Logics, temporal logics, and automata theory is required.

Tutor: Marcel Lippmann, Benjamin Zarrieß

More topics t.b.a.