Exploiting forwardness: Satisfiability and Query-Entailment in Forward Guarded Fragment

Bartosz BednarczykBartosz Bednarczyk

Bartosz Bednarczyk
Exploiting forwardness: Satisfiability and Query-Entailment in Forward Guarded Fragment
Proceedings of the 17th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2021), to appear

Details
Bibtex

KurzfassungAbstract
We study the complexity of two standard reasoning problems for Forward Guarded Logic (FGF), obtained as a restriction of the Guarded Fragment in which variables appear in atoms in a specific order. We show that FGF enjoys the higher-arity-forest-model property, which results in ExpTime-completeness of its (finite) knowledge-base satisfiability problem. Moreover, we show that FGF is well-suited for knowledge representation. By employing a generalisation of the spoiler technique, we prove that the conjunctive query entailment problem for FGF remains in ExpTime. We believe that our results are quite unusual as FGF is, up to our knowledge, the first decidable fragment of First-Order Logic, extend- ing standard description logics, that offers unboundedly many variables and higher-arity relations while keeping its complexity surprisingly low.
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{B2021,
  author    = {Bartosz Bednarczyk},
  title     = {Exploiting forwardness: Satisfiability and Query-Entailment in
               Forward Guarded Fragment},
  booktitle = {Proceedings of the 17th Edition of the European Conference on
               Logics in Artificial Intelligence (JELIA 2021)},
  year      = {2021},
  month     = {May}
}