Data complexity of answering conjunctive queries over SHIQ knowledge bases

Simple item page
dc.creatorde la Fuente, M. Magdalena Ortiz
dc.creatorCalvanese, Diego
dc.creatorEiter, Thomas
dc.creatorFranconi, Enrico
dc.date2005-07-22
dc.date.accessioned2026-07-07T06:33:57Z
dc.date.available2026-07-07T06:33:57Z
dc.descriptionAn 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.
dc.descriptionTechnical Report, 22 pages
dc.identifierhttps://arxiv.org/abs/cs/0507059
dc.identifierhttp://arxiv.org/abs/cs/0507059
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99371
dc.subjectLogic in Computer Science
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.titleData complexity of answering conjunctive queries over SHIQ knowledge bases
dc.typetext

Files

Collections

arXiv