Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics

Bartosz BednarczykBartosz Bednarczyk

Download

Bartosz Bednarczyk
Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics
Technical Report, arXiv.org, August 2021. Technical Report

Details
Bibtex

KurzfassungAbstract
We present a unified approach to (both finite and unrestricted) worst-case optimal entailment of (unions of) conjunctive queries (U)CQs in the wide class of "locally-forward" description logics. The main technique that we employ is a generalisation of Lutz's spoiler technique, originally developed for CQ entailment in ALCHQ. Our result closes numerous gaps present in the literature, most notably implying ExpTime-completeness of (U)CQ-querying for any superlogic of ALC contained in ALCHbregQ, and, as we believe, is abstract enough to be employed as a black-box in many new scenarios.
Bemerkung: Note: ArXiV
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@techreport{B2021,
  author      = {Bartosz Bednarczyk},
  title       = {Lutz's Spoiler Technique Revisited: A Unified Approach to
                 Worst-Case Optimal Entailment of Unions of Conjunctive Queries
                 in Locally-Forward Description Logics},
  institution = {arXiv.org},
  year        = {2021},
  month       = {August}
}