ECAI 2004 Conference Paper

[full paper]

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

Sebastian Brandt

In the area of Description Logic (DL) based knowledge representation, research on reasoning w.r.t.\ general terminologies has been 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 extending EL by inverse roles and admitting general concept inclusion (GCI) axioms at the same time 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.

Keywords: description logics, knowledge representation

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