Reasoning in ELH w.r.t. General Concept Inclusion Axioms

S. BrandtS. Brandt

Download

S. Brandt
Reasoning in ELH w.r.t. General Concept Inclusion Axioms
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-04-03, 2004. LTCS-Report

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.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Brandt-LTCS-04-03,
  address = {Germany},
  author = {S. {Brandt}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-04-03},
  title = {Reasoning in $\mathcal{ELH}$ w.r.t.\ General Concept Inclusion Axioms},
  type = {LTCS-Report},
  year = {2004},
}