Answer set programming provides a new paradigm for declarative logic programming, based on the well-known stable models semantics. This paper presents a language of weight constraint rules for answer set programming, specifically, a rule language allowing weight constraints in place of literals in a rule.

A declarative semantics is developed as an extension of the stable model semantics of normal programs, with no substantial increase in computational complexity; in particular, deciding whether a set of weighted constraint rules has a stable model is NP-complete.

The topic of answer set programming has been studied for years at a theoretical level, but recently, due to the efficient implementation of solvers, answer set programming has become a useful tool for reasoning systems related to knowledge processing and problem solving. Such applications can be applied to different problem areas, such as scheduling, clausal theories, diagnosis, cryptography, and verification.

The main contribution of this paper is the identification of a normal form for the general language, the basic constraint rules, and the analysis of complexity of relevant computational problems. An implementation of the language, called smodels, is presented for this fragment of the language. The procedure for computing stable models is tested against satisfiability testers and against dlv, another system for computing stable models.