We investigate the complexity of axiom pinpointing for different members of the DL-Lite family of Description Logics. More precisely, we consider the problem of enumerating all minimal subsets of a given DL-Lite knowledge base that have a given consequence. We show that for the DL-Litecore, DL-Litekrom and DL-Litehorn fragments such minimal subsets are efficiently enumerable with polynomial delay, but for the DL-Litebool fragment they cannot be enumerated in output polynomial time unless P = NP. We also show that interestingly, for the DL-Litehorn fragment such minimal sets can be enumerated in reverse lexicographic order with polynomial delay, but it is not possible in the forward lexicographic order since computing the first one is already coNP-hard.
Penaloza, R., Sertkaya, B. (2010). Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics. In ECAI 2010 : 19th European Conference on Artificial Intelligence : including prestigious applications of artificial intelligence (PAIS-2010) : proceedings (pp.29-34). IOS Press [10.3233/978-1-60750-606-5-29].
Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics
Penaloza, R
;
2010
Abstract
We investigate the complexity of axiom pinpointing for different members of the DL-Lite family of Description Logics. More precisely, we consider the problem of enumerating all minimal subsets of a given DL-Lite knowledge base that have a given consequence. We show that for the DL-Litecore, DL-Litekrom and DL-Litehorn fragments such minimal subsets are efficiently enumerable with polynomial delay, but for the DL-Litebool fragment they cannot be enumerated in output polynomial time unless P = NP. We also show that interestingly, for the DL-Litehorn fragment such minimal sets can be enumerated in reverse lexicographic order with polynomial delay, but it is not possible in the forward lexicographic order since computing the first one is already coNP-hard.File | Dimensione | Formato | |
---|---|---|---|
PeSe-ECAI10.pdf
accesso aperto
Tipologia di allegato:
Submitted Version (Pre-print)
Dimensione
250.73 kB
Formato
Adobe PDF
|
250.73 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.