Komplexpraktikum/Masterpraktikum/Project Group in WS 2014/2015

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

Initial meeting

takes place on October 22nd at 14:50 in Room 3027. Students who are not able to attend the initial meeting please contact Anni-Yasmin Turhan before October 21.

Position in curriculum

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

Prerequisites

Knowledge in propositional logic is neccessary.
Knowledge from the following lectures is helpful:
- Formale Systeme
- Theoretische Informatik und Logik
- Description Logics

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 Anni-Yasmin Turhan 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 description logics, you are expected to have successfully attended the lecture "Description Logics".

(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) The Cost of Rough Reasoning

In this project, the student is expected to design, implement and execute different tests for evaluating the practical cost of adding support to new constructors into a reasoner. As a guiding example, the cost of adding support of rough logical constructors is to be analysed. A deep statistical analysis and understanding of the obtained data is expected.

A basic knowledge of statistical tools and methods is desired, but not mandatory.

Tutor: Rafael Peñaloza

(4) Most Specific Generalizations w.r.t. General TBoxes in ELgfp

This project aims at the implementation and evaluation of methods for calculating least common subsumers and most specific concepts in the leight-weight description logic ELgfp, i.e. EL interpreted with greatest fixpoint semantics. In contrast to standard EL with descriptive semantics, those most specific generalizations always exist in ELgfp and can be computed in polynomial time. Furthermore, the student should make a comparison with most specific generalizations w.r.t. standard descriptive semantics and with role-depth bounded most specific generalizations w.r.t. descriptive semantics.

Basic knowledge in description logics and good programming skills are expected. For an easier handling and integration with existing software (e.g. Elk, Protégé etc.), the program should be built on top of the OWL API.

References
[1] Franz Baader: Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles
[2] OWL API

Tutor: Francesco Kriegel

(5) Formal Concept Analysis & Propositional Logic: From Pseudo-Intents to Implicational Bases

This project's aim is the formulation of a minimal theory of implications, which holds in a given set of propositional models and furthermore entails all other implications, that hold in the given model set. This requires an isomorphism between propositional model sets and formal contexts, to adapt the existing results for implicational bases of formal contexts. Furthermore the student should give an algorithm to compute the implicational base. The results can be extended to propositional bases.

Basic knowledge in propositional logic and set theory is expected. Further knowledge in logic or order theory may be helpful.

References
[1] Bernhard Ganter and Rudolf Wille: Formal Concept Analysis, ISBN 3-540-62771-5, Springer Verlag
[2] Bernhard Ganter: Attribute Exploration with Background Knowledge

Tutor: Francesco Kriegel

More topics t.b.a.