2015/07/01 by Mario Alviano, MARIO ALVIANO, Wolfgang Faber +3
Computer Science · #AI-based Problem Solving and Planning #Answer set programming #Function (biology) #Logic, Reasoning, and Knowledge #Modular design #Monotone polygon #Monotonic function #Multi-Agent Systems and Negotiation #Rewriting #Set (abstract data type) #Translation (biology) #cs.AI
paper · pdf · doi:10.1017/s1471068415000228
published as Theory and Practice of Logic Programming 15 (2015) 559-573
openalex publication_date 2015/07/01 · arxiv created 2015/07/14 · openalex created_date 2016/06/24 · arxiv updated 2020/02/19 · openalex updated_date 2026/08/05
Abstract Aggregation functions are widely used in answer set programming for representing and reasoning on knowledge involving sets of objects collectively. Current implementations simplify the structure of programs in order to optimize the overall performance. In particular, aggregates are rewritten into simpler forms known as monotone aggregates. Since the evaluation of normal programs with monotone aggregates is in general on a lower complexity level than the evaluation of normal programs with arbitrary aggregates, any faithful translation function must introduce disjunction in rule heads in some cases. However, no function of this kind is known. The paper closes this gap by introducing a polynomial, faithful, and modular translation for rewriting common aggregation functions into the simpler form accepted by current solvers. A prototype system allows for experimenting with arbitrary recursive aggregates, which are also supported in the recent version 4.5 of the grounder gringo , using the methods presented in this paper.