European Master's Program in Computational Logic

25 February 2015

Best EMCL Thesis Award 2014

Mr Tobias Kaminski received the price for the best EMCL master thesis 2014 during the EMCL students workshop at NOVA in February 2015.

Other candidates were Mr Andreas Fellner with his thesis on 'Space & Congruence Compression of Proofs' and Mr Enrique Matos with his thesis on 'Increasing the Robustness of SAT Solving with Machine Learning Techniques'.

Title of Mr Kaminski's thesis: 'Hybrid MKNF Knowledge Bases Under  Paraconsistent Well-Founded Semantics'


Ontologies formalized by means of Description Logics (DLs) and rules in the form of Logic Programs (LPs) are two prominent formalisms in the field of Knowledge Repre- sentation and Reasoning. While DLs adhere to the Open World Assumption and are suited for taxonomic reasoning, LPs implement reasoning under the Closed World Assumption, so that default knowledge can be expressed. However, for many applications it is useful to have a means that allows reasoning over an open domain and expressing rules with exceptions at the same time. Hybrid MKNF knowledge bases make such a means avail- able by formalizing DLs and LPs in a common logic, the Logic of Minimal Knowledge and Negation as Failure (MKNF).

Since rules and ontologies are used in open environments such as the Semantic Web, inconsistencies cannot always be avoided. This poses a problem due to the Principle of Ex- plosion, which holds in classical logics. Paraconsistent Logics offer a solution to this issue by assigning meaningful models even to contradictory sets of formulas. Consequently, paraconsistent semantics for DLs and LPs have been investigated intensively. Our goal is to apply the paraconsistent approach to the combination of DLs and LPs in hybrid MKNF knowledge bases.

In this thesis, a new six-valued semantics for hybrid MKNF knowledge bases is intro- duced, extending the three-valued approach by Knorr et al., which is based on the well- founded semantics for logic programs. Additionally, a procedural way of computing paraconsistent well-founded models for hybrid MKNF knowledge bases by means of an alternating fixpoint construction is presented and it is proven that the algorithm is sound and complete w.r.t. the model-theoretic characterization of the semantics. Moreover, it is shown that the new semantics is faithful w.r.t. well-studied paraconsistent semantics for DLs and LPs, respectively, and maintains the efficiency of the approach it extends.