Efficient Implementation of the Stable Model Semantics for Normal Logic Programs

Reference:

Patrik Simons. Efficient implementation of the stable model semantics for normal logic programs. Research Report A35, Helsinki University of Technology, Digital Systems Laboratory, Espoo, Finland, September 1995.

Abstract:

The aim of this work is to develop an efficient implementation method of the stable model semantics of logic programs with negation using as a basis a lately proposed decision procedure for Reiter's default logic. The problem of finding a stable model of a logic program is NP-complete. An algorithm for computing the stable model semantics of propositional logic programs is presented. The time complexity of the algorithm is examined and found to be exponential in the size of the input in the worst case. The algorithm is shown to compute the unique stable model of a logic program with a total well-founded model in time roughly quadratic in the size of the program. The algorithm is compared with three other advanced algorithms for computing the stable models semantics. It is found to be outperforming the other algorithms mainly due to a better technique for pruning the search space. A method for implementing the algorithm efficiently is presented and a prototype implementation is developed. As examples of applications of stable model semantics, model-based diagnosis of logic circuits and the problem of finding Hamiltonian circuits and N-colorings in undirected graphs are encoded as propositional logic programs. These encodings are then used as test cases in a comparison between the prototype implementation of the algorithm presented in this work and the SLG system, a state-of-the-art implementation of the stable model semantics. The performance of the prototype implementation compares favorably to that of the SLG system.

Keywords:

stable model semantics, well-founded semantics, logic programming, nonmonotonic reasoning, automatic theorem proving

Suggested BibTeX entry:

@techreport{HUT-TCS-A35,
    address = {Espoo, Finland},
    author = {Patrik Simons},
    institution = {Helsinki University of Technology, Digital Systems Laboratory},
    month = {September},
    number = {A35},
    pages = {66},
    title = {Efficient Implementation of the Stable Model Semantics for Normal Logic Programs},
    type = {Research Report},
    year = {1995},
}