Soundness preserving approximation for TBox reasoning in R

Yuan Ren, Jeff Z. Pan, Yuting Zhao

Research output: Contribution to journalConference articlepeer-review

2 Citations (Scopus)


TBox reasoning in description logics is hard. For example, reasoning in SROIQ (i.e. OWL2-DL) is N2ExpTime-complete; even with R, a fragment of SROIQ supporting ALC GCIs and role chains, the complexity of reasoning is 2ExpTime-hard. Although various optimisation techniques have been applied, existing tableau-based DL reasoners are still inefficient in dealing with arbitrary GCIs especially when complex role chains present. In this paper, we present a soundness preserving approximation for TBox reasoning in R. The main idea is to convert R ontologies to EL+ with an additional complement table maintaining the complementary relations between named concepts. Since existing benchmarks do not focus on complex GCIs and RIs, we propose a new set of testing ontologies for TBox reasoning inR and our preliminary evaluation shows that a naive implementation of our complement-integrated TBox reasoning algorithm outperforms existing reasoners on most of these ontologies.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalCEUR Workshop Proceedings
Publication statusPublished - 1 Jan 2009
Event22nd International Workshop on Description Logics, DL 2009 - Oxford, United Kingdom
Duration: 27 Jul 200930 Jul 2009 (Link to Official Website)

Bibliographical note

This work has been partially supported by the European Project Marrying Ontologies and Software Technologies (MOST ICT 2008-216691).


Dive into the research topics of 'Soundness preserving approximation for TBox reasoning in R'. Together they form a unique fingerprint.

Cite this