Data Complexity in Expressive Description Logics With Path Expressions
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910481853186048 |
|---|---|
| author | Bednarczyk, Bartosz |
| author_facet | Bednarczyk, Bartosz |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07095 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Data Complexity in Expressive Description Logics With Path Expressions Bednarczyk, Bartosz Logic in Computer Science Artificial Intelligence Computational Complexity 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. |
| title | Data Complexity in Expressive Description Logics With Path Expressions |
| topic | Logic in Computer Science Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2406.07095 |