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.
Introduction
In formal verification and mathematics, systems are often modeled using non-linear arithmetic and transcendental functions such as $e^x$, $\log(x)$, and $\sin(x)$. These functions are critical for representing cyber-physical systems, hybrid automata, and complex control software. However, checking the satisfiability of formulas containing these functions—a problem known as SMT(NTA)—is notoriously difficult.
The problem is fundamentally undecidable, and transcendental functions typically yield irrational outputs for rational inputs. Because computers rely on rational or floating-point representations, finding an exact satisfying assignment (a "model") is practically impossible. Existing tools often rely on interval propagation, which only guarantees "delta-satisfiability" (a solution exists near the bounds), or theorem proving, which struggles to generate models for satisfiable formulas. This paper introduces a method to bridge this gap.
The Abstraction-Refinement Framework
The authors tackle the problem using an abstraction-refinement loop built on top of the MathSAT SMT solver. The core logic of this approach is captured in the SMT-NTA-check-abstract algorithm.
The process begins with an Initial Abstraction, where the solver replaces all transcendental functions with "uninterpreted functions" (UF) in a simpler linear real arithmetic (LRA) space. The solver then enters a loop where it checks for satisfiability. If a candidate solution is found to be mathematically spurious (e.g., the solver assumes $e^0 = 5$), the algorithm refines the search space by adding linear constraints that "box in" the true function.
Incremental Linearization
To refine the abstraction, the algorithm uses Taylor series to compute safe, rational upper and lower bounds around a point of interest. It then adds linear constraints—specifically tangent and secant lines—to rule out invalid guesses.
By using secant and tangent lines rather than traditional piecewise-constant boxes, this approach captures the slope of the function. This results in much tighter approximations and faster pruning of the search space. For trigonometric functions like sine, where computing exact concavity is difficult due to the irrationality of $\pi$, the authors map inputs to a "base period" ($-\pi$ to $\pi$) using linear shift lemmas, allowing for safe refinement.
One of the major conceptual leaps in this work is the ability to prove a formula is Satisfiable (SAT) without explicitly finding an irrational number. The authors introduce a logical check that asks: Is the formula satisfiable under ALL possible interpretations of the uninterpreted function that fall within the guaranteed rational bounds? If the answer is yes, a true solution is mathematically guaranteed to exist, bypassing the limits of machine precision.
Experimental Evaluation
The authors evaluated their tool, implemented in MathSAT, against 2,512 instances across three benchmark classes: Bounded Model Checking (BMC), Mathematical (MetiTarski), and dReal distributions.
- Overall Performance: MathSAT solved 906 out of 2,512 benchmarks, outperforming 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, whereas competing tools like dReal and iSAT3 could only return "MaybeSAT" (delta-satisfiable).
- BMC Dominance: On BMC benchmarks, MathSAT solved 84 SAT and 556 UNSAT instances, significantly outperforming iSAT3 (35 SAT / 470 UNSAT).
Conclusion and Future Work
While the current prototype demonstrates significant potential, it currently relies on rewriting for functions like $\log$, $\cos$, and $\tan$, which can impact performance. Future work will focus on implementing native support for a broader range of transcendental functions and applying the solver to infinite-state transition systems and temporal planning. The results suggest that linearization and interval propagation are highly complementary, pointing toward a future hybrid framework that combines both techniques.
Summary updated