Computing the least common subsumer in the description logic EL w.r.t. terminological cycles with descriptive semantics

Franz BaaderFranz Baader

Download

Franz Baader
Computing the least common subsumer in the description logic EL w.r.t. terminological cycles with descriptive semantics
Proceedings of the 11th International Conference on Conceptual Structures, ICCS 2003, volume 2746 of Lecture Notes in Artificial Intelligence, 117-130, 2003. Springer

Details
Bibtex

KurzfassungAbstract
Computing the least common subsumer (lcs) is one of the most prominent non-standard inference in description logics. Baader, Kuesters, and Molitor have shown that the lcs of concept descriptions in the description logic EL always exists and can be computed in polynomial time. In the present paper, we try to extend this result from concept descriptions to concepts defined in a (possibly cyclic) EL-terminology interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, the lcs need not exist. However, we are able to define possible candidates P_k (kgeq 0) for the lcs, and can show that the lcs exists iff one of these candidates is the lcs. Since each of these candidates is a common subsumer, they can also be used to approximate the lcs even if it does not exist. In addition, we give a sufficient condition for the lcs to exist, and show that, under this condition, it can be computed in polynomial time.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaaderICCS03,
  author = {Franz {Baader}},
  booktitle = {Proceedings of the 11th International Conference on Conceptual Structures, {ICCS 2003}},
  pages = {117--130},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Computing the least common subsumer in the description logic {$\cal EL$} w.r.t.\ terminological cycles with descriptive semantics},
  volume = {2746},
  year = {2003},
}