# 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].

##### MSC:
 68T27 Logic in artificial intelligence 68T30 Knowledge representation
##### Keywords:
complexity; description logic; matching; tree automata
Full Text: