Aggregate Semantics for Propositional Answer Set Programs
  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.
