All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
From International Center for Computational Logic
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
Bartosz BednarczykBartosz Bednarczyk, Robert FerensRobert Ferens, Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja
Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1719--1725, July 2020. International Joint Conferences on Artificial Intelligence
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
In Christian Bessiere, eds., Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 1719--1725, July 2020. International Joint Conferences on Artificial Intelligence
- KurzfassungAbstract
The chase is a famous algorithmic procedure in database theory with numerous applications in ontology-mediated query answering. We consider static analysis of the chase termination problem, which asks, given set of TGDs, whether the chase terminates on all input databases. The problem was recently shown to be undecidable by Gogacz et al. for sets of rules containing only ternary predicates. In this work, we show that undecidability occurs already for sets of single-head TGD over binary vocabularies. This question is relevant since many real-world ontologies, e.g., those from the Horn fragment of the popular OWL, are of this shape. - Weitere Informationen unter:Further Information: Link
- Projekt:Project: DeciGUT
- Forschungsgruppe:Research Group: Computational LogicComputational Logic
@inproceedings{BFO2020,
author = {Bartosz Bednarczyk and Robert Ferens and Piotr
Ostropolski-Nalewaja},
title = {All-Instances Oblivious Chase Termination is Undecidable for
Single-Head Binary {TGDs}},
editor = {Christian Bessiere},
booktitle = {Proceedings of the 29th International Joint Conference on
Artificial Intelligence and the 17th Pacific Rim International
Conference on Artificial Intelligence (IJCAI 2020)},
series = {ijcai.org},
publisher = {International Joint Conferences on Artificial Intelligence},
year = {2020},
month = {July},
pages = {1719--1725},
doi = {10.24963/ijcai.2020/238}
}