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

Bartosz BednarczykBartosz Bednarczyk, Sebastian RudolphSebastian Rudolph

Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
In Sarit Kraus, eds., Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI 2019), ijcai.org, 1530--1536, August 2019. International Joint Conferences on Artificial Intelligence

Details
Bibtex

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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational 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},
  editor    = {Sarit Kraus},
  booktitle = {Proceedings of the Twenty-Eighth International Joint Conference
               on Artificial Intelligence (IJCAI 2019)},
  series    = {ijcai.org},
  publisher = {International Joint Conferences on Artificial Intelligence},
  year      = {2019},
  month     = {August},
  pages     = {1530--1536},
  doi       = {10.24963/ijcai.2019/212}
}