SATSMT

SATSMT is a term used in automated reasoning to describe the approach of solving satisfiability problems by combining Boolean satisfiability (SAT) with decision procedures for background theories, i.e., satisfiability modulo theories. In this view, a formula is solved by a SAT solver deciding the propositional skeleton, while theory solvers check the compatibility of the assigned literals with the intended theory semantics and may generate lemmas to guide the search. This cooperative architecture is often referred to as DPLL(T), where T denotes the background theory.

Techniques vary: either the theory is encoded into a SAT problem through bit-blasting or finite-domain encodings, or the problem is solved in a modular fashion with a SAT core and specialized theory solvers for linear arithmetic, arrays, uninterpreted functions, bit-vectors, or other theories. The integration allows incremental solving and backtracking, and theory lemmas can be asserted as new clauses in the SAT solver. Many modern SMT solvers implement SATSMT principles.

SATSMT found widespread use in software and hardware verification, formal methods, and program analysis, enabling tasks such as assertion checking, invariant synthesis, test-case generation, and debugging symbolic constraints. Benchmarks and competitions in the SMT community emphasize both the strength of SAT-based methods and the importance of robust theory solvers, with common theories including linear real and integer arithmetic, arrays, uninterpreted functions, and bit-vectors.

See also: Satisfiability Modulo Theories (SMT), SAT solvers, DPLL(T), formal verification.