Logic Programs with Monotone Cardinality Atoms

Title: Logic Programs with Monotone Cardinality Atoms

Abstract: This research investigates logic programs, or mca-programs, that use monotone cardinality atoms (mc-atoms). These atoms represent constraints on the lower bounds of cardinalities of sets. The study develops a theory for mca-programs and demonstrates that the one-step provability operator generalizes to these programs, but with nondeterminism. The main results show that mca-programs generalize normal logic programming, logic programming with cardinality atoms, and disjunctive logic programming. The research also presents a natural representation of normal logic programs as mca-programs, preserving all semantics.

Research Question: How can monotone cardinality atoms be used to extend existing logic programming formalisms?

Methodology: The study develops a theory for mca-programs by closely following the development of normal logic programming and lifting its major concepts, techniques, and results to the setting of mca-programs. It introduces models, supported models, and stable models for mca-programs, using a nondeterministic one-step provability operator. The research also presents a way to generalize the Gelfond-Lifschitz reduct to mca-programs.

Results: The research shows that mca-programs generalize normal logic programming, logic programming with cardinality atoms, and disjunctive logic programming. It also demonstrates that the one-step provability operator generalizes to mca-programs, but with nondeterminism.

Implications: The use of monotone cardinality atoms in logic programming allows for the representation of cardinality constraints, which can be useful in various applications. The research also provides a unified framework for understanding and comparing different logic programming formalisms.

Link to Article: https://arxiv.org/abs/0310063v1 Authors: arXiv ID: 0310063v1