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, omegarestricted programs, that stays decidable even when function symbols are used. We show that the computational complexity of omegarestricted programs is 2NEXPcomplete in the general case and NEXPcomplete 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 omegarestricted programs and give a similar translation for logic programs with ordered disjunction. We present some implementation details of omegarestricted programs and give several examples of their use.
Keywords:
Logic programming, cardinality constraint, instantiation, stable model semantics, smodels
Suggested BibTeX entry:
@techreport{HUTTCSA86,
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},
}
