Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting

Bartosz BednarczykBartosz Bednarczyk,  Sebastian RudolphSebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting


Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI'19), August 2019. International Joint Conferences on Artificial Intelligence
  • KurzfassungAbstract
    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 2EXPTIMEcomplete 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 firstorder logic with counting quantifiers, for which hitherto only conjunctive query entailment has been investigated.
  • Projekt:Project: DeciGUT
  • Forschungsgruppe:Research Group: Computational Logic
@inproceedings{BR2019,
  author    = {Bartosz Bednarczyk and Sebastian Rudolph},
  title     = {Worst-Case Optimal Querying of Very Expressive Description Logics
               with Path Expressions and Succinct Counting},
  booktitle = {Proceedings of the 28th International Joint Conference on
               Artificial Intelligence (IJCAI'19)},
  publisher = {International Joint Conferences on Artificial Intelligence},
  year      = {2019},
  month     = {August}
}