We investigate the computational complexity of axiom pin-pointing, 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.
Penaloza, R., Sertkaya, B. (2010). On the Complexity of Axiom Pinpointing in the EL Family of Description Logics. In Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (KR'10) (pp.280-289). AAAI Press.
On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
Penaloza, R
;
2010
Abstract
We investigate the computational complexity of axiom pin-pointing, 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.File | Dimensione | Formato | |
---|---|---|---|
PeSe-KR10.pdf
accesso aperto
Tipologia di allegato:
Submitted Version (Pre-print)
Dimensione
207.07 kB
Formato
Adobe PDF
|
207.07 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.