# A New Tractable Description Logic under Categorical Semantics

arXiv: https://arxiv.org/abs/2505.08916 · HTML: https://mlsanity.com/paper/2505.08916/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 57 references that are in the map.
- First posted on arXiv 13 May 2025.

## Builds on (most cited first, 3 of 3)

- [Category-theoretical Semantics of the Description Logic ALC (extended version)](https://mlsanity.com/paper/2110.08837/) (2021)
- [Reasoning in the Description Logic ALC under Category Semantics](https://mlsanity.com/paper/2205.04911/) (2022)
- [Hypertableau Reasoning for Description Logics](https://mlsanity.com/paper/1401.3485/) (2014)

## Built on by (most cited first, 1 of 1)

- [TAPO-Description Logic for Information Behavior: Refined OBoxes, Inference, and Categorical Semantics](https://mlsanity.com/paper/2604.21172/) (2026)

## Abstract (arXiv)

Biomedical ontologies contain numerous concept or role names involving negative knowledge such as lackspart, absenceof. Such a representation with labels rather than logical constructors would not allow a reasoner to interpret lackspart as a kind of negation of haspart. It is known that adding negation to the tractable Description Logic (DL) EL allowing for conjunction, existential restriction and concept inclusion makes it intractable since the obtained logic includes implicitly disjunction and universal restriction which interact with other constructors. In this paper, we propose a new extension of EL with a weakened negation allowing to represent negative knowledge while retaining tractability. To this end, we introduce categorical semantics of all logical constructors of the DL SH including EL with disjunction, negation, universal restriction, role inclusion and transitive roles. The categorical semantics of a logical constructor is usually described as a set of categorical properties referring to several objects without using set membership. To restore tractability, we have to weaken semantics of disjunction and universal restriction by identifying independent categorical properties that are responsible for intractability, and dropping them from the set of categorical properties. We show that the logic resulting from weakening semantics is more expressive than EL with the bottom concept, transitive roles and role inclusion.