TY - GEN
T1 - First-order disjunctive logic programming vs normal logic programming
AU - Zhou, Yi
PY - 2015
Y1 - 2015
N2 - In this paper, we study the expressive power of firstorder 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 NP ≠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.
AB - In this paper, we study the expressive power of firstorder 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 NP ≠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.
KW - artificial intelligence
KW - first-order logic
KW - logic programming
UR - http://handle.uws.edu.au:8081/1959.7/uws:33470
M3 - Conference Paper
SN - 9781577357384
SP - 3292
EP - 3298
BT - Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015): 25-31 July, 2015, Buenos Aires, Argentina
PB - AAAI Press / International Joint Conferences on Artificial Intelligence
T2 - International Joint Conference on Artificial Intelligence
Y2 - 25 July 2015
ER -