Satisfiability Modulo Transcendental Functions via Incremental Linearization

Alessandro Cimatti, Alberto Griggio, Ahmed Irfan, Marco Roveri, Roberto Sebastiani

TL;DR

This paper introduces a novel abstraction-refinement approach to solve Satisfiability Modulo Theories (SMT) problems that include transcendental functions like sine and exponentials. By combining piecewise-linear approximations with a clever logical check, the authors' method can definitively prove the existence of solutions—even when those solutions are irrational numbers—outperforming existing interval-propagation and theorem-proving tools on a wide range of benchmarks.

What Problem Does This Paper Address?

In formal verification and mathematics, systems are often modeled using non-linear arithmetic and transcendental functions (e.g., $e^x$, $\log(x)$, $\sin(x)$). Examples include cyber-physical systems, hybrid automata, and complex control software.

However, checking the satisfiability of formulas containing these functions—known as SMT(NTA)—is notoriously difficult. First, the problem is fundamentally undecidable. Second, transcendental functions typically yield irrational outputs for rational inputs. Because computers rely on rational/floating-point representations, finding an exact satisfying assignment (a "model") is practically impossible.

Existing tools usually rely on interval propagation (which only guarantees "delta-satisfiability"—meaning a solution exists near the bounds, but maybe not exactly) or theorem proving (which is great at proving a formula is unsatisfiable/valid, but cannot easily prove a formula is satisfiable or generate a model). This paper bridges that gap.

Methods

The authors tackle the problem using an abstraction-refinement loop built on top of the MathSAT SMT solver:

  1. Initial Abstraction: The solver replaces all transcendental functions with "uninterpreted functions" (UF) in a simpler linear real arithmetic (LRA) space.
  2. Piecewise-Linear Refinement: If the solver finds a candidate solution that is mathematically spurious (e.g., it guesses $e^0 = 5$), the algorithm refines the search space. It uses Taylor series to compute safe, rational upper and lower bounds around the point of interest. It then adds linear constraints—specifically tangent and secant lines—to box in the true function and rule out the bad guess.
  3. Handling Periodicity: For trigonometric functions like sine, computing exact concavity is impossible because $\pi$ is irrational. The authors solve this by mapping all inputs to a "base period" ($-\pi$ to $\pi$) using linear shift lemmas, allowing them to safely apply secant/tangent refinements.
  4. Proving SAT without Exact Models: To prove a formula is Satisfiable (SAT) without explicitly finding an irrational number, they introduce a novel logical check. They ask the solver: Is the formula satisfiable under ALL possible interpretations of the uninterpreted function that fall within our mathematically guaranteed rational bounds? If yes, a true solution is mathematically guaranteed to exist.

Datasets

The authors evaluated their tool against three classes of benchmarks (2,512 instances total):

  • Bounded Model Checking (BMC): 887 instances derived from unrolling transition systems of hybrid automata (sourced from tools like iSAT3, HyComp, nuXmv, and Hyst).
  • Mathematical: 681 quantifier-free instances translated from the MetiTarski theorem prover distribution.
  • dReal: 944 instances from the dReal solver distribution containing various transcendental functions.

Key Insights and Ideas

  • Slopes beat boxes: Traditional interval propagation approximates functions using piecewise-constant boxes. By using secant and tangent lines, this approach captures the slope of the function, resulting in much tighter approximations and faster pruning of the search space.
  • You don't need the exact number to prove it exists: The method for proving SAT is a major conceptual leap. By reducing the existence of an irrational solution to a purely universal quantifier-free check in LRA, the solver bypasses the limits of machine precision.
  • Lazy precision saves memory: Taylor series can generate fractions with massive numerators and denominators, which choke SMT solvers. The authors optimize this by using continued fractions to approximate these numbers, only increasing precision when absolutely necessary.

Key Results

  • Overall Performance: The proposed MathSAT implementation solved the highest number of benchmarks overall (906 out of 2,512), beating the next best tool (dReal) by 127 instances.
  • Definitive SAT Proofs: The novel SAT-checking technique successfully proved 72 BMC benchmarks to be strictly SAT. Competing tools like dReal and iSAT3 could only return "MaybeSAT" (delta-satisfiable) for these instances.
  • BMC Dominance: On scaled-down BMC benchmarks, MathSAT vastly outperformed competitors, solving 84 SAT and 556 UNSAT instances, compared to iSAT3 (35 SAT / 470 UNSAT) and dReal (0 SAT / 403 UNSAT).
  • Complementary Strengths: While MathSAT dominated BMC, MetiTarski remained the best at its own mathematical benchmarks, and dReal excelled on its native benchmarks. A "virtual best system" combining all tools would solve 1,353 benchmarks, showing that linearization and interval propagation are highly complementary.

Limitations and Future Work

  • Native Function Support: The current prototype only natively supports $e^x$ and $\sin(x)$. Other functions (like $\log$, $\cos$, $\tan$) are handled via rewriting (e.g., expressing $\cos$ in terms of $\sin$). The authors note this preprocessing hurts performance, as seen in the dReal benchmarks.
  • Future Directions: The authors plan to implement native support for more transcendental functions. They also aim to apply this solver to infinite-state transition systems, temporal planning, and to create a hybrid framework that actively combines their linearization technique with interval propagation.

Summary updated

Abstract

In this paper we present an abstraction-refinement approach to Satisfiability Modulo the theory of transcendental functions, such as exponentiation and trigonometric functions. The transcendental functions are represented as uninterpreted in the abstract space, which is described in terms of the combined theory of linear arithmetic on the rationals with uninterpreted functions, and are incrementally axiomatized by means of upper- and lower-bounding piecewise-linear functions. Suitable numerical techniques are used to ensure that the abstractions of the transcendental functions are sound even in presence of irrationals. Our experimental evaluation on benchmarks from verification and mathematics demonstrates the potential of our approach, showing that it compares favorably with delta-satisfiability/interval propagation and methods based on theorem proving.
BibTeX
@inproceedings{cimatti2017satisfiability,
  author = {Alessandro Cimatti and Alberto Griggio and Ahmed Irfan and Marco Roveri and Roberto Sebastiani},
  title = {{Satisfiability Modulo Transcendental Functions via Incremental Linearization}},
  booktitle = {CADE},
  year = {2017},
  url = {https://openreview.net/forum?id=kU2paNvigBy},
}

Loading related content...

Figure