LATPub442: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 9: | Zeile 9: | ||
|Year=2010 | |Year=2010 | ||
|Month= | |Month= | ||
|Booktitle=Proceedings of the 2010 International Workshop on Description Logics ( | |Booktitle=Proceedings of the 2010 International Workshop on Description Logics (DL2010) | ||
|Editor=Volker | |Editor=Volker Haarslev and David Toman and Grant Weddell | ||
|Note= | |Note= | ||
|Organization= | |Organization= | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=We investigate the computational complexity of axiom pinpointing in the | |Abstract=We investigate the computational complexity of axiom pinpointing in the DL-Lite family, which has been very popular due to its success in efficiently accessing large data and answering complex queries. We consider the problem of explaining TBox reasoning. We investigate in detail the complexity of enumerating MinAs in a DL-Lite TBox for a given consequence of this TBox. We show that for DL-Lite_core^{H}, DL-Lite_krom^{H} and DL-Lite_horn^{N} TBoxes MinAs are efficiently enumerable with polynomial delay, but for DL-Lite_bool they cannot be enumerated in output-polynomial time unless P = NP. | ||
DL-Lite family, which has been very popular due to its success in efficiently accessing large data and answering complex queries. | |||
We consider the problem of explaining TBox reasoning. We investigate in detail the | |||
complexity of enumerating MinAs in a DL-Lite TBox for a given consequence of this | |||
TBox. We show that for DL-Lite_core^{H}, DL-Lite_krom^{H} and DL-Lite_horn^{N} | |||
TBoxes MinAs are efficiently enumerable with polynomial delay, but for DL-Lite_bool | |||
they cannot be enumerated in output-polynomial time unless P = NP. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 45: | Zeile 38: | ||
year = {2010}, | year = {2010}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Complexity of Axiom Pinpointing in the DL-Lite Family
Rafael PeñalozaRafael Peñaloza, Barış SertkayaBarış Sertkaya
Rafael Peñaloza, Barış Sertkaya
Complexity of Axiom Pinpointing in the DL-Lite Family
In Volker Haarslev and David Toman and Grant Weddell, eds., Proceedings of the 2010 International Workshop on Description Logics (DL2010), volume 573 of CEUR-WS, 2010
Complexity of Axiom Pinpointing in the DL-Lite Family
In Volker Haarslev and David Toman and Grant Weddell, eds., Proceedings of the 2010 International Workshop on Description Logics (DL2010), volume 573 of CEUR-WS, 2010
- KurzfassungAbstract
We investigate the computational complexity of axiom pinpointing in the DL-Lite family, which has been very popular due to its success in efficiently accessing large data and answering complex queries. We consider the problem of explaining TBox reasoning. We investigate in detail the complexity of enumerating MinAs in a DL-Lite TBox for a given consequence of this TBox. We show that for DL-Lite_core^{H}, DL-Lite_krom^{H} and DL-Lite_horn^{N} TBoxes MinAs are efficiently enumerable with polynomial delay, but for DL-Lite_bool they cannot be enumerated in output-polynomial time unless P = NP. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ PeSe-DL10,
author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
booktitle = {Proceedings of the 2010 International Workshop on Description Logics ({DL2010})},
editor = {Volker {Haarslev} and David {Toman} and Grant {Weddell}},
series = {CEUR-WS},
title = {Complexity of Axiom Pinpointing in the DL-Lite Family},
volume = {573},
year = {2010},
}
