Complexity and compilation of GZ-aggregates in answer set programming. Issue 4 (3rd September 2015)

• Record Type: Journal Article
• Authors: ALVIANO, MARIO; LEONE, NICOLA
• Editors: Eiter, Thomas; Toni, Francesca
• Is Part Of: Theory and practice of logic programming. Volume 15:Issue 4/5(2015)
• Page Start: 574
• Page End: 587
• Publication Date: 2015-09-03
• Subjects: answer set programming, -- aggregates, -- complexity, -- compilation; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S147106841500023X
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: 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.