LATPub440: 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=We investigate the computational complexity of axiom pinpointing, | |Abstract=We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used. | ||
which is the task of finding minimal subsets of a Description Logic | |||
knowledge base that have a given consequence. We consider the problems | |||
of enumerating such subsets with and without order, and show hardness results | |||
that already hold for the propositional Horn fragment, or for the Description | |||
Logic | |||
enumeration problems for these fragments that extend to more expressive logics. | |||
In particular we show that hardness of these problems depends not | |||
only on expressivity of the fragment but also on the shape of the axioms used. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 46: | Zeile 37: | ||
year = {2010}, | year = {2010}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
Rafael PeñalozaRafael Peñaloza, Barış SertkayaBarış Sertkaya
Rafael Peñaloza, Barış Sertkaya
On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
In Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski, eds., Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010. AAAI Press
On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
In Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski, eds., Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010. AAAI Press
- KurzfassungAbstract
We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ PeSe-KR10,
author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
booktitle = {Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning ({KR 2010})},
editor = {Fangzhen {Lin} and Ulrike {Sattler} and Miroslaw {Truszczynski}},
publisher = {AAAI Press},
title = {On the Complexity of Axiom Pinpointing in the EL Family of Description Logics},
year = {2010},
}
