takes place on October 21st at
15:00 in Room INF-3027. Attending the initial meeting is mandatory for participation in the
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.
for computer scientists: Pflichtvorlesung "Grundlagen der Theoretischen Informatik"
-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
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 will be presented at the end of the
semester in a talk given by the student.
final presentations, students may choose to present their work in German or in English.
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.
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 automata theory 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).)
(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.
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
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).)