Complexity and Compilation of GZ-Aggregates in Answer Set Programming
This work addresses the interpretation of logic programs with aggregates for researchers in computational logic, but it is incremental as it builds on a recent proposal.
The paper analyzes the complexity of coherence testing and cautious reasoning under Gelfond and Zhang's new stable model semantics for aggregates in answer set programming, and develops compilation techniques to implement the semantics on existing ASP solvers, resulting in a prototype system.
Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.