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

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

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

Vortrag von Bartosz Bednarczyk
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, extending standard description logics, that offers unboundedly many variables and higher-arity relations while keeping its complexity surprisingly low.


This talk is based on an accepted paper submission to JELIA 2021 and will take approximately 30 minutes. It will take place online via BigBlueButton. To access the room, take one of the following links:


with ZIH-login:

https://selfservice.zih.tu-dresden.de/l/link.php?m=86974&p=57992a96


without ZIH-login:

https://selfservice.zih.tu-dresden.de/link.php?m=86974&p=f38fa613