Inductive decision procedures

Inductive decision procedures automate the verification of recursive data structures and infinite-state systems by integrating induction directly into SMT solvers.

Standard SMT solvers often struggle with quantified formulas over recursive structures like integers, lists, and trees because ground decision procedures lack a native mechanism for inductive reasoning. Inductive decision procedures bridge this gap by implementing techniques like inductive strengthening and automatic subgoal discovery within the solver core (notably in CVC4 and its successor, cvc5). By utilizing well-founded relations to generate induction schemes on the fly, these procedures allow engineers to prove complex properties of functional programs and hardware designs without manual lemma instantiation. This shift from external proof assistants to integrated solver logic enables higher levels of automation for verifying memory safety in separation logic and correctness in algebraic data types.

https://cvc5.github.io/