Navigating the ℰℒ Subsumption Hierarchy
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Title of host publication | Proceedings of the 34th International Workshop on Description Logics (DL 2021), Hybrid Event, Bratislava, Slovakia, September 19-22, 2021 |
Editors | Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt |
Publisher | CEUR-WS.org |
Volume | 2954 |
Publication status | Published - 19 Sept 2021 |
Peer-reviewed | Yes |
Publication series
Series | CEUR Workshop Proceedings |
---|
Workshop
Title | International Workshop on Description Logics 2021 |
---|---|
Abbreviated title | DL 2021 |
Conference number | 34 |
Duration | 19 - 22 September 2021 |
Degree of recognition | International event |
Location | Comenius University |
City | Bratislava |
Country | Slovakia |
External IDs
ORCID | /0000-0003-0219-0330/work/153109371 |
---|