Logic programs, well-orderings, and forward chaining

We investigate the construction of stable models of general propositional l ogic programs. We show that a forward-chaining technique, supplemented by a properly chosen safeguard can be used to construct stable models of logic programs. Moreover, the proposed method has the advantage that if a program has no stable model, the result of the construction is a stable model of a subprogram. Further, in such a case the proposed method "isolates the inco nsistency" of the program, that is it points to the part of the program res ponsible for the inconsistency. The results of computations are called stab le submodels. We prove that every stable model of a program is a stable sub model. We investigate the complexity issues associated with stable submodel s. The number of steps required to construct a stable submodel is polynomia l in the sum of the lengths of the rules of the program. in the infinite ca se the outputs of the forward chaining procedure have much simpler complexi ty than those for general stable models. We show how to incorporate other t echniques for finding models (e.g. Fitting operator, Van Gerder-Ross-Schlip f operator) into our construction. (C) 1999 Elsevier Science B.V. All right s reserved.