Simplified and Verified: A Second Look at a Proof-Producing Union-Find Algorithm

Lukas Stevens, Rebecca Ghidini · 2025

Read Simplified and Verified: A Second Look at a Proof-Producing Union-Find Algorithm by Lukas Stevens, Rebecca Ghidini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10246.txt.

Introduction

Lukas Stevens and Rebecca Ghidini revisit a verified data structure in a 2025 paper. Union-find is a classic tool that tracks which items belong to the same group, and one version can also explain its answers with a proof. That explaining version, by Nieuwenhuis and Oliveras, is useful inside logic solvers but hard to check by machine.

Working in the Isabelle/HOL proof assistant, the pair first built a simpler explain step whose soundness is easy to verify. They then proved the original step gives the same results as theirs. Last, they turned the design into fast imperative code that a computer can run. Verified parts like these raise trust in the solvers that check chips, code, and proofs.

Catalog record

CREATORLukas Stevens, Rebecca Ghidini
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10246

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Simplified and Verified: A Second Look at a Proof-Producing Union-Find Algorithm Lukas Stevens, Rebecca Ghidini Abstract Using Isabelle/HOL, we verify a union-find data structure with an explain operation due to Nieuwenhuis and Oliveras . We devise a simpler, more naive version of the explain operation whose soundness and completeness is easy to verify. Then, we prove the original formulation of the explain operation to be equal to our version. Finally, we refine this data structure to Imperative HOL, enabling us to export efficient imperative code. The formalisation provides a stepping stone towards the verification of proof-producing congruence closure algorithms which are a core ingredient of Satisfiability Modulo Theories (SMT) solvers. \isadelimtheory \endisadelimtheory \isatagtheory \endisatagtheory \isadelimtheory \endisadelimtheory \isadelimML \endisadelimML \isatagML \endisatagML \isadelimML \endisadelimML \isadelimML \endisadelimML \isatagML \endisatagML \isadelimML \endisadelimML \isadelimML \endisadelimML \isatagML \endisatagML \isadelimML \endisadelimML \isadelimtheory \endisadelimtheory \isatagtheory \endisatagtheory \isadelimtheory \endisadelimtheory \isadelimtheory \endisadelimtheory \isatagtheory theory Document imports Main Union - Find - Explain \mathord{.} Explain - Imp LaTeXsugar begin \endisatagtheory \isadelimtheory \endisadelimtheory \isadelimdocument \endisadelimdocument \isatagdocument 1 Introduction \endisatagdocument \isadelimdocument \endisadelimdocument The Union-Find (UF) data structure maintains the equivalence closure of a relation, which is given as a sequence of pairs or, in terms of the UF data structure, union operations. It is fundamental to efficiently implement well-known graph algorithms such as Kruskal ’s [ 14 ] minimum spanning-tree algorithm. There, it tracks which vertices belong to the same connected component and are, in that sense, equivalent. Beyond graph algorithms, its applicability extends to the domain of theorem proving as it routinely forms the basis of congruence closure algorithms, which are widely used by Satisfiability Modulo Theories (SMT) solvers. To increase their trustworthiness, current SMT solvers such as cvc5 [ 3 ] , E [ 26 ] , Vampire [ 13 ] , veriT [ 4 ] , and Z3 [ 18 ] can output detailed proofs when they determine an input formula to be unsatisfiable. To produce these proofs, it is crucial to have congruence closure algorithms that efficiently explain why they consider two terms to be equal. The first such algorithm was presented by Nieuwenhuis and Oliveras [ 20 , 21 ] , who extended the UF data structure with an explain operation to obtain a Union-Find-Explain (UFE) data structure. Verifying this data structure in Isabelle/HOL is the focus of our paper. Why, then, should we verify a data structure that already produces proofs? Our answer is three-fold. (1) While the data structure’s proofs guarantee soundness, we also prove its completeness. (2) Executing code exported from Isabelle depends on a substantial trusted computing base (TCB) , including the target language’s compiler and runtime. (3) Whereas SMT solvers typically operate with a large TCB , adding to the TCB of interactive theorem provers is usually discouraged. Proof-producing algorithms — such as those introduced in earlier work by the first author [ 27 ] — enable integration without increasing the TCB . \isadelimdocument \endisadelimdocument \isatagdocument 1.1 Contributions \endisatagdocument \isadelimdocument \endisadelimdocument We present, to our knowledge, the first formalisation of the UFE data structure as introduced by Nieuwenhuis and Oliveras . In their work, they present two variants of this data structure. Here, we only formalise the first variant, leaving the other for future work. We devise a simpler, more naive version of the explain operation, for which soundness and completeness is easier to prove. Then, we prove the original version of the explain operation to be extensionally equal to the simple one. Based on an existing formalisation of the UF data structure by Lammich [ 15 ] , we develop a more abstract formalisation of the data structure, hiding implementation details. Finally, we refine the UFE data structure to Imperative HOL [ 5 ] using Lammich ’s [ 15 ] separation logic framework, enabling generation of efficient imperative code. The formalisation is available online. 1 1 1 https://doi.org/10.5281/zenodo.15557955 Since everything is verified, we omit proofs and focus on outlining the structure of the formalisation. \isadelimdocument \endisadelimdocument \isatagdocument 1.2 Related Work \endisatagdocument \isadelimdocument \endisadelimdocument Efficient implementations of the UF data structure have been known for a long time. In particular, Galler and Fisher [ 9 ] represent the data structure as a forest of rooted trees and propose the union-by-size heuristic, which gives \mathcal{O}(\log n) running time for union and find for a data struture over n elements. Another heuristic, called path compression, was presented by Aho et al. [ 1 ] . Analysing the complexity of the data structure when combining both heuristics turned out to be challenging, but Tarjan [ 28 ] and Tarjan and van Leeuwen [ 29 ] eventually proved an amortised running time of \mathcal{O}(n+m\,\alpha(m+n,n)) for a sequence of at most n-1 union and m find operations where \alpha is the inverse Ackermann function. This means that any one operation runs in almost constant time, amortised. While the paper on the UFE data structure [ 20 ] is widely cited, there is limited follow-up literature on this data structure. It does, however, form the basis of proof-producing congruence closure algorithms, which are crucial in the field of SMT solving. There, they remain an active area of research; for example, when we are interested in efficiently finding small proofs [ 8 ] . The literature of verified algorithms and data structures is vast so we refer to a survey [ 22 ] for an overview. Focusing on the UF data structure, there is a formalisation in Coq [ 7 ] , where the amortised complexity is analysed by Charguéraud and Pottier [ 6 ] in a separation logic with time credits. Similarly, in Isabelle, there is a formalisation of the data structure [ 15 ] that was later extended with a complexity analysis by Haslbeck and Lammich [ 11 ] . More recently, there is formalisation by Guttmann [ 10 ] taking a relation-algebraic view. \isadelimdocument \endisadelimdocument \isatagdocument 1.3 Notation \endisatagdocument \isadelimdocument \endisadelimdocument Isabelle/HOL [ 23 ] conforms to everyday mathematical notation for the most part. We establish notation and in particular some essential data types together with their primitive operations that are specific to Isabelle/HOL. We write t \mathord{:} \mathord{:} \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a to specify that the term t has the type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a and \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a \Rightarrow \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu b for the space of total functions from type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a to type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu b . Sets with elements of type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a have the type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a set . The cardinality of a set A is denoted by \mid A \mid . We use \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a list to describe the type of lists, which are constructed using the empty list [ ] or the infix cons constructor ( \# ) , and are appended with the infix operator ( @ ) . The length of list xs is denote by \mid xs \mid . The function \mathsf{set} converts a list into a set. We write xs ! i to access the i -th element of the list xs . To represent partial values of type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a , we use the type \mskip 2.0mu{{}^{\prime}}\mskip-2.0mu a option with the constructors \mathsf{None} and \mathsf{Some} . We also define an order on this type by letting \mathsf{None} be smaller than \mathsf{Some} and

Read the complete text