# Data Complexity in Expressive Description Logics With Path Expressions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 40 references that are in the map.
- First posted on arXiv 11 Jun 2024.

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

- [Logical Separability of Labeled Data Examples under Ontologies](https://mlsanity.com/paper/2007.01610/) (2020)
- [Nested Regular Path Queries in Description Logics](https://mlsanity.com/paper/1402.7122/) (2014)
- [ExpTime Tableaux with Global Caching for Hybrid PDL](https://mlsanity.com/paper/1705.00848/) (2017)

## Abstract (arXiv)

We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests and establish its NP-completeness. This completes the data complexity landscape for decidable fragments of ZOIQ, and reproves known results on decidable fragments of OWL2 (SR family). Using the same technique, we establish coNEXPTIME-completeness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ.