First-Order Disjunctive Logic Programming vs Normal Logic Programming
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3292-3297.
Abstract
In this paper, we study the expressive power of first-order disjunctive logic programming (DLP) and normal logic programming (NLP) under the stable model semantics. We show that, unlike the propositional case, first-order DLP is strictly more expressive than NLP. This result still holds even if auxiliary predicates are allowed, assuming that NP not equals to coNP. On the other side, we propose a partial translation from first-order DLP to NLP via unfolding and shifting, which suggests a sound yet incomplete approach to implement DLP via NLP solvers. We also identify some NLP definable subclasses, and conjecture to exactly capture NLP definability by unfolding and shifting.
@inproceedings{ijcai2015p464,
title = {First-Order Disjunctive Logic Programming vs Normal Logic Programming},
author = {Zhou, Yi},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {3292--3297},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/464},
}
TY - CPAPER TI - First-Order Disjunctive Logic Programming vs Normal Logic Programming AU - Zhou, Yi T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 3292 EP - 3297 UR - https://ijcai.org/proceedings/2015/464 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
