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.
p04 and pdb06 studied a more general class of aggregates and developed a systematic theory of aggregates in logic programming based on the approximation theory @cite_0 . The resulting theory covers not only the stable models semantics but also the supported-model semantics and extensions of 3-valued Kripke-Kleene and well-founded semantics. The formalism introduced and studied by p04 and pdb06 allows for arbitrary aggregates (not only monotone ones) to appear in the bodies of rules. However, it does not allow for aggregates to appear in the heads of program clauses. Due to differences in the syntax and the scope of semantics studied there is no simple way to relate p04 and pdb06 formalism to programs with monotone (convex) constraints. We note though that programs with abstract monotone constraints with the heads of rules of the form @math can be viewed almost literally as programs in the formalism by p04 and pdb06 and that they have the same stable models according to the definitions we used in this paper and those by p04 and pdb06 .
@cite_0
1565496223
Aggregates are functions that take sets as arguments. Examples are the function that maps a set to the number of its elements or the function which maps a set to its minimal element. Aggregates are frequently used in relational databases and have many applications in combinatorial search problems and knowledge representation. Aggregates are of particular importance for several extensions of logic programming which are used for declarative programming like Answer Set Programming, Abductive Logic Programming, and the logic of inductive definitions (ID-Logic). Aggregate atoms not only allow a broader class of problems to be represented in a natural way but also allow a more compact representation of problems which often leads to faster solving times. Extensions of specific semantics of logic programs with, in many cases, specific aggregate relations have been proposed before. The main contributions of this thesis are: (i) we extend all major semantics of logic programs: the least model semantics of definite logic programs, the standard model semantics of stratified programs, the Clark completion semantics, the well-founded semantics, the stable models semantics, and the three-valued stable semantics; (ii) our framework admits arbitrary aggregate relations in the bodies of rules. We follow a denotational approach in which a semantics is defined as a (set of) fixpoint(s) of an operator associated with a program. The main tool of this work is Approximation Theory. This is an algebraic theory which defines different types of fixpoints of an approximating operator associated with a logic program. All major semantics of a logic program correspond to specific types of fixpoints of an approximati