Decidability and complexity of threshold description logics induced by concept similarity measures
Franz Baader, Oliver Fernández Gil · 2017
In a recent research paper, we have proposed an extension of the lightweight Description Logic (DL) εL in which concepts can be defined in an approximate way. To this purpose, the notion of a graded membership function m, which instead of a Boolean membership value 0 or 1 yields a membership degree from the interval [0, 1], was introduced. Threshold concepts can then, for example, require that an individual belongs to a concept C with degree at least 0.8. Reasoning in the threshold DL τε;L(m) obtained this way of course depends on the employed graded membership function m. The paper defines a specific such function, called deg, and determines the exact complexity of reasoning in τε;L(deg). In addition, it shows how concept similarity measures (CSMs) ∼ satisfying certain properties can be used to define graded membership functions m∼, but it does not investigate the complexity of reasoning in the induced threshold DLs τε;L(m∼). In the present paper, we start filling this gap. In particular, we show that computability of ∼ implies decidability of τε;L(m∼), and we introduce a class of CSMs for which reasoning in the induced threshold DLs has the same complexity as in τε;L(deg).