On the Closure of Description Logics under Substitutions

Abstract

We investigate the extension of Description Logics (DL) with a notion of "substitution". Substitutions naturally arise when reasoning about programs which modify graph structures that are characterized by DLs. They constitute also a means to express concept and role modifications such as addition or deletion of individuals (respectively, pairs of individuals) to or from concepts (respectively, roles). After a formal definition of substitutions, we conduct a systematic study of a wide range of DLs with the purpose of proving or disproving conservativity of an extension of the respective DL with substitutions. The resulting classification is a gauge of the expressiveness of description logics and their adequacy for reasoning about change of graph structures.