Data complexity of answering conjunctive queries over SHIQ knowledge bases

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

An algorithm for answering conjunctive queries over SHIQ knowledge bases that is coNP in data complexity is given. The algorithm is based on the tableau algorithm for reasoning with individuals in SHIQ. The blocking conditions of the tableau are weakened in such a way that the set of models the modified algorithm yields suffices to check query entailment. The modified blocking conditions are based on the ones proposed by Levy and Rousset for reasoning with Horn Rules in the description logic ALCNR.
Technical Report, 22 pages

Keywords

Logic in Computer Science, Artificial Intelligence, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/99371

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0507059
 http://arxiv.org/abs/cs/0507059

Collections

arXiv