# Aggregate Semantics for Propositional Answer Set Programs

arXiv: https://arxiv.org/abs/2109.08662 · HTML: https://mlsanity.com/paper/2109.08662/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 87 references that are in the map.
- First posted on arXiv 17 Sep 2021.

## Builds on (most cited first, 11 of 11)

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [ASP-Core-2 Input Language Format](https://mlsanity.com/paper/1911.04326/) (2019)
- [Clingo goes Linear Constraints over Reals and Integers](https://mlsanity.com/paper/1707.04053/) (2017)
- [Advancing Lazy-Grounding ASP Solving Techniques -- Restarts, Phase Saving, Heuristics, and More](https://mlsanity.com/paper/2008.03526/) (2020)
- [Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory](https://mlsanity.com/paper/2104.14789/) (2021)
- [Efficiently Coupling the I-DLV Grounder with ASP Solvers](https://mlsanity.com/paper/1810.00041/) (2018)
- [Grounding Recursive Aggregates: Preliminary Report](https://mlsanity.com/paper/1603.03884/) (2016)
- [On Relation between Constraint Answer Set Programming and Satisfiability Modulo Theories](https://mlsanity.com/paper/1702.07461/) (2017)
- [Fixpoint Semantics and Optimization of Recursive Datalog Programs with Aggregates](https://mlsanity.com/paper/1707.05681/) (2017)
- [Relating Two Dialects of Answer Set Programming](https://mlsanity.com/paper/1907.12139/) (2019)
- [Shared aggregate sets in answer set programming](https://mlsanity.com/paper/1804.08488/) (2018)

## Built on by (most cited first, 5 of 5)

- [Non-deterministic approximation operators: ultimate operators, semi-equilibrium semantics and aggregates (full version)](https://mlsanity.com/paper/2305.10846/) (2023)
- [On Nested Justification Systems (full version)](https://mlsanity.com/paper/2205.04541/) (2022)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Generalizing Level Ranking Constraints for Monotone and Convex Aggregates](https://mlsanity.com/paper/2308.15888/) (2023)
- [Operator-based semantics for choice programs: is choosing losing? (full version)](https://mlsanity.com/paper/2407.21556/) (2024)

## Abstract (arXiv)

Answer Set Programming (ASP) emerged in the late 1990ies as a paradigm for Knowledge Representation and Reasoning. The attractiveness of ASP builds on an expressive high-level modeling language along with the availability of powerful off-the-shelf solving systems. While the utility of incorporating aggregate expressions in the modeling language has been realized almost simultaneously with the inception of the first ASP solving systems, a general semantics of aggregates and its efficient implementation have been long-standing challenges. Aggregates have been proposed and widely used in database systems, and also in the deductive database language Datalog, which is one of the main precursors of ASP. The use of aggregates was, however, still restricted in Datalog (by either disallowing recursion or only allowing monotone aggregates), while several ways to integrate unrestricted aggregates evolved in the context of ASP. In this survey, we pick up at this point of development by presenting and comparing the main aggregate semantics that have been proposed for propositional ASP programs. We highlight crucial properties such as computational complexity and expressive power, and outline the capabilities and limitations of different approaches by illustrative examples.