mlsanityData to 7 Oct 2026

Data Complexity in Expressive Description Logics With Path Expressions

arXiv 2406.07095 ↗First posted 11 Jun 2024cs.LO cs.AI cs.CCcited by 0

Not on the map. Why?

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.

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

Builds on

3 of 40 references.

References · 3

  1. 2020Logical Separability of Labeled Data Examples under Ontologiescited by 10
  2. 2014Nested Regular Path Queries in Description Logicscited by 4
  3. 2017ExpTime Tableaux with Global Caching for Hybrid PDLcited by 1

Built on by

Not cited yet.