The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2EXPTIME-hard

Bartosz BednarczykBartosz Bednarczyk, Sebastian RudolphSebastian Rudolph

Bartosz Bednarczyk, Sebastian Rudolph
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2EXPTIME-hard
Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), 5495-5502, February 2022

Details
Bibtex

KurzfassungAbstract
In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking as the infer encing problem of primary interest. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be EXPTIME-complete and hence not harder than satisfiability. This does not change when the logic is extended by certain features (such as counting or role hierarchies), whereas adding others (inverses, nominals or transitivity together with role-hierarchies) turns CQ answering exponentially harder. We contribute to this line of results by showing the surprising fact that even extending ALC by just the Self operator – which proved innocuous in many other contexts – increases the complexity of CQ entailment to 2EXPTIME. As common for this type of problem, our proof establishes a reduction from alternating Turing machines running in exponential space, but several novel ideas and encoding tricks are required to make the approach work in that specific, restricted setting.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{BR2022,
  author    = {Bartosz Bednarczyk and Sebastian Rudolph},
  title     = {The Price of Selfishness: Conjunctive Query Entailment for
               {ALCSelf} is 2EXPTIME-hard},
  booktitle = {Proceedings of the 36th {AAAI} Conference on Artificial
               Intelligence (AAAI 2022)},
  series    = {5495-5502},
  year      = {2022},
  month     = {February},
  doi       = {10.1609/aaai.v36i5.20488}
}