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

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

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

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


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