×

Extending the description logic \(\tau\mathcal{EL}(\deg)\) with acyclic TBoxes. (English) Zbl 1403.68251

Kaminka, Gal A. (ed.) et al., ECAI 2016. 22nd European conference on artificial intelligence, The Hague, Netherlands, August 29 – September 2, 2016. Proceedings. Including proceedings of the accompanied conference on prestigious applications of intelligent systems (PAIS 2016). In 2 volumes. Amsterdam: IOS Press (ISBN 978-1-61499-671-2/pbk; 978-1-61499-672-9/ebook). Frontiers in Artificial Intelligence and Applications 285, 1096-1104 (2016).
Summary: In a previous paper, we have introduced an extension of the lightweight description logic \(\mathcal{EL}\) that allows us to define concepts in an approximate way. For this purpose, we have defined a graded membership function \(\deg\), which for each individual and concept yields a number in the interval \([0, 1]\) expressing the degree to which the individual belongs to the concept. Threshold concepts \(C_{\sim t}\) for \(\sim\;\in\{<,\leq,>,\geq\}\) then collect all the individuals that belong to \(C\) with degree \(\sim t\). We have then investigated the complexity of reasoning in the description logic \(\tau\mathcal{EL}(\deg)\), which is obtained from \(\mathcal{EL}\) by adding such threshold concepts. In the present paper, we extend these results, which were obtained for reasoning without TBoxes, to the case of reasoning w.r.t. acyclic TBoxes. Surprisingly, this is not as easy as might have been expected. On the one hand, one must be quite careful to define acyclic TBoxes such that they still just introduce abbreviations for complex concepts, and thus can be unfolded. On the other hand, it turns out that, in contrast to the case of \(\mathcal{EL}\), adding acyclic TBoxes to \(\tau\mathcal{EL}(\deg)\) increases the complexity of reasoning by at least on level of the polynomial hierarchy.
For the entire collection see [Zbl 1352.68013].

MSC:

68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI