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

Vortrag von Bartosz Bednarczyk

Veranstaltungsort: online
Beginn: 6. Mai 2021 um 13:00
Ende: 6. Mai 2021 um 14:30
Event series: Research Seminar Logic and AI
iCal

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