- Titel
- Decidability and Complexity of Threshold Description Logics Induced by Concept Similarity Measures
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-795856
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 16-07
- Erstveröffentlichung
- 2016
- DOI
- https://doi.org/10.25368/2022.229
- Abstract (EN)
- In a recent research paper, we have proposed an extension of the lightweight 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 T EL(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 T EL(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 T EL(m~). In the present paper, we start filling this gap. In particular, we show that computability of ~ implies decidability of T EL(m~), and we introduce a class of CSMs for which reasoning in the induced threshold DLs has the same complexity as in T EL(deg).
- Freie Schlagwörter (DE)
- Subsumtion, EL-Konzept, Beschreibungslogik, Entscheidbarkeit
- Freie Schlagwörter (EN)
- subsumption, EL-concept, description logic, decidability
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-795856
- Veröffentlichungsdatum Qucosa
- 20.06.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0