On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
Tomasz Gogacz, Víctor Gutiérrez-Basulto, Yazmín Ibáñez-García, Jean Christoph Jung, Filip Murlak
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1719-1725.
https://doi.org/10.24963/ijcai.2019/238
We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Logics for Knowledge Representation