Treating Role Assertions as First-class Citizens in Repair and Error-tolerant Reasoning

Research output: Contribution to book/conference proceedings/anthology/report โ€บ Conference contribution โ€บ Contributed โ€บ peer-review



Errors in Description Logic (DL) ontologies are often detected when reasoning yields unintuitive consequences. The question is then how to repair the ontology in an optimal way, i.e., such that the unwanted consequences are removed, but a maximal set of the unobjected consequences is kept. Error-tolerant reasoning does not commit to a single optimal repair: brave reasoning asks whether the consequence is entailed by some repair and cautious reasoning whether it is entailed by all repairs. Previous research on repairing ABoxes w.r.t. TBoxes formulated in the DL ๐“”๐“› has developed methods for computing optimal repairs, and has recently also determined the complexity of error-tolerant reasoning: brave reasoning is in P and cautious reasoning is in coNP. However, in this work the unwanted consequences were restricted to being ๐“”๐“› instance assertions. In the present paper, we show that the mentioned results can be extended to a setting where also role assertions can be required to be removed. Our solution is based on a two-stage approach where first the unwanted role assertions and then the unwanted concept assertions are removed. We also investigate the complexity of error-tolerant reasoning w.r.t. classical repairs, which are maximal subsets of the ABox that do not have the unwanted consequences, and show that, in this setting, brave reasoning is NP-complete and cautious reasoning is coNP-complete.


Original languageEnglish
Title of host publicationProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing (SAC '23), March 27โ€“31, 2023, Tallinn, Estonia
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (electronic)9781450395175
Publication statusPublished - 27 Mar 2023

External IDs

Scopus 85162885637
Mendeley f4549afd-4bb5-32eb-af3d-f3fa6cf55353
ORCID /0000-0002-4049-221X/work/142247973
ORCID /0000-0002-9047-7624/work/142251262
ORCID /0000-0003-0219-0330/work/153109420


Research priority areas of TU Dresden

Subject groups, research areas, subject areas according to Destatis

ASJC Scopus subject areas


  • description logic, error-tolerant reasoning, repairs