An Automata-based algorithm for description logics around SRIQ.
Magdalena Ortiz · 2008
Abstract. In this paper we use automata-theoretic techniques to tightly characterize the worst-case complexity of the knowledge base satisfiability problem for the very expressive Description Logics (DLs) ALCQIb + reg and SRIQ. The logic ALCQIb + reg extends ALC with qualified number restrictions, inverse roles, safe Boolean role expressions, regular expressions over roles, and concepts of the form ∃P.Self in the style of SRIQ, a well known DL closely related to the new Semantic Web Standard OWL 2. By reducing its knowledge base satisfiability problem to the emptiness test of an automaton on infinite trees, we show that all these additions do not increase the worst case complexity of ALC and provide a decision procedure for one of the most expressive DLs that have been shown to be decidable in exponential time. We also close the open question of the precise complexity of reasoning in SRIQ, exploiting a reduction from the SRIQ knowledge base satisfiability problem into the ALCQIb + reg one. 1