Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
From International Center for Computational Logic
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
Talk by Bartosz Bednarczyk
- Location: APB 3027
- Start: 30. July 2019 at 1:00 pm
- End: 30. July 2019 at 1:30 pm
- Research group: Computational Logic
- Event series: KBS Seminar
- iCal
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 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 first order logic with counting quantifiers, for which hitherto only conjunctive query entailment has been investigated.