Komplexpraktikum/Project "Automated Reasoning in Logical Formalisms" in WS 2003/04
- takes place on October 17 at
11:10 (3. DS) in Room 454. 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 send an
email until April 8.
Position in curriculum
- - Diplomstudiengang Informatik (Diplom-
und Bakkalaureatsabschlu▀), ab 5. Semester
- Course of studies Computation Logic; project (12 credits); module TCSL
- for computer scientists: Pflichtvorlesung "Grundlagen der Theoretischen Informatik"
- - An initial meeting is held at the beginning of the semester (see
above). In this meeting, a brief presentation of the available topics
will be given (see below). Students then have the opportunity to
choose a topic to work on.
- 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. Time and date are yet to be
- The language of the initial meeting is English. 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.
Some of the topics can be worked on by more than one student. Further
topics will be added in due course.
Implementation of optimized ALC-ALE Approximations
Approximation is a new reasoning service for description logics that
has recently cought the attention of researchers. The purpose of this
project is to enhance the existing LISP implementation of
approximation for the description logics ALC and ALE by integrating
two optimization techniques: (1) a special treatment of certain
well-behaved (so called "nice") concepts and (2) implementation of the
so-called "lazy unfolding" of acyclic TBoxes. Both implementations
should then also be evaluated and compared.
Tutor: Anni-Yasmin Turhan.
- (2) Semantic
Annotation of Webpages and description of the experiences made.
The semantic web is a current initiative for generating new
W3C standards that allow to
annotate WWW pages with a machine-understandable description
of their content. Obviously, such a semantic annotation would
facilitate the implementation of more exact search engines
and allow the deployment of all kinds of autonomous agents
on the web. The purpose of this project is to semantically
annotate the web pages of the chair for automata theory using
the currently emerging OWL standard, and to
give a detailed discussion of the experiences made.
Tutor: Carsten Lutz,
- S. Bechhofer, L. Carr, C. Goble, S. Kampa, T. Miles-board.
The Semantics of Semantic Annotation. COHSE: Conceptual Open Hypermedia Service. Annotation for the Semantic Web eds. Siegfried Handschuh and Steffen Staab. IOS Press, Frontiers in Artifical Intelligence and Applications. Vol 96. 2003.
- S. Bechhofer,
I. Horrocks, C. Goble, and R. Stevens. OilEd: a reason-able
ontology editor for the semantic web. In Proc. of the Joint German
Austrian Conference on AI, number 2174 in Lecture Notes In
Artificial Intelligence, pages 396-408. Springer-Verlag, 2001.
Concept generator for description logics.
- to evaluate the quality of imlemented DL reasoning systems,
it is very useful
to generate a large amount of formulas with certain characteristics.
The goal of this project is to implement a generator for description
logic concepts (i.e., formulas) that takes several parameters,
such as nesting depth and number of atomic concepts, and randomly
generates a set of concepts in accordance with the input parameters.
Tutor: Jan Hladik
- Ian P. Gent and Toby Walsh. Beyond
NP: The QSAT Phase Transition. Proceedings of AAAI-99, 1999.
- I. Horrocks, P. F. Patel-Schneider, and R. Sebastiani. An analysis
of empirical testing for modal decision procedures. Logic Journal
of the IGPL, 8(3):293-323, 2000.
Implementation of a matching algorithm for the Description Logic ALN.
- A matching problem comprises a concept description and a
so-called concept pattern, i.e., a concept description with
variables. Matching a concept pattern against a concept description
means finding a substitution of the occurring variables by concept
descriptions such that the original concept description is subsumed by
the instantiated concept pattern.
Since matching in the Description Logic ALN is theoretically
well-examined this topic focusses on the implementation of the
relevant algorithm in LISP and on the evaluation w.r.t. run-time
Tutor: Sebastian Brandt
- F. Baader, R. Küsters, A. Borgida, and
D. McGuinness. Matching in Description Logics. Journal of Logic and
Computation, 9(3):411-447, 1999.
- S. Brandt. Matching under Side Conditions in Description Logics. Diploma thesis, RWTH Aachen, Germany, 2000.
- Guy L., Jr. Steele. Common Lisp: The Language.
Unification in Equational Theories.
- An important problem in the area of Term Rewriting is
unification of two terms modulo an equational theory. This problem is
in general. There is a complete procedure to solve E-unification problems,
but this procedure does not halt for all inputs.
On the other hand, if we look for a solution with an equational proof of
a given length n and E is non-subterm-collapsing,
then the E-unification procedure
becomes a decision procedure.
The project requires implementing the
procedure that takes as input an equational theory, a goal equation and
a natural number n, and gives as output
an equational proof of length n of the solved goal, if it exists, or
a negative answer if it does not exist.
Tutor: Barbara Morawska
- B. Morawska. Completeness of E-unification with eager Variable Elimination.
LTCS-Report 03-03, Chair for Automata Theory, Institute for Theoretical
Dresden University of Technology, Germany, 2003. See