%0 Conference Paper %1 Bednarczyk2019-sm %A Bednarczyk, Bartosz %A Rudolph, Sebastian %B Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence %C California %D 2019 %I International Joint Conferences on Artificial Intelligence Organization %K %T Worst-case optimal querying of very expressive description logics with path expressions and succinct counting %X 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.

@inproceedings{Bednarczyk2019-sm, 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.}, added-at = {2024-09-10T11:56:37.000+0200}, address = {California}, author = {Bednarczyk, Bartosz and Rudolph, Sebastian}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2e92bfa5a92e0824869768543c2703a5a/scadsfct}, booktitle = {Proceedings of the {Twenty-Eighth} International Joint Conference on Artificial Intelligence}, conference = {Twenty-Eighth International Joint Conference on Artificial Intelligence \{IJCAI-19\}}, interhash = {39d76f87d6dc44445a036997f04e570c}, intrahash = {e92bfa5a92e0824869768543c2703a5a}, keywords = {}, location = {Macao, China}, month = aug, publisher = {International Joint Conferences on Artificial Intelligence Organization}, timestamp = {2024-09-10T15:15:57.000+0200}, title = {Worst-case optimal querying of very expressive description logics with path expressions and succinct counting}, year = 2019 }