Project Group Computational Logic

Lehrveranstaltung mit SWS 0/0/4 (Vorlesung/Übung/Praktikum) in WS 2014

Dozent

Sebastian Rudolph

Tutor

Umfang (SWS)

0/0/4

Module

MCL-P

Leistungskontrolle

Hausarbeit
Referat

Information

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.

Organization

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

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

Argumentation is one of the major fields in Non-Monotonic Reasoning and Artificial Intelligence, where Abstract the Argumentation Framework (AF) as introduced by Dung in 1995, is one the most popular formalism.

3.1 Optimizing ASP Encodings for Abstract Argumentation Frameworks: The Answer-Set Programming (ASP) based system ASPARTIX is one of the first systems in for this formalism which is capable to deal with a wide range of semantics. The goal of the project is to optimize existing ASP encodings for our participation in the first International Competition on Computational Models of Argumentation (ICCMA) in 2015.
3.2 Implementing the Decomposition Schema for Abstract Dialectical Frameworks: Abstract Dialecital Frameworks (ADFs) are a generalization of Dungs AFs. As the computational complexity of the dedicated reasoning problems is in general higher than for AFs, a common approach is to decompose the framework into smaller subproblems and compose the solutions of the subproblems to an overall solution. The task of the project is to implement a system which computes the models of various semantics based on a given decomposition schema for ADFs.
3.3 Visualization of Solutions in Abstract Argumentation Frameworks: Abstract argumentation frameworks (AFs) are typically represented as directed graphs. There can be many solutions for an AF depending on the specific semantics. The goal of this project is to analyze possible ways how to represent and navigate through the whole solution space for an AF with respect to a semantics.

4. Existential Rules

Ontology-Based Query Answering (OBQA) aims at querying databases while taking some domain knowledge into account. An introduction to the topic may be found there: An Introduction to Ontology-Based Query Answering with Existential Rules. Topics regarding this problem include (but are not limited to) the following two.

4.1 Optimization of rule storage: For large ontologies such as SNOMED-CT (bio-medical domain), current query rewriting techniques do not scale. The goal of this project is to study efficient storage techniques for large ontologies, with the aim of facilitating query rewriting.
4.2 Query-Driven algorithm: The choice of a relevant algorithm for OBQA is mostly based on the kind of ontologies that are considered. However, the query may also be relevant: some simple algorithms that are incomplete in the general case may be sufficient for the given query. The goal of this project is to study the related literature, and to improve/implement/come up with different ideas depending on the student's tastes.