Decidability and Complexity of Threshold Description Logics Induced by Concept Similarity Measures

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung


In a recent research paper, we have proposed an extension of the light-weight Description Logic (DL) EL 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 tel(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 tel(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 tel(m ). In the present paper, we start filling this gap. In particular, we show that computability of implies decidability of tel(m ), and we introduce a class of CSMs for which reasoning in the induced threshold DLs has the same complexity as in tel(deg).


TitelProceedings of the Symposium on Applied Computing, SAC 2017
Herausgeber (Verlag)ACM Press
PublikationsstatusVeröffentlicht - 2017


TitelThe 32nd ACM SIGAPP Symposium On Applied Computing
Dauer4 - 6 April 2017

Externe IDs

Scopus 85013364190
ORCID /0000-0002-4049-221X/work/142247922