Polynomial Time Reasoning in a Description Logic with Existential Restrictions, GCI Axioms, and—What Else?

Sebastian BrandtSebastian Brandt

Download

Sebastian Brandt
Polynomial Time Reasoning in a Description Logic with Existential Restrictions, GCI Axioms, and—What Else?
In R. López de Mantáras and L. Saitta, eds., Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004), 298-302, 2004. IOS Press

Details
Bibtex

KurzfassungAbstract
In the area of Description Logic (DL) based knowledge representation, research on reasoning w.r.t. general terminologies has mainly focused on very expressive DLs. Recently, though, it was shown for the DL EL, providing only the constructors conjunction and existential restriction, that the subsumption problem w.r.t. cyclic terminologies can be decided in polynomial time, a surprisingly low upper bound. In this paper, we show that even admitting general concept inclusion (GCI) axioms and role hierarchies in EL terminologies preserves the polynomial time upper bound for subsumption. We also show that subsumption becomes co-NP hard when adding one of the constructors number restriction, disjunction, and `allsome', an operator used in the DL K-Rep. An interesting implication of the first result is that reasoning over the widely used medical terminology SNOMED is possible in polynomial time.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Brandt-ECAI-2004,
  author = {Sebastian {Brandt}},
  booktitle = {Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004)},
  editor = {R. L{\'o}pez de {Mant{\'a}ras} and L. {Saitta}},
  pages = {298--302},
  publisher = {IOS Press},
  title = {Polynomial Time Reasoning in a Description Logic with Existential Restrictions, {GCI} Axioms, and---What Else?},
  year = {2004},
}