Winter Term 2013/14

Course Description

The students will work on a small scientific project. Depending on the specific topic the students will review the related literature, identify the appropriate methodology and solve the given tasks. The respective steps will be discussed in regular meetings with the supervisor. At the end of the semester the students will present their results in a talk and submit a project report.

Lecturer:  Prof. Sebastian Rudolph, Dr. Sarah Alice Gaggl, Michaël Thomazo

Modules:  MCL-P

Status:  basic unit

SWS (lecture/tutorial/practical):  0/0/4

Examination method:  talk and project report

Prerequisites:

• none

Organization

In the initial meeting on Monday 14.10.2013, 13:00-14:30 (DS 4) in room INF E005 the possible topics will be presented. Students should choose a topic and work on it during the semester. There will be regular meetings with the supervisor. At the end of the semester the students will present their results in a talk (30 min) and write a project report (ca. 15 pages).
Slides of the initial meeting: project_group_topics.pdf.

Topics

1. Description Logics

• 1.1 Inconsistency Handling in Description Logics
  Dealing with inconsistencies is a very important challenge in practical scenarios of ontology use. The aim of this project is to understand, present, and formally compare different approaches to inconsistency in DLs (such as paraconsistent reasoning and reasoning with maximal consistent subontologies).
• 1.2 Reducing Grounded Circumscription to Standard Reasoning
  Mainstream Description Logics do not support nonmonotony. In some modelling tasks, however, this feature is required. One approach to add "mild" nonmonotonic modelling to DLs is called "grounded circumscription". In this project, efficient ways of reasoning with grounded-circumscription in DLs, based on existing reasoning machinery for standard DLs, shall be explored.
• 1.3 Creating a DL-Ontology
  Over the past years, Description Logic research has investigated a large variety of logics ranging from very lightweight DLs like EL to the very expressive DLs that underly today's most advanced ontology modelling language OWL. The goal of this project is to create an ontology describing these diverse logics and their properties (such as expressiveness, reasoning complexity, etc.) in a way that the reasoning capabilities of OWL can be used to infer information about these properties from given facts.

2. Formal Concept Analysis

• 2.1 Meta-Modelling in FCA
  FCA starts from a very basic data structure comprising objects and their attributes. Sometimes, however, it is benefitial to also define attributes of attributes (so-called meta attributes). The general goal of this project is to develop a framework for this kind of Meta-Modelling in FCA, including formal definitions and appropriate visualizations.
• 2.2 Executing Logical Operations on Formal Contexts via OBDDs
  Formal contexts, the basic data structures in FCA can be described as Boolean functions. On the other hand, Boolean functions can be expressed (often very efficiently) via ordered binary decision diagrams (OBDDs). This project aims at expressing standard operations on formal contexts by means of OBDDs and comparing the efficiency to the standard algorithms.
• 2.3 Finding the Least Common Subsumer of Closure Operators
  There are several ways to encode closure operators. Two such encodings are formal contexts and implication sets. Finding the lcs of two closure operators expressed as implication sets is easy, one just computes the union of the two sets. Finding the lcs in the contextual encoding seems less straightforward. This project is dedicated to this task.

3. Abstract Argumentation

• 3.1 Implementing labeling-based Algorithms
  Labeling-based algorithms are used as direct implementation method to compute solutions for abstract Argumentation Frameworks (AFs). Such labelings distinguish different statuses of arguments, e.g. whether they are accepted, attacked or undecided. The label of one argument has immediate implications for its neighbors. The idea of labeling-based algorithms is to use these implications to prune the search space. The task of this topic is to implement an existing algorithm for a specific semantics and evaluate the performance compared to the system ASPARTIX.
• 3.2 Approximating Skeptical Preferred Reasoning
  Most of the argumentation semantics are intractable, in particular skeptical reasoning for preferred semantics is Π₂^P-complete. On attempt to improve the performance is to approximate the acceptance of an argument from easier decision problems from other semantics. The task is to analyse and implement algorithms for top-down and bottom-up approximations and compare the approaches to existing implementations.

4. Existential Rules

• 4.1 Query-dependent Algorithm
  Most of the proposed approaches for Ontology-Based Data Access do not take into account properties of the query. Some approaches propose a modification of the ruleset with respect to the query. Goal of the project: understand, implement and/or extend these approaches.
• 4.2 Adaptation of Current Algorithms to Data Updates
  Current algorithms for OBDA would recompute everything from scratch if the data changes. Data updates is a classical topic in database theory. Goal of the project: understand how updates are dealt with in databases and lift the approaches to some existential rules algorithms.