We extend a theorem by Francois Fages about the relationship between the completion semantics and the answer set semantics of logic programs to a class of programs with nested expressions permitted in the bodies of rules. Fages' theorem is important from the perspective of answer set programming: whenever the two semantics are equiva- lent, answer sets can be computed by propositional solvers, such as sato, instead of answer set solvers, such as smodels. The need to extend Fages' theorem to programs with nested expressions is related to the use of choice rules in the input language of smodels.

PS

In Proceedings of International Conference on Logic Programming (ICLP), pp. 242-254 2001.

@InProceedings{erd01, title={Fages' Theorem for Programs with Nested Expressions}, author={Esra Erdem and Vladimir Lifschitz}, booktitle={Proceedings of International Conference on Logic Programming (ICLP)}, pages={242-254}, url="http://www.cs.utexas.edu/users/ai-lab?erd01", year={2001} }