ASP(𝓐𝒞): Answer Set Programming with Algebraic Constraints

Thomas Eiter, Rafael KieselTheory Pract. Log. Program 2020 · OpenReview

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.

Comparison of language constructs in ASP(AC) versus other ASP 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

Abstract

Weighted Logic is a powerful tool for the specification of calculations over semirings that depend on qualitative information. Using a novel combination of Weighted Logic and Here-and-There (HT) Logic, in which this dependence is based on intuitionistic grounds, we introduce Answer Set Programming with Algebraic Constraints (ASP($\mathcal A \mathcal C$)), where rules may contain constraints that compare semiring values to weighted formula evaluations. Such constraints provide streamlined access to a manifold of constructs available in ASP, like aggregates, choice constraints, and arithmetic operators. They extend some of them and provide a generic framework for defining programs with algebraic computation, which can be fruitfully used e.g. for provenance semantics of datalog programs. While undecidable in general, expressive fragments of ASP($\mathcal A \mathcal C$) can be exploited for effective problem solving in a rich framework.
BibTeX
@inproceedings{eiter2020asp,
  author = {Thomas Eiter and Rafael Kiesel},
  title = {{ASP(𝓐𝒞): Answer Set Programming with Algebraic Constraints}},
  booktitle = {Theory Pract. Log. Program},
  year = {2020},
  url = {https://openreview.net/forum?id=JAqlWqHuYj},
}

Loading related content...

Figure