Description logics (DL) is a well-known knowledge representation formalism. DL have been applied as reasoning framework in diverse domains, including the Semantic Web and Context-Aware Systems. It is an open question whether or not the expressive description logic ALCQIOreg is decidable. This logic is equipped with negation, conjunction, regular roles, inverse roles, nominals and qualified number restrictions. In this paper, we show this logic is decidable when interpreted over tree models. Moreover, it is shown that μALCTIO, which is known to be undecidable and that subsumes ALCQIOreg, is in EXPTIME in the case of tree models. μALCTIO generalizes regular roles with fixed-point constructors, and qualified number restrictions with arithmetic constraints. This EXPTIME bound holds even if the arithmetic constraints are coded in binary. Furthermore, we show that knowledge base reasoning, TBoxes and ABoxes, can also be decided in EXPTIME. These results are achieved via a polynomial reduction to the satisfiability problem of the propositional modal i-calculus extended with Presburger arithmetic constraints interpreted over tree models.
['Everardo Bárcenas', 'Guillermo Molero', 'Gabriela Sánchez', 'Edgard Benítez-Guerrero', 'Carmen Mezura-Godoy']
Reasoning on expressive description logics with arithmetic constraints