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

From International Center for Computational Logic
Toggle side column

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
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
  • 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}
}