Weight Constraints as Nested Expressions

Title: Weight Constraints as Nested Expressions

Research Question: How can weight constraints be related to nested expressions in the context of logic programming?

Methodology: The researchers compared two extensions of the answer set semantics: one using nested expressions and the other using weight constraints. They proposed a simple, modular translation from weight constraints to nested expressions that preserves the program's answer sets.

Results: They showed that there is a close relationship between these two forms of the answer set semantics. They defined a translation that turns any program with weight constraints into a program with nested expressions having the same answer sets. Furthermore, they demonstrated that every rule of the translated program can be equivalently replaced with a set of nondisjunctive rules, leading to a nondisjunctive version of the basic translation. They also defined a nonnested translation that eliminates nested expressions in favor of additional atoms, resulting in a conservative extension of the original program.

Implications: The translations defined in this paper can be of interest for several reasons. They can help in understanding the relationship between weight constraints and nested expressions in the context of logic programming. The nonnested translation can be particularly useful as it provides a way to drop the new atoms from the answer sets, resulting in the original answer sets for the program without nested expressions.

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