Data Complexity in Expressive Description Logics With Path Expressions
<|reference_start|>Data Complexity in Expressive Description Logics With Path Expressions: 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.<|reference_end|>
@article{bednarczyk2024data,
    title={Data Complexity in Expressive Description Logics With Path Expressions},
    author={Bartosz Bednarczyk},
    journal={arXiv preprint arXiv:2406.07095},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.07095},
    primaryClass={cs.LO cs.AI cs.CC}
}