Shared aggregate sets in answer set programming. Issue 3 (10th August 2018)

• Record Type: Journal Article
• Authors: ALVIANO, MARIO; DODARO, CARMINE; MARATEA, MARCO
• Editors: Dal Palu, Alessandro; Tarau, Paul
• Is Part Of: Theory and practice of logic programming. Volume 18:Issue 3/4(2018)
• Page Start: 301
• Page End: 318
• Publication Date: 2018-08-10
• Subjects: answer set programming, -- aggregations in logic programming, -- efficient computation; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068418000133
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: Aggregates are among the most frequently used linguistic extensions of answer set programming. The result of an aggregation may introduce new constants during the instantiation of the input program, a feature known as value invention. When the aggregation involves literals whose truth value is undefined at instantiation time, modern grounders introduce several instances of the aggregate, one for each possible interpretation of the undefined literals. This paper introduces new data structures and techniques to handle such cases, and more in general aggregations on the same aggregate set identified in the ground program in input. The proposed solution reduces the memory footprint of the solver without sacrificing efficiency. On the contrary, the performance of the solver may improve thanks to the addition of some simple entailed clauses which are not easily discovered otherwise, and since redundant computation is avoided during propagation. Empirical evidence of the potential impact of the proposed solution is given.