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

Bartosz BednarczykBartosz Bednarczyk

ISBN: 978-3-030-75775-5
Download
DOI Link

Bartosz Bednarczyk
Exploiting forwardness: Satisfiability and Query-Entailment in Forward Guarded Fragment
In Wolfgang Faber, Gerhard Friedrich, Martin Gebser, Michael Morak, eds., Proceedings of the 17th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2021), volume 12678 of Lecture Notes in Computer Science, 179--193, May 2021. Springer International Publishing

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.
Weitere Informationen unter:Further Information: Link
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},
  editor    = {Wolfgang Faber and Gerhard Friedrich and Martin Gebser and
               Michael Morak},
  booktitle = {Proceedings of the 17th Edition of the European Conference on
               Logics in Artificial Intelligence (JELIA 2021)},
  series    = {Lecture Notes in Computer Science},
  volume    = {12678},
  publisher = {Springer International Publishing},
  year      = {2021},
  month     = {May},
  pages     = {179--193},
  doi       = {10.1007/978-3-030-75775-5_13}
}