On the Closure of Description Logics under Substitutions

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.
 

Online Copy

Online version

BibTeX Entry

@inproceedings{brenas16:_closur_descr_logic_subst,
  author    = {Jon Ha{\"{e}}l Brenas and
               Rachid Echahed and
               Martin Strecker},
  title     = {On the Closure of Description Logics under Substitutions},
  booktitle = {Proceedings of the 29th International Workshop on Description Logics,
               Cape Town, South Africa, April 22-25, 2016.},
  year      = 2016,
  editor    = {Maurizio Lenzerini and
               Rafael Pe{\~{n}}aloza},
  url       = {http://ceur-ws.org/Vol-1577/paper_47.pdf}
}