Forschungsprojekte Grundlagen im WS 2014/2015

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

Die Einführungsveranstaltung

findet am 22. Oktober um 14:50 im Raum 3027 statt. Die Teilnahme an der Einführungsveranstaltung ist notwendig für die Teilnahme am Praktikum. Falls Ihnen eine Teilnahme nicht möglich ist, nehmen Sie bitte Kontakt mit Anni-Yasmin Turhan auf.

Position im Studienplan

Für der Master in Informatik wird dieses Forschungsprojekt im Modul INF-PM-FPG (im Umfang von 8 SWS) angeboten und es gibt 12 Punkte dafür.

Voraussetzungen

Kenntnisse der Aussagenlogik sind notwendig.
Kenntnisse aus folgenden Vorlesungen sind hilfreich:
- Formale Systeme
- Theoretische Informatik und Logik
- Description Logics

Organisation

In einer Einführungsveranstaltung (siehe oben) werden verschiedene Themen vorgestellt. Die interessierten Studenten können dann ein Thema zur Bearbeitung auswählen. Studenten, die an einer Teilnahme am Forschungspraktikum interessiert sind, jedoch an der Einführungsveranstaltung nicht teilnehmen können, sollten Anni-Yasmin Turhan kontaktieren. Jedem Studenten wird abhängig vom gewählten Thema ein Tutor zugewiesen. Während des Semesters werden regelmäßige Treffen des Studenten und seines Tutors abgehalten. Am Ende des Semesters präsentiert der Student die Ergebnisse des Forschungsprojektes in einem Vortrag.

Sprache

Die Abschlusspräsentation kann in deutsch oder englisch gehalten werden.

Pflichten der Teilnehmer

Die Teilnehmer sollten die relevante Literatur lesen und diese mit ihrem Tutor diskutieren, um mit dem gewählten Thema vertraut zu werden. Die ggf. nötige Implementierungsarbeit (falls vorhanden) sollte in einer strukturierten Weise ausgeführt werden, und muss ordentlich dokumentiert werden. Falls ein Thema von zwei oder mehr Studenten bearbeitet wird, dann ist das Aneignen von Fähigkeiten zur Gruppenarbeit ein weiteres Ziel des Praktikums. Die Ergebnisse des Forschungsprojekts müssen in einem Bericht (~25 Seiten) beschrieben und in einem Vortrag (~30 Minuten) am Semesterende präsentiert werden.
Weiterhin sind die Teilnehmer verpflichtet, genügend Zeit für die Durchführung des Forschungsprojektes zu reservieren. Die unbedingte Frist zur Beendigung des Forschungspraktikums ist der Beginn des folgenden Semesters, d.h. die Bearbeitungszeit für das Praktikums beträgt ein Semester inklusive der vorlesungsfreien Zeit. Es obliegt dem teilnehmenden Studenten, das Praktikum rechtzeitig zu beginnen und Termine mit dem Tutor für regelmäßige Besprechungen während des Semesters zu vereinbaren.

Themen

Bei der Themenauswahl berücksichtigen Sie bitte Ihr vorhandenes Wissen. Falls Sie bespielsweise ein Thema im Fachgebiet Beschreibungslogik wählen möchten, dann sollten Sie idealerweise an der Vorlesung "Description Logics" teilgenommen haben bevor Sie das Praktikum beginnen.

(1) Endliche Herbrand-Modelle für Hornklauseln

Man kann die Existenz eines endlichen Herbrand-Modells für bestimmte Mengen von prädikatenlogischen Anti-Hornklauseln in exponentieller Zeit entscheiden. Dieses Entscheidungsproblem ist außerdem ExpTime-hart. Das Ziel dieses Praktikums ist es, die Komplexität des analogen Problems für Mengen von Hornklauseln zu bestimmen. Dazu soll ein Algorithmus entwickelt und/oder untere Schranken mittels eines Härtebeweises gefunden werden und diese Ergebnisse dann auf die Kombination von Horn- und Anti-Hornklauseln zu erweitern.

Es werden grundlegende Kenntnisse über Prädikatenlogik sowie Komplexitätstheorie vorausgesetzt.

Tutor: Stefan Borgwardt

(2) Endliche Herbrand-Modelle für Anti-Hornklauseln

Das Ziel dieses Praktikums ist es, einen Algorithmus zu implementieren, der die Existenz endlicher Herbrand-Modelle für bestimmte Mengen von prädikatenlogischen Anti-Hornklauseln entscheidet. Das Programm soll an vielfältigen Eingabeproblemen getestet werden. Die Programmiersprache kann frei gewählt werden.

Es werden grundlegende Kenntnisse über Prädikatenlogik sowie gute Programmierfähigkeiten vorausgesetzt.

Tutor: Stefan Borgwardt

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

Dieses Thema zielt auf die Implementierung und Evaluierung von Methoden zur Berechnung des kleinsten gemeinsamen Oberbegriff (least common subsumer) und speziellster Begriff (most specific concept) in der leicht-gewichtigen Beschreibungslogik ELgfp, d.h. EL interpretiert mit größter Fixpunkt Semantik. Im Unterschied zu Standard-EL mit deskriptiver Semantik existieren diese speziellsten Verallgemeinerungen stets in ELgfp und können in polynomieller Zeit berechnet werden. Weiterhin sollte der Student einen Vergleich mit speziellsten Generalisierungen bezüglich deskriptiver Semantik und mit Rollentiefe-beschränkten speziellsten Generalisierungen bezüglich deskriptiver Semantik machen.

Grundlegende Kenntnisse von Beschreibungslogiken und gute Programmierfähigkeiten werden erwartet. Für eine einfachere Verwendung und Integration mit existierenden Programmen (z.B. Elk, Protégé usw.) sollte das Programm auf der OWL API aufbauen.

Literatur
[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) Formale Begriffsanalyse & Aussagenlogik: Von Pseudo-Inhalten zu Implikations-Basen

Ziel dieses Themas ist die Formulierung einer minimalen Theorie von Implikationen, die in einer gegebenen Menge von aussagenlogischen Modellen gelten, und aus der alle anderen Implikationen folgen, die in der gegebenen Modellmenge gelten. Hierfür ist ein Isomorphismus zwischen aussagenlogischen Modellmengen und formalen Kontexten nötig, um bestehende Ergebnisse aus der formalen Begriffsanalyse zu verwenden. Weiterhin sollte der Student einen Algorithmus zur Berechnung der Implikations-Basis angeben. Die Resultate können auf aussagenlogische Basen erweitert werden.

Grundlegende Kenntnisse in Aussagenlogik und Mengenlehre werden erwartet. Weitere Kenntnisse in Logik oder Ordnungstheorie können hilfreich sein.

Literatur
[1] Bernhard Ganter und Rudolf Wille: Formale Begriffsanalyse - Mathematische Grundlagen, Springer Verlag, Heidelberg 1996
[2] Bernhard Ganter: Attribute Exploration with Background Knowledge

Tutor: Francesco Kriegel

Weitere Themen werden noch hinzugefügt.