Polynomial time reasoning in a Description Logic with existential restrictions, GCI axioms, and—what else?
Sebastian Brandt · European Conference on Artificial Intelligence · 2004
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 ℇL, 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 ℇL 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. implication of the first result is that reasoning over the widely used medical terminology SNOMED is possible in polynomial time.