Smodels - an implementation of the stable model and well-founded semantics for normal logic programs

Ilkka Niemelä, Patrik Simons

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    241 Citations (Scopus)

    Abstract

    The Smodels system is a C++ implementation of the well-founded and stable model semantics for range-restricted function-free normal programs. The system includes two modules: (i) smodels which implements the two semantics for ground programs and (ii) parse which computes a grounded version of a range-restricted function-free normal program. The latter module does not produce the whole set of ground instances of the program but a subset that is sufficient in the sense that no stable models ate lost. The implementation of the stable model semantics for ground programs is based on bottom-up backtracking search where a powerful pruning method is employed. The pruning method exploits an approximation technique for stable models which is closely related to the well-founded semantics. One of the advantages of this novel technique is that it can be implemented to work in linear space. This makes it possible to apply the stable model semantics also in areas where resulting programs are highly non-stratified and can possess a large number of stable models. The implementation has been tested extensively and compared with a state of the art implementation of the stable model semantics, the SLG system. In tests involving ground programs it clearly outperforms SLG.

    Original languageEnglish
    Title of host publicationLOGIC PROGRAMMING AND NONMONOTONIC REASONING
    Subtitle of host publication4th International Conference, LPNMR '97 Dagstuhl Castle, Germany, July 28–31, 1997. Proceedings
    EditorsJ Dix, U Furbach, A Nerode
    Place of PublicationGermany
    Pages420-429
    Number of pages10
    ISBN (Electronic)978-3-540-69249-2
    DOIs
    Publication statusPublished - 1997
    MoE publication typeA4 Article in a conference publication
    EventInternational Conference on Logic Programming and Nonmonotonic Reasoning - Dagstuhl Castle, Wadern, Germany
    Duration: 28 Jul 199731 Jul 1997
    Conference number: 4

    Publication series

    NameLecture Notes in Artificial Intelligence
    PublisherSPRINGER-VERLAG BERLIN
    Volume1265
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Conference on Logic Programming and Nonmonotonic Reasoning
    Abbreviated titleLPNMR
    CountryGermany
    CityWadern
    Period28/07/199731/07/1997

    Keywords

    • normal logic programs
    • stable model semantics
    • well-founded semantics

    Cite this