As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
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[Hscr ]core, DL-Lite[Hscr ]krom and DL-Lite[Hscr ][Nscr ]horn 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-Lite[Hscr ][Nscr ]horn 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.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.