AAAI Publications, Twelfth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
On the Progression Semantics and Boundedness of Answer Set Programs
Yan Zhang, Yi Zhou

Last modified: 2010-04-27


In this paper, we propose a progression semantics for first-order answer set programs. Based on this new semantics, we are able to define the notion of boundedness for answer set programming. We prove that boundedness coincides with the notions of recursion-free and loop-free under program equivalence, and is also equivalent to first-order definability of answer set programs on arbitrary structures.


answer set programming, nonmonotonic logics, first-order definability

Full Text: PDF