Logic Programming with Cardinality Constraints

Reference:

Tommi Syrjänen. Logic programming with cardinality constraints. Research Report A86, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, December 2003.

Abstract:

In this work we examine cardinality constraint logic programs. We give a formal definition of the stable model semantics for general cardinality constraint programs and define a syntactic subclass of them, omega-restricted programs, that stays decidable even when function symbols are used. We show that the computational complexity of omega-restricted programs is 2-NEXP-complete in the general case and NEXP-complete if function symbols are not used. We give a general framework for extending the semantics and give four extensions to the basic semantics, including classical negation and partial stable model semantics. We show how the extensions can be translated back to normal omega-restricted programs and give a similar translation for logic programs with ordered disjunction. We present some implementation details of omega-restricted programs and give several examples of their use.

Keywords:

Logic programming, cardinality constraint, instantiation, stable model semantics, smodels

Suggested BibTeX entry:

@techreport{HUT-TCS-A86,
    address = {Espoo, Finland},
    author = {Tommi Syrj{\"a}nen},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {December},
    number = {A86},
    pages = {118},
    title = {Logic Programming with Cardinality Constraints},
    type = {Research Report},
    year = {2003},
}