Finite Model Reasoning in Hybrid Classes of Existential Rules

Finite Model Reasoning in Hybrid Classes of Existential Rules

Georg Gottlob, Marco Manna, Andreas Pieris

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1831-1837. https://doi.org/10.24963/ijcai.2018/253

Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i.e., a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i.e., query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Multidisciplinary Topics and Applications: Databases