Data Complexity in Expressive Description Logics with Path Expressions
Authors: Bartosz Bednarczyk
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 co NEXPTIMEcompleteness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ. |
| Researcher Affiliation | Academia | Bartosz Bednarczyk Computational Logic Group, TU Dresden, Germany Institute of Computer Science, University of Wrocław, Poland |
| Pseudocode | Yes | Algorithm 1: Quasi-Forest Satisfiability in ZOIQ Input: A ZOIQ-KB K := (A, T ). Output: True iff K is quasi-forest satisfiable. 1 Turn T into Scott s normal form. // L. 13. 2 Compute the set ST . // L. 16. 3 Guess a K-summary S. // L. 14. 4 Return False if S is clearing-consistent. // L. 15. 5 Foreach a ind(K) do compute the (T , S,a)-ghost-summary Sa and return False if Sa ST . 6 Return True. |
| Open Source Code | No | No explicit statement about open-source code or links to repositories for the methodology described. |
| Open Datasets | No | The paper does not describe experiments using specific datasets, as it focuses on theoretical complexity analysis. |
| Dataset Splits | No | The paper focuses on theoretical analysis and does not describe dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software dependencies with version numbers for reproducing experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe specific experimental setup details such as hyperparameters or training configurations. |