Data Complexity in Expressive Description Logics With Path Expressions

Bartosz Bednarczyk
6/11/2024
cs.LOcs.AIcs.CC

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default ā€” verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

CSPs with Few Alien Constraints

77% match2024

Minimal Model Reasoning in Description Logics: Don't Try This at Home!

73% match2025

The Computational Complexity of Satisfiability in State Space Models

71% match2025

Finding hardness reductions automatically using SAT solvers

71% match1 repo22024

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning

71% match2024

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations

70% match2025

Cite this paper

@article{bednarczyk2024data,
  title  = {Data Complexity in Expressive Description Logics With Path Expressions},
  author = {Bartosz Bednarczyk},
  year   = {2024},
  eprint = {2406.07095},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2406.07095v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2406.07095.svg)](https://codeofpaper.com/paper/2406.07095)

Discussion