About the Multi-Head Linear Restricted Chase Termination

Lukas GerlachLukas Gerlach, Lucas LarroqueLucas Larroque, Jerzy MarcinkowskiJerzy Marcinkowski, Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja

ISBN: 978-1-956792-08-9
ISSN: 2334-1033
Download
Slides
DOI Link

Lukas Gerlach, Lucas Larroque, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
About the Multi-Head Linear Restricted Chase Termination
In Magdalena Ortiz,Renata Wassermann,Torsten Schaub, eds., Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR 2025), volume 22 of Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 346-355, October 2025. IJCAI Organization

Details
Bibtex

KurzfassungAbstract
The chase is a ubiquitous algorithm in database theory. However, for existential rules (aka tuple-generating dependencies), its termination is not guaranteed, and even undecidable in general. The problem of termination becomes particularly difficult for the restricted (or standard) chase, for which the order of rule application matters. Thus, decidability of restricted chase termination is still open for many well-behaved classes such as linear or guarded multi-headed rules. We make a step forward by showing that all-instances restricted chase termination is decidable in the linear multi-headed case.
Projekt:Project: Cfaed, CPEC, CeTI, InnoSale, SECAI, ScaDS.AI
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{GLMO2025,
  author    = {Lukas Gerlach and Lucas Larroque and Jerzy Marcinkowski and Piotr
               Ostropolski-Nalewaja},
  title     = {About the Multi-Head Linear Restricted Chase Termination},
  editor    = {Magdalena Ortiz and Renata Wassermann and Torsten Schaub},
  booktitle = {Proceedings of the 22nd International Conference on Principles of
               Knowledge Representation and Reasoning (KR 2025)},
  series    = {Proceedings of the International Conference on Principles of
               Knowledge Representation and Reasoning},
  volume    = {22},
  publisher = {IJCAI Organization},
  year      = {2025},
  month     = {October},
  pages     = {346-355},
  doi       = {10.24963/kr.2025/34}
}