A Faithful Integration of Description Logics with Logic Programming

Abstract

Developing model-based automatic debugging strategies has been an active research area for several years. We present a model-based debugging approach that is based on Abstract Interpretation, a technique borrowed from program analysis. The Abstract Interpretation mechanism is integrated with a classical model-based reasoning engine. We test the approach on sample programs and provide the first experimental comparison with earlier models used for debugging. The results show that the Abstract Interpretation based model provides more precise explanations than previous models or standard non-model based approaches.Integrating description logics (DL) and logic programming (LP) would produce a very powerful and useful formalism. However, DLs and LP are based on quite different principles, so achieving a seamless integration is not trivial. In this paper, we introduce hybrid MKNF knowledge bases that faithfully integrate DLs with LP using the logic of Minimal Knowledge and Negation as Failure (MKNF) [Lifschitz, 1991]. We also give reasoning algorithms and tight data complexity bounds for several interesting fragments of our logic.