zbMATH — the first resource for mathematics

Matching in the description logic \(\mathcal{FL}_0\) with respect to general TBoxes. (English) Zbl 1415.68216
Barthe, Gilles (ed.) et al., LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning, Awassa, Ethiopia, November 17–21, 2018. Selected papers. Manchester: EasyChair. EPiC Ser. Comput. 57, 76-94 (2018).
Summary: Matching concept descriptions against concept patterns was introduced as a new inference task in description logics two decades ago, motivated by applications in the classic system. Shortly afterwards, a polynomial-time matching algorithm was developed for the DL \(\mathcal{FL}_0\). However, this algorithm cannot deal with general TBoxes (i.e., finite sets of general concept inclusions). Here we show that matching in \(\mathcal{FL}_0\) w.r.t. general TBoxes is in ExpTime, which is the best possible complexity for this problem since already subsumption w.r.t. general TBoxes is ExpTime-hard in \(\mathcal{FL}_0\). We also show that, w.r.t. a restricted form of TBoxes, the complexity of matching in \(\mathcal{FL}_0\) can be lowered to PSpace.
For the entire collection see [Zbl 1407.68021].

68T27 Logic in artificial intelligence
68T30 Knowledge representation
Full Text: DOI