Abstract
In the field of Answer Set Programming (ASP), certain mathematical properties—specifically Constraint Monotonicity and Foundedness—have long been proposed as mandatory benchmarks for any valid semantics. This paper challenges that consensus by demonstrating that these properties can inadvertently exclude intuitive and logically sound solutions in complex reasoning tasks. Using the Generalized Strategic Companies (GSC) problem as a primary counter-example, the authors illustrate how rigid adherence to these properties fails to account for the nuances of epistemic specifications and subset-minimality, suggesting a need for more flexible criteria in evaluating ASP semantics.
Introduction
Answer Set Programming (ASP) has established itself as a powerful declarative paradigm for solving difficult combinatorial problems. As the field matures, researchers have sought to define the fundamental characteristics that constitute a "good" semantics—the underlying logic used to derive solutions. Recently, two properties have emerged as potential "litmus tests" for any proposed ASP semantics: Constraint Monotonicity and Foundedness.
Constraint Monotonicity dictates that the addition of a constraint to a program should only serve to eliminate existing solutions, never to generate new ones or alter the truth values of atoms in a way that contradicts the original logic. Foundedness requires that every atom in a solution be "justified" by the program's rules, effectively prohibiting circular reasoning where atoms are true simply because they support each other. While these properties appear to be common-sense requirements, this research argues that they are overly restrictive and can outlaw the very solutions required by real-world applications.
Methodology: The Counter-Example Approach
Rather than relying on abstract proofs, the authors employ a counter-example-driven methodology centered on the Generalized Strategic Companies (GSC) problem. GSC is a standard benchmark in ASP competitions designed to test high-level reasoning. It involves determining a minimal set of companies that must be kept "strategic" to ensure the production of specific goods, given various ownership and production constraints.
The authors represent GSC instances using disjunctive programs and epistemic specifications (which incorporate operators for "knowledge" and "possibility"). They then perform a comparative analysis between two primary semantics:
- GL-semantics: The classic approach which strictly enforces monotonicity and foundedness.
- DI-semantics (Determining Inference): A newer approach that prioritizes logical inference over rigid property adherence.
Key Insights: The Conflict with Minimality
The Minimalist Trap and Monotonicity
The core conflict regarding Constraint Monotonicity often arises from the requirement for subset-minimality. In the GSC problem, a set of companies is considered strategic if it is the smallest possible set capable of producing the required goods. The authors demonstrate that adding a constraint can sometimes invalidate a previously minimal set, making a different, previously "too large" set the new smallest valid option. Under GL-semantics, this shift is often disallowed because it violates monotonicity, even though the new solution is the only logically consistent outcome for the modified problem.
The Limits of Foundedness
Foundedness is intended to prevent "unfounded sets"—circular justifications. However, in the context of GSC, the choice of which company produces a good may be restricted by external rules. The authors show that an intuitive solution can technically contain an "unfounded set" by strict mathematical definition while remaining the only rational solution to the actual problem constraints. By enforcing foundedness, solvers may fail to find any valid answer set for problems that clearly possess a logical solution.
Epistemic Impact
The critique extends to Epistemic Specifications, which use operators like K (known) and M (may be true). The research shows that "subjective constraint monotonicity" can exclude valid "world views" (sets of possible solutions). If a semantics is forced to be monotonic, it may fail to represent the full range of knowledge states possible in complex epistemic scenarios.
Results and Comparative Analysis
Through a series of five primary examples, the authors highlight the following:
- Monotonicity Failures: In GSC instances where a simple rule acts as a constraint, GL-semantics often fails to return a solution, whereas DI-semantics successfully identifies the expected, intuitive result.
- Foundedness Violations: The authors provide a GSC instance where the only rational solution is technically "unfounded," proving that foundedness is not always a desirable trait for finding practical solutions.
- Epistemic Logic: The failures observed in standard ASP are mirrored in epistemic specifications, where enforcing these properties breaks the ability to generate accurate world views.
Conclusion and Future Directions
The paper concludes that while Constraint Monotonicity and Foundedness are useful features for many classes of programs, they should not be treated as mandatory requirements for all ASP semantics. Their enforcement can lead to the rejection of valid, intuitive solutions in complex domains like the GSC problem.
This finding leaves the ASP community with a significant open question: If these "golden rules" are not universal, what properties should be used to judge the soundness of a semantics? Future work is needed to identify alternative criteria that ensure logical consistency without sacrificing the expressive power required for complex combinatorial and epistemic reasoning.
Summary updated