On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles
This work addresses foundational complexity issues in knowledge representation and reasoning, providing precise computational bounds for logics used in ontology-based systems, though it is incremental in extending known results to new query types.
The paper tackles the problem of query entailment in description logics with transitive roles and number restrictions, showing that both unrestricted entailment of regular path queries and finite entailment of positive existential queries have tight 2EXPTIME upper bounds for extensions with nominals or inverse roles.
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).