LATPub384: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract= | |Abstract= We have shown recently that, in extensions of ALC that involve inverse roles, conjunctive query answering is harder than satisfiability: it is 2-ExpTime-complete in general and NExpTime-hard if queries are connected and contain at least one answer variable. In this paper, we show that, in SHIQ without inverse roles (and without transitive roles in the query), conjunctive query answering is only ExpTime-complete and thus not harder than satisfiability. We also show that the mentioned NExpTime-lower bound is tight. | ||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 46: | Zeile 37: | ||
year = {2008}, | year = {2008}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
Two Upper Bounds for Conjunctive Query Answering in SHIQ
Carsten LutzCarsten Lutz
Carsten Lutz
Two Upper Bounds for Conjunctive Query Answering in SHIQ
Proceedings of the 21st International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008
Two Upper Bounds for Conjunctive Query Answering in SHIQ
Proceedings of the 21st International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008
- KurzfassungAbstract
We have shown recently that, in extensions of ALC that involve inverse roles, conjunctive query answering is harder than satisfiability: it is 2-ExpTime-complete in general and NExpTime-hard if queries are connected and contain at least one answer variable. In this paper, we show that, in SHIQ without inverse roles (and without transitive roles in the query), conjunctive query answering is only ExpTime-complete and thus not harder than satisfiability. We also show that the mentioned NExpTime-lower bound is tight. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Lutz-DL08,
author = {Carsten {Lutz}},
booktitle = {Proceedings of the 21st International Workshop on Description Logics ({DL2008})},
series = {CEUR-WS},
title = {Two Upper Bounds for Conjunctive Query Answering in SHIQ},
volume = {353},
year = {2008},
}
