Abstract
Among the most expressive knowledge representation formalisms are the description logics of the Z
family. For well-behaved fragments of ZOIQ, entailment of positive two-way regular path queries
is well known to be 2EXPTIME-complete under
the proviso of unary encoding of numbers in cardinality constraints. We show that this assumption
can be dropped without an increase in complexity
and EXPTIME-completeness can be achieved when
bounding the number of query atoms, using a novel
reduction from query entailment to knowledge base
satisfiability. These findings allow to strengthen
other results regarding query entailment and query
containment problems in very expressive description logics. Our results also carry over to GC2
, the
two-variable guarded fragment of first-order logic
with counting quantifiers, for which hitherto only
conjunctive query entailment has been investigated