Inproceedings3361

PublikationenPublications

• Nach AutorBy Author
  • Tim LyonTim Lyon
  • Sebastian RudolphSebastian Rudolph
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets

Tim LyonTim Lyon,  Sebastian RudolphSebastian Rudolph

• Download
• Slides
• DOI Link

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 European Conference on Logics in Artificial Intelligence (JELIA 2023), volume 14281 of Lecture Notes in Artificial Intelligence, 369-384, 2023. Springer

• 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

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-031-43619-2_26.

@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 European Conference on Logics in
               Artificial Intelligence (JELIA 2023)},
  series    = {Lecture Notes in Artificial Intelligence},
  volume    = {14281},
  publisher = {Springer},
  year      = {2023},
  pages     = {369-384},
  doi       = {10.1007/978-3-031-43619-2_26}
}