ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

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.


[prev] [tofc] [next]


ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).