Semantics and Compilation of Answer Set Programming with Generalized
  Atoms
  Answer Set Programming (ASP) is logic programming under the stable model or
answer set semantics. During the last decade, this paradigm has seen several
extensions by generalizing the notion of atom used in these programs. Among
these, there are aggregate atoms, HEX atoms, generalized quantifiers, and
abstract constraints. In this paper we refer to these constructs collectively
as generalized atoms. The idea common to all of these constructs is that their
satisfaction depends on the truth values of a set of (non-generalized) atoms,
rather than the truth value of a single (non-generalized) atom. Motivated by
several examples, we argue that for some of the more intricate generalized
atoms, the previously suggested semantics provide unintuitive results and
provide an alternative semantics, which we call supportedly stable or SFLP
answer sets. We show that it is equivalent to the major previously proposed
semantics for programs with convex generalized atoms, and that it in general
admits more intended models than other semantics in the presence of non-convex
generalized atoms. We show that the complexity of supportedly stable models is
on the second level of the polynomial hierarchy, similar to previous proposals
and to stable models of disjunctive logic programs. Given these complexity
results, we provide a compilation method that compactly transforms programs
with generalized atoms in disjunctive normal form to programs without
generalized atoms. Variants are given for the new supportedly stable and the
existing FLP semantics, for which a similar compilation technique has not been
known so far.
