Abstract: The Extended Theory of Trees and Algebraic (Co)datatypes

Fabian Zaiser, Luke Ong

Introduction

Satisfiability Modulo Theories (SMT) solvers are foundational to modern formal verification and programming language research. They are used to prove code correctness by reasoning about data structures. Two of the most common structures are algebraic datatypes (finite structures like lists or binary trees) and codatatypes (potentially infinite structures like streams). While the logic of these structures is deeply rooted in the mathematical theory of finite and infinite trees—a field studied since the 1980s—a gap has existed between foundational tree theories and the practical requirements of modern SMT solvers.

The Problem: Bridging the Gap

Previous foundational work on tree theories relied on restrictive assumptions that prevented their algorithms from being directly applicable to the algebraic (co)datatypes used in contemporary SMT solvers. Specifically, there was a need for a unified framework that could handle both finite and infinite structures within a single, decidable theory.

Methodology: Extending the Theory

To address this, the authors propose an extension to the first-order theory of finite and infinite trees. The core of their approach involves three key components:

  • The Finiteness Predicate: The authors introduce a new predicate that explicitly checks for the finiteness of trees. This is the "missing link" that allows the theory to distinguish between and reason about both standard datatypes (finite) and codatatypes (infinite) simultaneously.
  • Simplification Procedure: Building on prior research, they developed a decidable simplification procedure. Unlike standard algorithms that merely return a boolean satisfiability result, this procedure takes an arbitrary formula (including open formulas) and produces a simplified version. This output is designed to be human-readable, allowing researchers to identify all possible models that satisfy the original formula.
  • Formal Translation: The authors provide a detailed translation procedure that mathematically maps the relationship between the theory of trees and the theory of (co)datatypes, ensuring that the two domains are formally linked.

Key Insights: Expressiveness and Decidability

A significant finding of this work is that the theory of trees is inherently more expressive than the standard theories of (co)datatypes currently employed in SMT solvers. Often, in the field of automated reasoning, increasing the expressiveness of a logic risks making it undecidable—meaning an algorithm might never finish its computation.

However, the authors demonstrate that leveraging the theory of trees increases expressiveness without sacrificing decidability. This makes the extended theory a highly attractive candidate for the architecture of future SMT solvers, offering more power to verify complex software properties without losing the guarantee of a result.

Implementation and Evaluation

The authors developed a prototype implementation of their simplification procedure. To test its efficacy, they evaluated it against instances from the SMT-LIB (Satisfiability Modulo Theories Library), which serves as the industry standard for benchmarking SMT solvers. While quantitative metrics were deferred to the full workshop proceedings, the prototype demonstrates the practical feasibility of using tree theories for (co)datatype reasoning.

Conclusion

By introducing a finiteness predicate and a robust simplification procedure, this research successfully adapts classical tree theory for modern computational needs. The result is a more expressive, yet still decidable, framework that paves the way for more powerful automated reasoning tools in formal verification.

Summary updated

Abstract

The first-order theory of finite and infinite trees has been studied since the eighties, especially by the logic programming community. Following Djelloul, Dao and Frühwirth, we consider an extension of this theory with an additional predicate for finiteness of trees, which is useful for expressing properties about (not just datatypes but also) codatatypes. Based on their work, we present a simplification procedure that determines whether any given (not necessarily closed) formula is satisfiable, returning a simplified formula which enables one to read off all possible models. Our extension makes the algorithm usable for algebraic (co)datatypes, which was impossible in their original work due to restrictive assumptions. We also provide a prototype implementation of our simplification procedure and evaluate it on instances from the SMT-LIB.
BibTeX
@inproceedings{zaiser2021abstract,
  author = {Fabian Zaiser and Luke Ong},
  title = {{Abstract: The Extended Theory of Trees and Algebraic (Co)datatypes}},
  booktitle = {SMT},
  year = {2021},
}
Figure