Declarative and computational properties of logic programs with aggregates

Rather, it is based on a syntactic transformation, which turns a logic program into a formula of secondorder logic that is similar to the formula familiar from the definition of circumscription. In this paper we propose a new definition of that concept, which covers many constructs used in answer set programming includ Abstract - Cited by 71 37 self - Add to MetaCart The definition of a stable model has provided a declarative semantics for Prolog programs with negation as failure and has led to the development of answer set programming.

Strong equivalence is convenient for the study of equivalent transformations of logic programs: one can prove that a local change is correct without c Strong equivalence is convenient for the study of equivalent transformations of logic programs: one can prove that a local change is correct without considering the whole program.

This note considers a simpler, more direct characterization of strong equivalence for such programs, and shows that it can also be applied without modication to the weight constraint programs of Niemel? Thus, this characterization of strong equivalence is convenient for the study of equivalent transformations of logic programs written in the input languages of answer set programming systems dlv and smodels.

The note concludes with a brief discussion of results that can be used to automate reasoning about strong equivalence, including a novel encoding that reduces the problem of deciding the strong equivalence of a pair of weight constraint programs to that of deciding the inconsistency of a weight constraint program. What Is Answer Set Programming?

Answer set programming ASP is a form of declarative programming oriented towards difficult search problems. As an outgrowth of research on the use of nonmonotonic reasoning in knowledge representation, it is particularly useful in knowledge-intensive applications. ASP programs consist of rules tha Abstract - Cited by 67 9 self - Add to MetaCart Answer set programming ASP is a form of declarative programming oriented towards difficult search problems.

ASP programs consist of rules that look like Prolog rules, but the computational mechanisms used in ASP are different: they are based on the ideas that have led to the creation of fast satisfiability solvers for propositional logic. Another advantage of the ultimate approximation is that in cases where TP is monotone the ultimate well-founded model will be 2-valued and will coincide with the least fixpoint of TP.

This is not the case for the standard well-founded semantics. For example in the sta In this paper, we review recent work aimed at the application of declarative logic programming to knowledge representation in artificial intelligence.

We consider exten- sions of the language of definite logic programs by classical strong negation, disjunc- tion, and some modal operators and sh Abstract - Cited by 20 self - Add to MetaCart In this paper, we review recent work aimed at the application of declarative logic programming to knowledge representation in artificial intelligence.

We consider exten- sions of the language of definite logic programs by classical strong negation, disjunc- tion, and some modal operators and show how each of the added features extends the representational power of the language. The area of deductive databases has matured in recent years, and it now seems appropriate to re ect upon what has been achieved and what the future holds.

In this paper, we provide an overview of the area and briefly describe a number of projects that have led to implemented systems. Abstract - Cited by 7 self - Add to MetaCart The area of deductive databases has matured in recent years, and it now seems appropriate to re ect upon what has been achieved and what the future holds.

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming ASP. They strengthen the modeling power of ASP, in terms of concise problem representations. While many important problems can be encoded using nonrecursive aggregates, som While many important problems can be encoded using nonrecursive aggregates, some relevant examples lend themselves for the use of recursive aggregates.

Previous semantic definitions typically agree in the nonrecursive case, but the picture is less clear for 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 disjunctive programs with arbitrary aggregates including monotone, antimonotone, and nonmonotone aggregates. This semantics is a fully declarative, genuine generalization of the answer set semantics for disjunctive logic programming DLP. It is defined by a natural variant of the Gelfond-Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. We prove that our semantics guarantees the minimality and therefore the incomparability of answer sets, and demonstrate that it coincides with the standard answer set semantics on aggregate-free programs.

Finally we analyze the computational complexity of this language, paying particular attention to the impact of syntactical restrictions on programs. Citation Context We propose a semantics for aggregates in deductive databases based on a notion of minimality. Unlike some previous approaches, we form a minimal model of a program component including aggregate operators, rather than insisting that the aggregate apply to atoms that have been fully determined, or tha Abstract - Cited by 66 3 self - Add to MetaCart We propose a semantics for aggregates in deductive databases based on a notion of minimality.

Unlike some previous approaches, we form a minimal model of a program component including aggregate operators, rather than insisting that the aggregate apply to atoms that have been fully determined, or that aggregate functions are rewritten in terms of negation.

In order to guarantee the existence of such a minimal model we need to insist that the domains over which we are aggregating are complete lattices, and that the program is in a sense monotonic. Our approach generalizes previous approaches based on the well-founded semantics and various forms of stratification.

We are also able to handle a large variety of monotonic or pseudo-monotonic aggregate functions. Recently, a number of researchers have considered adding aggregation to the rule language. If the aggregation is applied in a Another advantage of the ultimate approximation is that in cases where TP is monotone the ultimate well-founded model will be 2-valued and will coincide with the least fixpoint of TP. This is not the case for the standard well-founded semantics.

In [Ferraris, ] it was shown that the semantics of 6 In [Ferraris, ] it was independently shown that deciding Smodels programs with positive weight constraints is equal answer set existence for a program with weight constraints possibly to answer sets as defined in [Faber et al. Gelfond and V. Indeed, we can show that the AtMost pruning operator Databases.

NGC, —, Representing Knowledge in A- operator defined in the proof sketch for Theorem In Computational Logic. Kemp and P. MIT Press, Koch, N.

Leone, and G. En- gates. The declarative and fixpoint characterizations of an- hancing Disjunctive Logic Programming Systems by SAT swer sets, provided in Sections 4 and 5, allow for a better Checkers. Artificial Intelligence, 15 1—2 —, A Model-Theoretic Counterpart of Loop and provide a handle on effective methods for computing an- Formulas. Leone, P. Rullo, and F.

Later in the computation, it can Disjunctive Stable Models: Unfounded Sets, Fixpoint Se- be used as a pruning operator and for answer set checking as mantics and Computation. Information and Computation, described in [Koch et al. Osorio and B. NGC, 17 3 — the computation. The well-founded semantics of LP A m,a is , Pelov and LPA m,a , while nonmonotone aggregates bring about a com- M. Semantics of disjunctive programs plexity gap, and cannot be easily accommodated in NP sys- with monotone aggregates - an operator-based approach.

In NMR , pp. A main concern for future work is therefore the exploita- [Pelov et al. Pelov, M. Denecker, and tion of our results for the implementation of recursive aggre- M. Partial stable models for logic pro- gates in ASP systems. Semantics of Logic Programs with References Aggregates. Knowledge Representation, Reason- [Pfeifer, ] G. CUP, Calimeri, W. Faber, N. Leone, and junctive Programs. Pruning Operators for Answer Set Program- Ross and Y. Faber, G.

Ielpa, Aggregation in Deductive Databases. JCSS, 54 1 —97, N. Aggregate Functions in DLV. Online at [Schlipf, ] J. Programming Semantics. JCSS, 51 1 —86, Denecker, N. Pelov, and [Simons et al. Simons, I. Model Semantics for Logic Programs with Aggregates. In Artificial Intelligence, —, ICLP, pp.

A lattice-theoretical fixpoint theo- [Dix and Osorio, ] J. Dix and M. On Well- rem and its applications. Pacific J. Math, —, Behaved Semantics Suitable for Aggregation. Van Gelder, K. Ross, and J. Port Jefferson, N.