Optimizing the computation of stable models using merged rules

Recently, logic programs under the stable model semantics, have emerged as a new paradigm for declarative programming. In this new approach, a logic program is used to represent the knowledge of the domain, and various tasks are reduced to computing the stable models of this program. This paradigm has been successfully used in a wide range of applications including planning, diagnostics, graph problems, etc. The basic algorithm for computing stable models is implemented by several efficient systems. The most efficient implementation to date is called Smodels. Even though Smodels was demonstrated to be capable of solving several large industrial problems, there are some simple logic programs for which Smodels' performance is unexpectedly slow. This problem is not related to the implementation. Rather, it is the result of the one rule at a time inference used by the basic algorithm. The goal of this work is to improve the efficiency of the basic algorithm extending the set of inference rules with a new rule called the Extended Evaluation Rule (EER). EER efficiently retrieves information spread across several rules of a program. An algorithm, newsmodels, was developed incorporating the EER. A system Surya, based on the newsmodels algorithm was implemented. It was found that the EER considerably improves the efficiency of the system.