Unification in the Description Logic ELHR+ without the Top Concept modulo Cycle-Restricted Ontologies
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Unification has been introduced in Description Logic (DL) as a means to detect redundancies in ontologies. In particular, it was shown that testing unifiability in the DL EL is an NP-complete problem, and this result has been extended in several directions. Surprisingly, it turned out that the complexity increases to PSpace if one disallows the use of the top concept in concept descriptions. Motivated by features of the medical ontology SNOMED CT, we extend this result to a setting where the top concept is disallowed, but there is a background ontology consisting of restricted forms of concept and role inclusion axioms. We are able to show that the presence of such axioms does not increase the complexity of unification without top, i.e., testing for unifiability remains a PSpace-complete problem.
Details
Original language | English |
---|---|
Title of host publication | Automated Reasoning - 12th International Joint Conference, IJCAR 2024, Nancy, France, July 1-6, 2024, Proceedings, Part II |
Editors | Christoph Benzmüller, Marijn J. H. Heule, Renate A. Schmidt |
Publisher | Springer |
Pages | 279-297 |
Number of pages | 19 |
Publication status | Published - 2 Jul 2024 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science |
---|---|
Volume | 14740 |
ISSN | 0302-9743 |
Conference
Title | 12th International Joint Conference on Automated Reasoning |
---|---|
Abbreviated title | IJCAR 2024 |
Conference number | 12 |
Duration | 1 - 6 July 2024 |
Website | |
Degree of recognition | International event |
Location | Université de Lorraine |
City | Nancy |
Country | France |
External IDs
ORCID | /0000-0002-4049-221X/work/163766175 |
---|---|
Scopus | 85200267201 |
Keywords
ASJC Scopus subject areas
Keywords
- Complexity, Description Logics, Unification