We study properties of programs with monotone and convex constraints. We extend to these formalisms concepts and results from normal logic programming. They include the notions of strong and uniform equivalence with their characterizations, tight programs and Fages Lemma, program completion and loop formulas. Our results provide an abstract account of properties of some recent extensions of logic programming with aggregates, especially the formalism of lparse programs. They imply a method to compute stable models of lparse programs by means of off-the-shelf solvers of pseudo-boolean constraints, which is often much faster than the smodels system.
flp04 developed the theory of disjunctive logic programs with aggregates. Similarly as p04 and pdb06 , flp04 do not allow for aggregates to appear in the heads of program clauses. This is one of the differences between that approach and programs with monotone (convex) constraints we studied here. The other major difference is related to the postulate of the minimality of stable models (called answer sets in the context of the formalism considered by flp04 ). In keeping with the spirit of the original answer-set semantics @cite_24 , answer sets of disjunctive programs with aggregates, as defined by flp04 , are minimal models. Stable models of programs with abstract constraints do not have this property. However, for the class of programs with abstract monotone constraints with the heads of rules of the form @math the semantics of answer sets defined by flp04 coincides with the semantics of stable models by mt04 and mnt03,mnt06 .
@cite_24
2076698873
The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case. In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming - DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs. Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and nega