Techreport3017
Published: 2011
Mai
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe
Archivierungsnummer:3017
Kurzfassung
Recently, non-standard reasoning problems have gained the attention from the research community. Amongst others, different approaches to computing the Uniform Interpolation for concepts and knowledge bases expressed in $\mathcal{H}$orn extensions of $\mathcal{EL}$ were proposed. Further, it was shown, that Uniform Interpolation may not exist in the presence of terminological cycles and sufficient, but not necessary conditions for its existence in general terminologies were identified. The aim of this paper is to investigate, using the example of the Uniform Interpolation in $\mathcal{EL}$, the existence of the result for a particular class of non-standard reasoning problems in $\mathcal{EL}$ and some of its $\mathcal{H}$orn
extensions. In this paper, we show that the Uniform Interpolation always exists in $\mathcal{EL}$ enriched with least and greatest fixpoint constructors and show how it can be computed by reducing the problem to the computation of most general subconcept and most specific superconcept. Moreover, we give the conditions for the existence of the Uniform Interpolation in $\mathcal{EL}$ and provide a complete algorithm for its computation.