Komplexpraktikum/Project in WS 2011/2012

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

Initial meeting

takes place on October 21st 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 until October 20.

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 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) The Many Boundaries of Context Reasoning

One approach for reasoning with context consists on maintaining one (large) ontology, and label each axiom with label expressing the contexts to which it is relevant. For every consequence, one must then find a so-called boundary: a label that represents the (un)availability of the consequence for every concept.
The project consists on studying the properties of these boundaries; for example, if/when it is unique, how can one compute them all, or the greatest, or the least, etc.

This is a theoretical topic; some knowledge of lattice theory and/or algebra is desirable.
Suggested literature: A Generic Approach for Large-Scale Ontological Reasoning in the Presence of Access Restrictions to the Ontology's Axioms (available online (as pdf).)

Tutor: Rafael Peñaloza

(2) Deciding Emptiness of Alternating Automata Efficiently

Alternating Automata on finite words are a generalization of finite automata where states can be divided into universal and existential. Every alternating automaton can be transformed into a finite automaton with exponentially many states. This yields an exponential-time decision procedure for the emptiness of alternating automata. However, this algorithm is highly inefficient.
The project consists on developing an algorithm for performing the emptiness test of alternating automata directly (that is, without first transforming them into finite automata). The algorithm should then be implemented and tested.

This is a mainly theoretical topic, but an implementation is expected; knowledge of automata theory is desirable.

Tutor: Barbara Morawska

(3) Implementing Incremental Reasoning in jCEL

jCEL is a JAVA-based reasoner for the Description Logic EL based on a completion algorithm. In its most basic form, this algorithm requires to recompute all the information every time a small change is introduced in the ontology. Incremental reasoning aims to avoid unnecessary recomputations, by adding only the information introduced by every new axiom.
The project consists on implementing the incremental reasoning technique to jCEL and evaluate its performance through extensive testing.

This is a practical topic, an implementation and testing is expected; knowledge of JAVA is required.
Suggested literature: Module Extraction and Incremental Classification: A Pragmatic Approach for EL+ Ontologies (available online (as pdf).)

Tutor: Julian Mendez

More topics t.b.a.