Navigating the ℰℒ Subsumption Hierarchy
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
The 𝓔𝓛 subsumption hierarchy consists of all 𝓔𝓛 concept descriptions and is partially ordered by subsumption. In order to navigate within this hierarchy, one can go up to subsumers and down to subsumees. We analyze how smallest steps can be made. Specifically, we show how all upper neighbors as well as all lower neighbors of a given 𝓔𝓛 concept description can be efficiently computed, where two concepts are neighbors if one subsumes the other and there is no third concept in between. We further show that the hierarchy contains very long chains: there is a sequence of concepts Cₙ with size linear in n such that each chain of neighbors from ⊤ to Cₙ has at least n-fold exponential length. As applications, we provide a template for determining upper complexity bounds for deciding whether a concept is maximally general or maximally specific w.r.t. a property, we construct a metric on the set of all 𝓔𝓛 concept descriptions, we introduce a similarity measure that fulfills the triangle inequality, and we conclude that an uninformed search for a target concept by subsequently computing neighbors or, equivalently, along an ideal refinement operator is not feasible in practical applications.
Details
Originalsprache | Englisch |
---|---|
Titel | Proceedings of the 34th International Workshop on Description Logics (DL 2021), Hybrid Event, Bratislava, Slovakia, September 19-22, 2021 |
Redakteure/-innen | Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt |
Herausgeber (Verlag) | CEUR-WS.org |
Band | 2954 |
Publikationsstatus | Veröffentlicht - 19 Sept. 2021 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | CEUR Workshop Proceedings |
---|
Workshop
Titel | International Workshop on Description Logics 2021 |
---|---|
Kurztitel | DL 2021 |
Veranstaltungsnummer | 34 |
Dauer | 19 - 22 September 2021 |
Bekanntheitsgrad | Internationale Veranstaltung |
Ort | Comenius University |
Stadt | Bratislava |
Land | Slowakei |
Externe IDs
ORCID | /0000-0003-0219-0330/work/153109371 |
---|