Navigating the ℰℒ Subsumption Hierarchy

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publicationProceedings of the 34th International Workshop on Description Logics (DL 2021), Hybrid Event, Bratislava, Slovakia, September 19-22, 2021
EditorsMartin Homola, Vladislav Ryzhikov, Renate A. Schmidt
PublisherCEUR-WS.org
Volume2954
Publication statusPublished - 19 Sept 2021
Peer-reviewedYes

Publication series

SeriesCEUR Workshop Proceedings

Workshop

TitleInternational Workshop on Description Logics 2021
Abbreviated titleDL 2021
Conference number34
Duration19 - 22 September 2021
Degree of recognitionInternational event
LocationComenius University
CityBratislava
CountrySlovakia

External IDs

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