Stable model semantics of weight constraint rules

Ilkka Niemelä, Patrik Simons, Timo Soininen

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

    65 Citations (Scopus)

    Abstract

    A generalization of logic program rules is proposed where rules are built from weight constraints with type information for each predicate instead of simple literals. These kinds of constraints are useful for concisely representing different kinds of choices as well as cardinality, cost and resource constraints in combinatorial problems such as product configuration. A declarative semantics for the rules is presented which generalizes the stable model semantics of normal logic programs. It is shown that for ground rules the complexity of the relevant decision problems stays in NP. The first implementation of the language handles a decidable:subset where function symbols are not allowed. It is based on a new procedure for computing stable models for ground rules extending normal programs with choice and weight constructs and a compilation technique where a weight rule with variables is transformed to a set of such simpler ground rules.

    Original languageEnglish
    Title of host publicationLogic Programming and Nonmonotonic Reasoning
    Subtitle of host publication5th International Conference, LPNMR’ 99 El Paso, Texas, USA, December 2–4, 1999. Proceedings
    EditorsM. Gelfond, N. Leone, G. Pfeifer
    Place of PublicationBerlin
    Pages317-331
    Number of pages15
    ISBN (Electronic)978-3-540-46767-0
    DOIs
    Publication statusPublished - 1999
    MoE publication typeA4 Article in a conference publication
    EventInternational Conference on Logic Programming and Nonmonotonic Reasoning - El Paso, United States
    Duration: 2 Dec 19994 Dec 1999
    Conference number: 5

    Publication series

    NameLECTURE NOTES IN ARTIFICIAL INTELLIGENCE
    PublisherSPRINGER-VERLAG BERLIN
    Volume1730
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Conference on Logic Programming and Nonmonotonic Reasoning
    Abbreviated titleLPNMR
    CountryUnited States
    CityEl Paso
    Period02/12/199904/12/1999

    Keywords

    • linear inequalities
    • logic programs
    • stable model semantics

    Cite this