Complexity of the Description Logic ALCM
arXiv:1511.03749v16 citations
Originality Incremental advance
AI Analysis
This work addresses a theoretical complexity issue for researchers in description logics and knowledge representation, providing a foundational result.
The paper tackled the problem of checking consistency of knowledge bases in the Description Logic ALCM, proving that this problem is ExpTime-complete.
In this paper we show that the problem of checking consistency of a knowledge base in the Description Logic ALCM is ExpTime-complete. The M stands for meta-modelling as defined by Motz, Rohrer and Severi. To show our main result, we define an ExpTime Tableau algorithm as an extension of an algorithm for checking consistency of a knowledge base in ALC by Nguyen and Szalas.