A Decision Procedure for (Co)datatypes in SMT Solvers

Andrew Reynolds, Jasmin Christian BlanchetteIJCAI 2016

Introduction

This paper introduces a unified decision procedure for reasoning about both datatypes (finite structures like lists) and codatatypes (potentially infinite structures like streams) within SMT solvers. By integrating this procedure into the CVC4 solver, the authors provide a powerful tool for automated theorem proving and software verification, particularly for systems involving infinite processes.

Standard algebraic datatypes are "well-founded," meaning they eventually bottom out. However, many computer science concepts—like infinite streams or process logs—are better represented as codatatypes, which are "non-well-founded" and can be infinite or cyclic. While SMT solvers excel at logic and arithmetic, they have historically struggled with codatatypes due to the need for specialized rules like "uniqueness" (bisimilarity).

Methodology

The authors propose a three-phase decision procedure integrated into the CVC4 SMT solver:

  1. Bidirectional Closure: Computes logical consequences of constraints, handling equality and constructor properties.
  2. Acyclicity and Uniqueness: Uses $\mu$-binder notation to represent cyclic values. For datatypes, an acyclicity rule rejects cyclic definitions. For codatatypes, a uniqueness rule identifies terms that expand to the same infinite $\mu$-term.
  3. Branching: Performs case analysis on constructors.

This approach is unified, allowing datatypes and codatatypes to be nested or combined.

Experimental Setup

The procedure was evaluated using benchmarks generated from the Isabelle proof assistant via the Sledgehammer tool. The dataset comprised goals from the Isabelle Distribution (1,179 goals), the Archive of Formal Proofs (3,014 goals), and Bird and Stern–Brocot trees (265 goals), representing real-world formal verification tasks.

Key Insights

  • $\mu$-terms: Using $\mu$-binders to name repeating subterms allows for finite reasoning about infinite structures.
  • Duality: The rule forbidding cycles in datatypes (Acyclicity) is the logical dual of the rule identifying identical cycles in codatatypes (Uniqueness).
  • Model Finding: The solver can construct concrete examples of (co)datatypes for satisfiable constraints, aiding in debugging.

Results and Discussion

The implementation in CVC4 showed significant improvements over existing tools.

Comparison of CVC4 and Z3 performance across different (co)datatype configurations.

As illustrated in the table above, the full decision procedure in CVC4 (Full (co)datatypes) achieved the highest number of solved goals. On problems with 16 lemmas ($n=16$), the new procedure increased the success rate by over 5% compared to the baseline. CVC4 outperformed Z3 on codatatype-heavy benchmarks, as Z3 lacked the specialized uniqueness and acyclicity rules. The procedure proved 27 goals that were previously impossible to solve.

Limitations and Future Work

The current procedure assumes all codatatypes are corecursive, a simplification of broader theory. Additionally, the added complexity caused timeouts in 17 cases where simpler methods previously succeeded. Future work will focus on better integration with finite model finding to exclude "spurious counterexamples."

Summary updated

BibTeX
@inproceedings{reynolds2016decision,
  author = {Andrew Reynolds and Jasmin Christian Blanchette},
  title = {{A Decision Procedure for (Co)datatypes in SMT Solvers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}

Loading related content...

Figure