Constraint Answer Set Programming versus Satisfiability Modulo Theories

Yuliya Lierler, Benjamin SusmanIJCAI 2016

Introduction

Automated reasoning has long been divided into two powerful but distinct paradigms: Answer Set Programming (ASP) and Satisfiability Modulo Theories (SMT). While ASP excels at representing complex knowledge and default reasoning, it often suffers from a "grounding bottleneck" when dealing with large or infinite numeric domains. Conversely, SMT is highly efficient at handling complex mathematical constraints by integrating boolean logic with specialized background theories.

Constraint Answer Set Programming (CASP) emerged as a hybrid approach to address ASP's limitations by delegating constraints to specialized solvers. However, the formal relationship between CASP and SMT remained obscured by disparate terminologies. This research bridges that gap, providing a precise mathematical dictionary to translate between these two fields and proving their deep theoretical connection.

Theoretical Framework: Uniform Theories and Input Answer Sets

To unify these frameworks, the authors introduce several key concepts:

  • Input Answer Sets: A generalization of traditional answer sets that accounts for atoms from different vocabularies, specifically distinguishing between regular logic and irregular constraints.
  • Constraint Formulas: A middle-ground representation that maintains the structure of logic while behaving like a constraint satisfaction problem.
  • Uniform Theories: This is the core theoretical contribution. The authors define a class of SMT theories where the domain (e.g., Integers) and the interpretation of functions (e.g., arithmetic operators) are fixed across all models. Most common SMT theories, such as linear arithmetic and difference logic, fall into this category.

By identifying these uniform theories, the paper proves that the distinction between a "constraint" in CASP and a "theory atom" in SMT is primarily a matter of notation rather than fundamental logic.

Bridging the Gap: Tightness and Equivalence

A significant insight of this work is the "tightness" bridge. For "tight" logic programs—those lacking certain circular dependencies—answer sets coincide with the models of the program's completion. This formal mapping (detailed in Theorems 4 and 5) demonstrates that under uniform theories, a CASP program is essentially equivalent to an SMT formula or an "ASP Modulo Theory" (ASPT) program. This equivalence suggests that highly optimized SMT technology can be directly leveraged to compute answer sets for a broad class of CASP programs.

Solver Taxonomy and Unified Outlook

The authors apply their unified framework to categorize existing solvers, clarifying which logic-theory combinations they support. This taxonomy provides a clear landscape of the current state of the art.

Table 1: Categorization of solvers within the unified ASPT framework.

As shown in the table above, solvers like MINGO operate by translating CASP into Mixed Integer Programming, while others like DINGO utilize SMT solvers like Z3. This categorization helps researchers identify the most appropriate tool for specific constraint-logic problems.

Conclusion and Future Directions

This research successfully proves that CASP languages are a special case of SMT languages when defined over uniform theories. This theoretical unification opens the door for significant cross-pollination between the two fields, allowing ASP researchers to benefit from SMT performance optimizations.

Future work aims to extend these results beyond "tight" programs to handle more complex recursion. Additionally, the authors suggest generalizing this framework to non-numeric theories and applying similar unification techniques to other formalisms, such as HEX-programs, which integrate external information sources into logic programs.

Summary updated

BibTeX
@inproceedings{lierler2016constraint,
  author = {Yuliya Lierler and Benjamin Susman},
  title = {{Constraint Answer Set Programming versus Satisfiability Modulo Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure