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.
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.
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.
(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.
(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.