Rewriting in Description Logics Using Terminologies.
Franz Baader, Ralf Molitor · 1999
We consider the inference problem of computing (minimal) rewritings of concept descriptions using defined concepts from a terminology. We introduce a general framework for this problem and instantiate it with the small description logic FL 0 , which provides us with conjunction and value restrictions. We show that the decision problem induced by the minimal rewriting problem is NP-complete for FL 0 . 1 Motivation Informally, the problem of rewriting a concept given a terminology can be stated as follows: given a TBox T and a concept description C that does not contain concept names defined in T , can this description be rewritten into an equivalent "better" description D by using (some of) the names defined in T ? Better may mean shorter, but one can also imagine other optimality criteria. In the formal framework of rewriting introduced in Section 2 of this paper, we will not fix such an optimality criterion, and we will allow T , C, and D to be built over different DLs. However, wh...