  Some of the applications of OWL and RDF (e.g. biomedical knowledge
representation and semantic policy formulation) call for extensions of these
languages with nonmonotonic constructs such as inheritance with overriding.
Nonmonotonic description logics have been studied for many years, however no
practical such knowledge representation languages exist, due to a combination
of semantic difficulties and high computational complexity. Independently,
low-complexity description logics such as DL-lite and EL have been introduced
and incorporated in the OWL standard. Therefore, it is interesting to see
whether the syntactic restrictions characterizing DL-lite and EL bring
computational benefits to their nonmonotonic versions, too. In this paper we
extensively investigate the computational complexity of Circumscription when
knowledge bases are formulated in DL-lite_R, EL, and fragments thereof. We
identify fragments whose complexity ranges from P to the second level of the
polynomial hierarchy, as well as fragments whose complexity raises to PSPACE
and beyond.
