Approximation and Difference in Description Logics
LuFG Theoretische Informatik, RWTH Aachen, Sebastian Brandt, Ralf Küsters, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel, Anni-Yasmin Turhan, LuFG Theoretische Informatik, RWTH Aachen · 2001
Approximation is a new inference service in Description Logics first mentioned by Baader, Küsters, and Molitor. Approximating a concept, defined in one Description Logic, means to translate this concept to another concept, defined in a second typically less expressive Description Logic, such that both concepts are as closely related as possible with respect to subsumption. The present paper provides the first in-depth investigation of this inference task. We prove that approximations from the Description Logic ALC to ALE always exist and propose an algorithm computing them. As a measure for the accuracy of the approximation, we introduce a syntax-oriented difference operator, which yields a concept description that contains all aspects of the approximated concept that are not present in the approximation. It is also argued that a purely semantical difference operator, as introduced by Teege, is less suited for this purpose. Finally, for the logics under consideration, we propose an algorithm computing the difference.