Navigating the 𝓔𝓛 Subsumption Hierarchy

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

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

OriginalspracheEnglisch
TitelProceedings of the 34th International Workshop on Description Logics (DL 2021), Hybrid Event, Bratislava, Slovakia, September 19-22, 2021
Redakteure/-innenMartin Homola, Vladislav Ryzhikov, Renate A. Schmidt
Herausgeber (Verlag)CEUR-WS.org
Band2954
PublikationsstatusVeröffentlicht - 19 Sept. 2021
Peer-Review-StatusJa

Publikationsreihe

ReiheCEUR Workshop Proceedings

Workshop

TitelInternational Workshop on Description Logics 2021
KurztitelDL 2021
Veranstaltungsnummer34
Dauer19 - 22 September 2021
BekanntheitsgradInternationale Veranstaltung
OrtComenius University
StadtBratislava
LandSlowakei

Externe IDs

ORCID /0000-0003-0219-0330/work/153109371