# The instance problem and the most specific concept in the description logic EL w.r.t. terminological cycles with descriptive semantics

The instance problem and the most specific concept in the description logic EL w.r.t. terminological cycles with descriptive semantics
Proceedings of the 26th Annual German Conference on Artificial Intelligence, KI 2003, volume 2821 of Lecture Notes in Artificial Intelligence, 64-78, 2003. Springer
• KurzfassungAbstract
Previously, we have investigated both standard and non-standard inferences in the presence of terminological cycles for the description logic EL, which allows for conjunctions, existential restrictions, and the top concept. The present paper is concerned with two problems left open by this previous work, namely the instance problem and the problem of computing most specific concepts w.r.t. descriptive semantics, which is the usual first-order semantics for description logics. We will show that---like subsumption---the instance problem is polynomial in this context. Similar to the case of the least common subsumer, the most specific concept w.r.t. descriptive semantics need not exist, but we are able to characterize the cases in which it exists and give a decidable sufficient condition for the existence of the most specific concept. Under this condition, it can be computed in polynomial time.
• Forschungsgruppe:Research Group: Automatentheorie
The final publication is available at Springer.
@inproceedings{ BaaderKI03,
title = {The instance problem and the most specific concept in the description logic {$\cal EL$} w.r.t.\ terminological cycles with descriptive semantics},