Inproceedings3378: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 6: | Zeile 6: | ||
|Referiert=1 | |Referiert=1 | ||
|Title=Data Complexity in Expressive Description Logics With Path Expressions | |Title=Data Complexity in Expressive Description Logics With Path Expressions | ||
|To appear= | |To appear=0 | ||
|Year=2024 | |Year=2024 | ||
|Month=August | |Month=August | ||
|Booktitle=Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024 | |Booktitle=Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024 | ||
|Pages=3241--3249 | |||
|Publisher=ijcai.org | |Publisher=ijcai.org | ||
}} | }} | ||
| Zeile 17: | Zeile 18: | ||
Using the same technique, we establish coNExpTime-completeness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ. | Using the same technique, we establish coNExpTime-completeness (w.r.t. the combined complexity) of the entailment problem of rooted queries in ZIQ. | ||
|Download=BBE-IJCAI-2024.pdf | |Download=BBE-IJCAI-2024.pdf | ||
|Link=https://www.ijcai.org/proceedings/2024/359 | |||
|Projekt=DeciGUT | |Projekt=DeciGUT | ||
|Forschungsgruppe=Computational Logic | |Forschungsgruppe=Computational Logic | ||
}} | }} | ||
Aktuelle Version vom 22. Oktober 2024, 07:16 Uhr
Data Complexity in Expressive Description Logics With Path Expressions
Bartosz BednarczykBartosz Bednarczyk
Bartosz Bednarczyk
Data Complexity in Expressive Description Logics With Path Expressions
Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024, 3241--3249, August 2024. ijcai.org
Data Complexity in Expressive Description Logics With Path Expressions
Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024, 3241--3249, August 2024. ijcai.org
- KurzfassungAbstract
We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb^self_regOIQ) 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. - Weitere Informationen unter:Further Information: Link
- Projekt:Project: DeciGUT
- Forschungsgruppe:Research Group: Computational LogicComputational Logic
@inproceedings{B2024,
author = {Bartosz Bednarczyk},
title = {Data Complexity in Expressive Description Logics With Path
Expressions},
booktitle = {Proceedings of the 33rd International Joint Conference on
Artificial Intelligence, {IJCAI} 2024},
publisher = {ijcai.org},
year = {2024},
month = {August},
pages = {3241--3249}
}
