Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets

Tim LyonTim Lyon, Sebastian RudolphSebastian Rudolph

Tim Lyon, Sebastian Rudolph
Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
In Sarah Alice Gaggl, Maria Vanina Martinez, Magdalena Ortiz, eds., Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023), Lecture Notes in Computer Science, 2023. Springer International Publishing

Details
Bibtex

KurzfassungAbstract
This paper establishes alternative characterizations of very expressive classes of existential rule sets with decidable query entailment. We consider the notable class of greedy bounded-treewidth sets (gbts) and a new, generalized variant, called weakly gbts (wgbts). Revisiting and building on the notion of derivation graphs, we define (weakly) cycle-free derivation graph sets ((w)cdgs) and employ elaborate proof-theoretic arguments to obtain that gbts and cdgs coincide, as do wgbts and wcdgs. These novel characterizations advance our analytic proof-theoretic understanding of existential rules and will likely be instrumental in practice.
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{LR2023,
  author    = {Tim Lyon and Sebastian Rudolph},
  title     = {Derivation-Graph-Based Characterizations of Decidable Existential
               Rule Sets},
  editor    = {Sarah Alice Gaggl and Maria Vanina Martinez and Magdalena Ortiz},
  booktitle = {Proceedings of the 18th Edition of the European Conference on
               Logics in Artificial Intelligence (JELIA 2023)},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer International Publishing},
  year      = {2023}
}