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

Bartosz BednarczykBartosz Bednarczyk, Sebastian RudolphSebastian Rudolph

Download

Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
In Mantas Simkus, Grant E. Weddell, eds., Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings, June 2019. CEUR-WS.org

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{DBLP:conf/dlog/BednarczykR19,
  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 32nd International Workshop on Description Logics,
               Oslo, Norway, June 18-21, 2019.},
  year      = {2019},
  crossref  = {DBLP:conf/dlog/2019},
  url       = {http://ceur-ws.org/Vol-2373/paper-4.pdf},
  timestamp = {Fri, 30 Aug 2019 13:15:06 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/dlog/BednarczykR19},
  bibsource = {dblp computer science bibliography, https://dblp.org} 
}
@proceedings{DBLP:conf/dlog/2019,
  editor    = {Mantas Simkus and
               Grant E. Weddell},
  title     = {Proceedings of the 32nd International Workshop on Description Logics,
               Oslo, Norway, June 18-21, 2019},
  series    = {{CEUR} Workshop Proceedings},
  volume    = {2373},
  publisher = {CEUR-WS.org},
  year      = {2019},
  url       = {http://ceur-ws.org/Vol-2373},
  urn       = {urn:nbn:de:0074-2373-7},
  timestamp = {Fri, 30 Aug 2019 13:15:06 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/dlog/2019},
  bibsource = {dblp computer science bibliography, https://dblp.org} 
}