Abstract
Answer Set Programming (ASP) is a powerful paradigm for combinatorial problem-solving, yet it often requires ad-hoc extensions to handle complex algebraic calculations like aggregates or data provenance. This paper introduces ASP($\mathcal{AC}$), a framework that unifies logic programming with algebraic constraints by integrating semiring-based "Weighted Logic" into the Here-and-There (HT) logical foundation of ASP. The resulting system allows for native expression of numeric and structural dependencies while maintaining the non-monotonic reasoning capabilities of stable model semantics.
Introduction
While ASP is a go-to for hard combinatorial problems, its evolution has been marked by various "patches" to support aggregates (e.g., sum, count), weight constraints, and integrations with Constraint Programming (CP). These extensions often treat constraints as "black boxes" rather than first-class logical citizens. ASP($\mathcal{AC}$) addresses this by providing a principled, logic-based foundation capable of handling diverse algebraic structures—ranging from simple integers to complex provenance structures—in a unified manner.
The ASP($\mathcal{AC}$) Framework
The framework is built upon First-Order Weighted Here-and-There (FO-WHT) Logic. This combines traditional HT logic with Weighted Logic, where the "weight" or value of a formula is determined by the truth of its atoms.
Key Technical Components
- Semiring Generality: The framework is parameterized by a semiring (a set with addition-like and multiplication-like operations). By swapping the semiring, the same syntax can model classical logic (Boolean semiring), cost optimization (Tropical semiring), or arithmetic (Natural numbers).
- Algebraic Constraints: Constraints take the form $k \sim \alpha$, where $\alpha$ is a weighted formula and $k$ is a value from the semiring.
- Safety and Domain Independence: To ensure practical solvability, the authors define syntactic safety rules. These ensure that the program's results remain consistent regardless of irrelevant elements added to the underlying domain.
Key Results and Complexity
A primary contribution of this work is the demonstration that ASP($\mathcal{AC}$) is a true generalization of existing ASP dialects. It provides a single, elegant syntax for constructs that were previously handled by disparate extensions.
In terms of computational complexity, the authors prove that for ground (variable-free) programs, adding these algebraic constraints does not increase the complexity class of ASP. Finding an answer set remains $\Sigma^p_2$-complete, provided that the semiring operations themselves are efficiently computable. This parity suggests that the framework offers increased expressivity without a fundamental performance penalty in the finite case.
Applications: Native Provenance
One of the most compelling applications of ASP($\mathcal{AC}$) is its ability to handle provenance semantics. By choosing an appropriate semiring, the framework can natively encode "why" and "how" a specific fact was derived. This allows developers to track the history of a proof or the source of data directly within the logic rules, a task that typically requires significant external instrumentation in standard ASP.
Limitations and Future Work
Despite its theoretical robustness, ASP($\mathcal{AC}$) faces challenges in the first-order case, which is generally undecidable. Furthermore, the current semantics do not fully address "infinite support"—scenarios where a value is derived from an infinite set of true atoms. Future research will focus on developing efficient solvers for the "safe" fragments of the logic and extending provenance support to include negated formulas.
Summary updated