Exponential Speedup in UL Subsumption Checking Relative to General TBoxes for the Constructive Semantics

Computational Proteomics

计算机科学;物理学

Michael Mendler ; Stephan Scheele

Others  :  http://CEUR-WS.org/Vol-477/paper_8.pdf
PID  :  50193

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

The complexity of the subsumption problem in description logics can vary widely with the choice of the syntactic fragment and the semantic interpretation. In this paper we show that the constructive semantics of concept descriptions, which includes the classical descriptive semantics as a special case, offers exponential speed-up in the existential-disjunctive fragment UL of ALC.