Extended abstract of a paper published at IJCAI 20251 [2]-Constraint Logic Programming (CLP) is a logic programming formalism used to solve problems requiring the consideration of constraints, like resource allocation and automated planning and scheduling. It has previously been extended in various directions, for example to support fuzzy constraint satisfaction, uncertainty, or negation, with diferent notions of semiring being used as a unifying abstraction for these generalizations. None of these extensions have studied clauses with negation allowed in the body. We investigate an extension of CLP which unifies many of these extensions and allows negation in the body. We provide semantics for such programs, using the framework of approximation fixpoint theory (AFT), and give a detailed overview of the impacts of properties of the semirings on the resulting semantics. As such, we provide a unifying framework that captures existing approaches and allows extending them with a more expressive language.
Using classical answer set programming semantics to evaluate this program with the goal
schedule(HoursTask1, HoursTask2) returns false. Intuitively, this happens because no schedule
can complete the two tasks—totalling ten hours of work—in less than eight hours. Knowing that the two
tasks cannot both be completed in the time available, we may wish to optimize their partial completion
instead. One way to do this is to replace false and true with values in [
Our example demonstrated that CLP is limited to strict satisfaction or violation of constraints, and that we require an alteration of this framework to solve problems of constraint optimization. The same holds—for example—for problems involving fuzziness, uncertainty, or probability.
Bistarelli et al. [
While some of the above-mentioned works permit negation, most do not, and a general analysis
of negation in the semiring setting is so far absent from the literature. Herein lies the second major
contribution of this work; a semiring-agnostic form of negation—based on negation in Gödel logics [
Notably, and as is to be expected, the addition of negation leads to nonmonotonicity of the immediate consequence operator. To work around this problem we capture the new negation-permitting formalism in Approximation Fixpoint Theory (ADT) [14], endowing it with AFT’s various semantics like KripkeKleene, Well-founded, and Stable, which generalize the semantics of normal logic programs.
Concretely, the contributions of this work come in five parts:
1. A novel notion of model—considering all contributing clauses at once, and specific to the
semiringbased setting—is introduced and compared to the traditional notion of model which considers
each clause’s satisfaction separately.
2. The minimal model semantics based on these notions of model are then compared with the least
ifxpoint semantics based on an immediate consequence operator.
3. A generalized method for deriving orderings of semiring elements needed to define models and
least fixpoints—but also needed in the later application of approximation fixpoint theory—is
investigated and found to be a generalization of the method studied by Bistarelli et al. [
This work studies semiring-based semantics for constraint logic programming with negation,
generalizing the approaches of [
Acknowledgments This work was partially supported by the project LogicLM: Combining Logic Programs with Language Model with file number NGF.1609.241.010 of the research programme NGF AiNed XS Europa 2024-1, is (partly) financed by the Dutch Research Council (NWO).
The authors have not employed any Generative AI tools. [14] M. Denecker, V. Marek, M. Truszczynski, Approximations, Stable Operators, Well-Founded Fixpoints And Applications In Nonmonotonic Reasoning, Logic-based Artificial Intelligence (2001). doi:10.1007/978-1-4615-1567-8_6. [15] M. A. Khamis, H. Q. Ngo, R. Pichler, D. Suciu, Y. R. Wang, Convergence of Datalog over (Pre-)
Semirings., SIGMOD Rec. 52 (2023) 75–82. doi:10.1145/3604437.3604454. [16] J. Vennekens, D. Gilis, M. Denecker, Splitting an operator: Algebraic modularity results for logics with fixpoint semantics, CoRR cs.AI/0405002 (2004). [17] J. Heyninck, An Algebraic Notion of Conditional Independence, and Its Application to Knowledge
Representation (full version)., CoRR abs/2412.13712 (2024). doi:10.48550/ARXIV.2412.13712. [18] J. Heyninck, O. Arieli, B. Bogaerts, Non-deterministic approximation fixpoint theory and its application in disjunctive logic programming., Artif. Intell. 331 (2024) 104110. doi:10.1016/J. ARTINT.2024.104110.