Return to search

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

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:79320
Date31 May 2022
CreatorsBrandt, Sebastian
PublisherTechnische Universität Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/acceptedVersion, doc-type:report, info:eu-repo/semantics/report, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relationurn:nbn:de:bsz:14-qucosa2-785040, qucosa:78504

Page generated in 0.0023 seconds