Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics
Rafael Peñaloza, Barış Sertkaya · Frontiers in artificial intelligence and applications · 2010
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-Liteℋcore, DL-Liteℋkromand DL-Liteℋ𝒩hornfragments such minimal subsets are efficiently enumerable with polynomial delay, but for the DL-Liteboolfragment they cannot be enumerated in output polynomial time unless P = NP. We also show that interestingly, for the DL-Liteℋ𝒩horn